JavaRush /Java Blog /Random-TW /摸索演算法或輕鬆介紹演算法

等級 3

28 二月 2021
42 views
0 comments

摸索演算法或輕鬆介紹演算法

《Grocking Algorithms》一書的評論。一點個人看法，舉幾個例子。我希望這篇評論能幫助您了解您是否想閱讀這本書，或者它是否不會在您的書架上佔據一席之地。警告：大量文字）

“增長演算法”或輕鬆介紹演算法

介紹

幾乎所有初級職缺都有「資料結構和演算法知識」等要求。對於受過專業教育的人來說，演算法屬於普通課程，應該沒有問題。但如果這些發展是從其他草原引進的呢？剩下的就是自己學習了。「誰該責備」這個問題是有答案的，但「該做什麼」這個問題必須尋求答案。我們去書本上看看吧。我想告訴你一個。

Grok 演算法

在所有的著作中，我看到了《Grocking Algorithms》這樣一本書。您可以在這裡找到更多資訊：“ 《增長演算法。為程式設計師和好奇者提供的圖解指南》一書。” 我很久以前就注意到這本書了，但臭氧價格是680盧布。貴還是便宜－每個人自己決定。我已經以一半的價格購買了關於 Avito 的第二本書。所以我在聖彼得堡找到了它，買了它，然後去探索。這就是我決定與大家分享的內容。是的，書中沒有 Java 程式碼，但有…其他程式碼，稍後會詳細介紹。

演算法簡介（選擇排序）

因此，以一種簡單的敘述形式，我們達到了表演的第一個排序。這就是選擇排序。它的本質是我們從左到右（從0個元素到最後一個）遍歷元素，並在剩餘元素中尋找最大的元素。如果找到它，那麼我們就交換現在所在的元素和最大的元素。首先想到陣列的最簡單的方式是：[5, 3, 6, 2, 10]。拿一張紙，一支筆（最簡單、最便宜的方式），想像我們如何有一個左邊框（左），一個當前索引（或右邊框），有一個最小元素的索引。以及我們如何使用它。例如：

演算法通常以偽代碼描述，例如在維基百科上。我們的程式碼並不完全是偽代碼，稍後會詳細介紹。現在讓我們來看看：


def selectionSort(array):
    for left in range(0, len(array)):
        minIndex = left
        for right in range (left+1, len(array)):
            if array[right] < array[minIndex]:
                minIndex = right
        if minIndex != left:
            temp = array[left]
            array[left] = array[minIndex]
            array[minIndex] = temp
    return array

print(selectionSort([5, 3, 6, 2, 10]))

現在我們以Java程式碼的形式來呈現：

public static void selectionSort(int[] array) {
        for (int left = 0; left < array.length; left++) {
            int minIndex = left;
            for (int right = left+1; right < array.length; right++) {
                if (array[right] < array[minIndex]) {
                    minIndex = right;
                }
            }
            if (minIndex != left) {
                int temp = array[left];
                array[left] = array[minIndex];
                array[minIndex] = temp;
            }
        }
}

正如您所看到的，程式碼幾乎是相同的。第一個程式碼是書中的範例。第二個是我在Java程式碼中的自由執行。

遞迴

接下來我們被告知有遞歸這樣的東西。首先，存在一個關於擁有 AxB 大小田地的農民的問題。有必要將這個領域分成相等的「正方形」。然後提到歐幾裡得演算法。我不喜歡的是他們沒有嘗試編寫其程式碼。但歐幾裡得演算法簡單有效：

老實說，我錯過了書中的一些細節，例如這個影片：「資訊學。算法理論。歐幾裡得演算法。” 例如，如果 a 小於 b，則在第一次運行期間 b 和 a 將交換位置，第二次時較大的值將除以較小的值。因此，參數的順序並不重要。像往常一樣，首先我們可以在一張紙上「感受」演算法：

現在我們來看看程式碼：


def euclidean(a, b):
    if a == 0 : return b
    if b == 0 : return a
    return euclidean (b, a % b)

讓我們用 Java 來寫相同的程式碼。如果需要，我們可以使用線上編譯器：

public static int euclid(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        return euclid(b, a%b);
}

本書開頭也提到了階乘。數字 n (n!) 的階乘是從 1 到 n 的數字的乘積。為什麼要這樣做？這裡有一個實際應用。如果我們有 n 個物件（例如，n 個城市），那麼我們可以製作 n 個！組合。您可以在此處閱讀有關遞歸的更多資訊：“遞歸。訓練任務。” 迭代和遞歸方法的比較：「遞歸」。

快速排序

快速排序是一個相當有趣的演算法。書中並沒有太在意他。此外，僅給出最壞情況（當選擇第一個元素時）的代碼。然而，也許對於第一次認識的人來說這個例子會更容易記住。寫一個糟糕的快速排序比根本不寫好。這是書中的一個例子：


def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

這裡的一切都超級簡單。如果我們有一個包含 0 或 1 個元素的數組，則無需對其進行排序。如果它更大，我們就取出數組的第一個元素並將其視為“樞軸元素”。我們建立 2 個新陣列 - 第一個包含比主元大的元素，第二個包含比主元小的元素。我們遞歸地重複。這不是最好的選擇，但還是最好記住。讓我們用 Java 實作這個演算法，但更正確。評論“ JavaScript 中的計算機科學：快速排序”中的材料將幫助我們解決這個問題。在寫程式之前，我們再畫一下來「感受」一下演算法：首先，我們在一張紙上再畫一下，來理解演算法：

在我看來，最危險的時刻之一就是徹底解決問題。因此，我們將分幾個小步驟來進行實作：

我們需要能夠交換數組中的元素：

private static void swap(int[] array, int firstIndex, int secondIndex) {
        int temp = array[firstIndex];
        array[firstIndex] = array[secondIndex];
        array[secondIndex] = temp;
}

我們需要一個方法，將指定區間內的陣列分成 3 部分

private static int partition(int[] array, int left, int right) {
        int pivot = array[(right + left) / 2];
        while (left <= right) {
            while (array[left] < pivot) {
                left++;
            }
            while (array[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(array, left, right);
                left++;
                right--;
            }
        }
        return left;
}

詳情請見上面的連結。簡而言之，我們移動左遊標，直到該元素小於樞軸。同樣，從另一端移動右遊標。如果遊標不匹配，我們會進行交換。我們繼續直到遊標收斂。我們回傳一個索引，將進一步處理分為兩部分。

有一個分離，我們需要排序本身：

public static void quickSort(int[] array, int left, int right) {
        int index = 0;
        if (array.length > 1) {
            index = partition(array, left, right);
            if (left < index - 1) {
                quickSort(array, left, index - 1);
            }
            if (index < right) {
                quickSort(array, index, right);
            }
        }
}

也就是說，如果陣列至少包含兩個元素，那麼它們就已經可以排序了。首先，我們將整個陣列分成兩部分，小於主元的元素和大於主元的元素。然後我們對每個結果部分執行類似的操作。

對於測試：

public static void main(String []args){
        int[] array = {8,9,3,7,6,7,1};
        quickSort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
}

書中指出，該演算法屬於所謂的「分而治之」演算法，即每次將處理的資料集一分為二。演算法複雜度：O(nLogn)

不好的（也就是我不喜歡的）是這本書順便提到了合併排序，但沒有提供任何範例或程式碼。更多詳細資訊可以在這裡找到：「資訊學。搜尋和排序演算法：歸併排序」。因此，為了保持一致性，我們還是自己來做吧。當然，演算法本身本質上是簡單明了的：

public static void mergeSort(int[] source, int left, int right) {
    if ((right - left) > 1) {
        int middle = (right + left) / 2;
        mergeSort(source, left, middle);
        mergeSort(source, middle + 1, right);
    }
    merge(source, left, right);
}

我們確定中間位置並將陣列分成兩半。對於每一半，我們都做同樣的事情，依此類推。停止條件或基本情況 - 我們必須有多個元素，因為我們不能將一個元素一分為二。現在我們需要實作合併，也就是merge：

public static void merge(int[] array, int from, int to) {
    int middle = ((from + to) / 2) + 1;
    int left = from;
    int right = middle;
    int cursor = 0;

    int[] tmp = new int[to - from + 1];
    while (left < middle || right <= to) {
        if (left >= middle) {
            tmp[cursor] = array[right];
            System.out.println("Остаток справа: " + array[right]);
            right++;
        } else if (right > to) {
            tmp[cursor] = array[left];
            System.out.println("Остаток слева: " + array[left]);
            left++;
        } else if (array[left] <= array[right]) {
            tmp[cursor] = array[left];
            System.out.println("Слева меньше: " + array[left]);
            left++;
        } else if (array[right] < array[left]) {
            tmp[cursor] = array[right];
            System.out.println("Справа меньше: " + array[right]);
            right++;
        }
        cursor++;
    }
    System.arraycopy(tmp, 0, array, from, tmp.length);
}

這裡沒有太多可評論的。從變數的名稱來看，println一切都清楚了。好吧，檢查一下：

int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));

哈希表

本書也涉及哈希表。您不必自己實現它，哈希表的本質非常簡單。畢竟Java也有哈希表的實現，java.util.HashTable。如果我們查看 HashTable 設備，我們會看到 Entry 陣列位於其中。Entry是一個由Key-Value組合而成的記錄。HashTable有initialCapacity－即初始大小。loadFactor——負載因子。預設值為 0.75。這個數字告訴您在數組負載達到什麼程度（元素數/總量）時需要增加大小。在Java中它增加了2倍。書中解釋說，哈希表之所以稱為哈希表，是因為基於雜湊函數，其中的數組單元（籃子）Entry。您也可以在這裡閱讀更多內容：圖片中的資料結構。HashMap和LinkedHashMap。你也可以在書上讀到。例如這裡：“哈希表基礎知識”

圖，廣度優先搜尋（最短路徑搜尋）

圖表可能是最有趣的主題之一。公平地說，本書對它們給予了許多關注。也許這就是這本書值得一讀的原因。雖然也許可以說得更清楚一些））但是，我們有互聯網，除了這本書之外，您還可以查看這個關於“那些第一次聽說圖表的人”的理論的播放列表。 ” 嗯，自然地，在本書的一開始，breadth-first-search就給出了廣度優先搜尋演算法，也稱為 BFS。書中包含以下圖表：

書中指出隊列會對我們有幫助。此外，我們可以將元素新增至末端並從頭開始處理佇列。這樣的隊列稱為雙向隊列，英文稱為Deque。書中建議使用一種資料結構—哈希表。將名稱和鄰居關聯起來。對於編號的頂點，您可以簡單地使用陣列。這種頂點存儲稱為“相鄰頂點列表”，書中沒有提及。這對他們來說是一個缺點。讓我們用 Java 來實作這個：

private Map<String, String[]> getGraph() {
    Map<String, String[]> map = new HashMap<>();
    map.put("you", new String[]{"alice", "bob", "claire"});
    map.put("bob", new String[]{"anuj", "peggy"});
    map.put("alice", new String[]{"peggy"});
    map.put("claire", new String[]{"thom", "jonny"});
    map.put("annuj", null);
    map.put("peggy", null);
    map.put("thom", null);
    map.put("johny", null);
    return map;
}

現在搜尋本身是建立在這些數據的基礎上的：

private String search() {
    Map<String, String[]> graph = getGraph();
    Set<String> searched = new HashSet<>();
    Deque<String> searchQue = new ArrayDeque<>();
    searchQue.add("you");
    while (!searchQue.isEmpty()) {
        String person = searchQue.pollFirst();
        System.out.println(person);
        if (personIsSeller(person)) {
            return person;
        } else {
            String[] friends = graph.get(person);
            if (friends == null) continue;
            for (String friend : friends) {
                if (friend != null && !searched.contains(friend)) {
                    searchQue.addLast(friend);
                }
            }
        }
    }
    return null;
}

如您所見，沒什麼複雜的。和書上的程式碼比較一下，幾乎是一樣的。

圖，Dijkstra 演算法

或多或少了解了 BFS，本書作者邀請我們了解 Daysktra 演算法和加權圖。建議下圖作為解決方案：

首先，我們需要了解如何表示我們的圖表。我們可以將其表示為矩陣。關於 Habré 的文章將對我們有所幫助：Dijkstra 演算法。在圖表上尋找最佳路線。讓我們使用鄰接矩陣：

public Integer[][] getGraphMatrix(int size) {
    Integer[][] matrix = new Integer[size][size];
    matrix[0][1] = 6;
    matrix[0][2] = 2;
    matrix[2][1] = 3;
    matrix[1][3] = 1;
    matrix[2][3] = 5;
    return matrix;
}

現在邏輯本身：

@Test
public void dijkstra() {
    Integer[][] graph = getGraphMatrix();           // Данные графа
    Integer[] costs = new Integer[graph.length];    // Стоимость перехода
    Integer[] parents = new Integer[graph.length];  // Родительский узел
    BitSet visited = new BitSet(graph.length);      // "Ферма" маркеров посещённости

    Integer w = 0;
    do {
        System.out.println("-> Рассматриваем вершину: " + w);
        Integer min = null;
        for (int i = 0; i < graph.length; i++) {    // Обрабатываем каждую дугу
            if (graph[w][i] == null) continue;      // Дуги нет - идём дальше
            if (min == null || (!visited.get(i) && graph[w][min] > graph[w][i])) {
                min = i;
            }
            if (costs[i] == null || costs[i] > costs[w] + graph[w][i]) {
                System.out.print("Меням вес с " + costs[i]);
                costs[i] = (costs[w] != null ? costs[w] : 0) + graph[w][i];
                System.out.println(" на " + costs[i] + " для вершины " + i);
                parents[i] = w;
            }
        }
        System.out.println("Вершина с минимальным весом: " + min);
        visited.set(w);
        w = min;
    } while (w != null);

    System.out.println(Arrays.toString(costs));
    printPath(parents, 3);
}

public void printPath(Integer[] parents, int target) {
    Integer parent = target;
    do {
        System.out.print(parent + " <- ");
        parent = parents[parent];
    } while (parent != null);
}

這本書一步一步地分解了它。如果你在網路上加入Habré的文章+看看程式碼，你就能記住它。我發現逐步分析有點混亂。但對於循序漸進的性質本身來說，這是一個優點。整體來說還可以，雖然可以更好）

貪心演算法

下一節專門討論「貪婪演算法」。本節很有趣，因為它使用了集合（java.util.Set）。最後我們可以明白為什麼需要它。我們使用狀態列表作為輸入：

Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));

還有涵蓋其中一些州的廣播電台清單：

Map<String, Set<String>> stations = new HashMap<>();
stations.put("kone", new HashSet(Arrays.asList("id", "nv", "ut")));
stations.put("ktwo", new HashSet(Arrays.asList("wa", "id", "mt")));
stations.put("kthree", new HashSet(Arrays.asList("or", "nv", "ca")));
stations.put("kfour", new HashSet(Arrays.asList("nv", "ut")));
stations.put("kfive", new HashSet(Arrays.asList("ca", "az")));

書中接著指出並解釋了演算法本身：

Set<String> finalStations = new HashSet();
while (!statesNeeded.isEmpty()) {
    String bestStation = null;
    Set<String> statesCovered = new HashSet();
    for (String station: stations.keySet()) {
        Set covered = new HashSet(statesNeeded);
        covered.retainAll(stations.get(station));
        if (covered.size() > statesCovered.size()) {
           bestStation = station;
           statesCovered = covered;
        }
    }
    statesNeeded.removeAll(statesCovered);
    finalStations.add(bestStation);
}
System.out.println(finalStations);

動態規劃

本書也描述了應用「動態規劃」方法的問題。任務給出：

我們有一個 4 磅的袋子。您需要找到給定重量下最賺錢的商品。首先，讓我們列出一個項目清單：

List<Thing> things = new ArrayList<>();
things.add(new Thing("guitar", 1, 1500));
things.add(new Thing("tape recorder", 4, 3000));
things.add(new Thing("notebook", 3, 2000));

現在演算法本身：

int bagSize = 4;
int cell[][] = new int[things.size()][bagSize];
// Заполняем первую строку без условий
for (int i = 0; i < bagSize; i++) {
    cell[0][i] = things.get(0).cost;
}
// Заполняем оставшиеся
for (int i = 1; i < cell.length; i++) {
    for (int j = 0; j < cell[i].length; j++) {
        // Если вещь не влезает - берём прошлый максимум
        if (things.get(i).weight > j+1) {
            cell[i][j] = cell[i - 1][j];
        } else {
            // Иначе текущая стоимость + предыдущий максимум оставшегося размера
            cell[i][j] = things.get(i).cost;
            if (j + 1 - things.get(i).weight > 0) {
                cell[i][j] += cell[i-1][j + 1 - things.get(i).weight];
            }
        }
    }
}
System.out.println(Arrays.deepToString(cell));

還有一個有趣的任務是找到最相似的單字。很有趣，不是嗎？更多詳細資訊請參閱：LongestCommonSubsequence.java

搜尋最近的鄰居

書中也非常清楚地講了k近鄰演算法：

並給出計算公式：

底線

本書最後有一個有趣的「下一步是什麼？」部分，其中提供了有趣演算法的快速概述。這裡簡單介紹一下樹和其他演算法的意思。總的來說，我喜歡這本書。不應將其視為某種綜合資訊。你必須自己去尋找和理解。但作為引起興趣並給出初步想法的介紹訊息，這是相當不錯的。是的，書中的程式碼是用Python寫的。所以上面所有的例子都是可以編譯的）我希望這篇評論能幫助你了解這本書包含什麼內容以及它是否值得購買。