Grocking-Algorithmen oder eine schmerzlose Einführung in Algorithmen

Rezension des Buches „Grocking Algorithms“. Eine kleine persönliche Meinung, ein paar Beispiele. Ich hoffe, diese Rezension hilft Ihnen zu verstehen, ob Sie dieses Buch lesen möchten oder ob es nicht in Ihrem Regal Platz findet. ACHTUNG: Viel Text)

„Grocking Algorithms“ oder eine schmerzlose Einführung in Algorithmen

Einführung

Für fast jede Junior-Stelle gelten Anforderungen wie „Kenntnisse über Datenstrukturen und Algorithmen“. Für diejenigen, die eine spezielle Ausbildung haben, sind Algorithmen im allgemeinen Kurs enthalten und es sollte keine Probleme geben. Was aber, wenn die Entwicklung aus anderen Steppen eingeschleppt würde? Es bleibt nur noch, selbst zu lernen. Es gibt eine Antwort auf die Frage „Wer ist schuld“, aber auf die Frage „Was ist zu tun?“ muss eine Antwort gesucht werden. Schauen wir mal in Büchern nach. Und davon möchte ich Ihnen etwas erzählen.

Grok-Algorithmen

Unter all den Werken stieß ich auf ein Buch wie „Grocking Algorithms“. Mehr erfahren Sie hier: „ Das Buch „Growing Algorithms. Ein illustrierter Leitfaden für Programmierer und Neugierige .“ Das Buch ist mir schon vor langer Zeit aufgefallen, aber bei Ozon kostete es 680 Rubel. Teuer oder günstig – das entscheidet jeder für sich. Ich kaufe bereits das zweite Buch bei Avito zum halben Preis. Also fand ich es in St. Petersburg, kaufte es und machte mich auf den Weg zum Einkaufen. Genau das habe ich beschlossen, mit Ihnen zu teilen. Ja, das Buch enthält keinen Java-Code, aber es gibt... anderen Code, aber dazu später mehr.

Einführung in Algorithmen (Auswahlsortierung)

So gelangen wir in einer einfachen Form des Erzählens zur ersten Sortierung unserer Darbietung. Dies ist die Auswahlsortierung. Sein Wesen besteht darin, dass wir die Elemente von links nach rechts durchgehen (vom Element 0 bis zum letzten) und nach dem größten unter den verbleibenden Elementen suchen. Wenn wir es finden, dann tauschen wir das Element, auf dem wir uns gerade befinden, und das größte Element. Der einfachste Weg, sich zunächst ein Array vorzustellen, ist: [5, 3, 6, 2, 10]. Nehmen Sie ein Blatt Papier, einen Stift (die einfachste und kostengünstigste Methode) und stellen Sie sich vor, dass wir einen linken Rand, einen aktuellen Index (oder rechten Rand) und einen Index des minimalen Elements haben. Und wie wir damit arbeiten. Zum Beispiel: Algorithmen werden häufig in Pseudocode beschrieben, beispielsweise auf Wikipedia. Bei uns handelt es sich nicht gerade um Pseudocode, aber dazu später mehr. Schauen wir uns zunächst Folgendes an:

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]))

Lassen Sie es uns nun in Form von Java-Code präsentieren:

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;
            }
        }
}

Wie Sie sehen, ist der Code fast derselbe. Der erste Code ist ein Beispiel aus dem Buch. Das zweite ist meine kostenlose Ausführung in Java-Code.

Rekursion

Als nächstes wird uns gesagt, dass es so etwas wie Rekursion gibt. Erstens gibt es ein Problem mit einem Landwirt, der ein Feld der Größe AxB hat. Es ist notwendig, dieses Feld in gleiche „Quadrate“ zu unterteilen. Und danach wird der Euklid-Algorithmus erwähnt. Was mir nicht gefällt, ist, dass sie nicht versucht haben, den Code zu schreiben. Aber der Euklid-Algorithmus ist einfach und effektiv: Ehrlich gesagt habe ich einige Details im Buch übersehen, wie zum Beispiel in diesem Video: „ Informatik. Theorie der Algorithmen. Euklids Algorithmus . Wenn beispielsweise a kleiner als b ist, tauschen b und a beim ersten Durchlauf die Plätze und beim zweiten Mal wird der größere durch den kleineren geteilt. Daher ist die Reihenfolge der Argumente nicht wichtig. Wie üblich können wir den Algorithmus zunächst auf einem Blatt Papier „erfühlen“: Schauen wir uns nun den Code an:

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

Schreiben wir den gleichen Code in Java. Auf Wunsch können wir den Online-Compiler verwenden :

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

Factorial wurde auch am Anfang des Buches erwähnt. Die Fakultät einer Zahl n (n!) ist das Produkt der Zahlen von 1 bis n. Warum das tun? Hier gibt es eine praktische Anwendung. Wenn wir n Objekte haben (zum Beispiel n Städte), dann können wir n davon machen! Kombinationen. Weitere Informationen zur Rekursion finden Sie hier: „ Rekursion. Trainingsaufgaben “. Vergleich iterativer und rekursiver Ansätze: „ Rekursion “.

Schnelle Sorte

Quick Sort ist ein ziemlich interessanter Algorithmus. Das Buch schenkt ihm keine große Aufmerksamkeit. Darüber hinaus wird der Code nur für den schlimmsten Fall angegeben, wenn das erste Element ausgewählt wird. Für eine erste Bekanntschaft ist dieses Beispiel jedoch vielleicht leichter zu merken. Und es ist besser, einen schlechten Quicksort zu schreiben, als überhaupt keinen zu schreiben. Hier ist ein Beispiel aus dem Buch:

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)

Hier ist alles super einfach. Wenn wir ein Array mit 0 oder 1 Elementen haben, besteht keine Notwendigkeit, es zu sortieren. Wenn es größer ist, nehmen wir das erste Element des Arrays und betrachten es als „Pivot-Element“. Wir erstellen zwei neue Arrays – eines enthält Elemente, die größer als der Pivot sind, und das zweite enthält Elemente, die kleiner sind. Und wir wiederholen es rekursiv. Nicht die beste Option, aber besser im Gedächtnis. Lassen Sie uns diesen Algorithmus in Java implementieren, aber korrekter. Das Material aus der Rezension „ Computer Science in JavaScript: Quicksort “ wird uns dabei helfen . Und bevor wir den Code schreiben, zeichnen wir noch einmal, um den Algorithmus zu „fühlen“: Zeichnen wir zunächst noch einmal auf ein Blatt Papier, um den Algorithmus zu verstehen: Es scheint mir, dass einer der gefährlichsten Momente darin besteht, Probleme vollständig zu lösen. Daher werden wir die Umsetzung in mehreren kleinen Schritten durchführen:

• Wir müssen in der Lage sein, Elemente in einem Array auszutauschen:

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




• Wir benötigen eine Methode, die das Array im angegebenen Intervall in 3 Teile unterteilt

  
  

  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;
  }

  Details unter dem Link oben. Kurz gesagt, wir bewegen den linken Cursor, bis das Element kleiner als der Pivot ist. Bewegen Sie auf ähnliche Weise den rechten Cursor vom anderen Ende. Und wir führen einen Tausch durch, wenn die Cursor nicht übereinstimmen. Wir machen weiter, bis die Cursor konvergieren. Wir geben einen Index zurück, der die weitere Verarbeitung in zwei Teile unterteilt.

• Es gibt eine Trennung, wir brauchen die Sortierung selbst:

  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);
              }
          }
  }

  Das heißt, wenn das Array aus mindestens zwei Elementen besteht, können diese bereits sortiert werden. Zuerst teilen wir das gesamte Array in zwei Teile, Elemente, die kleiner als der Pivot sind, und Elemente, die größer sind. Dann führen wir ähnliche Aktionen für jedes der resultierenden Teile durch.

  Und zum Test:

  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));
  }

Das Buch besagt, dass dieser Algorithmus zu den sogenannten „Divide and Conquer“-Algorithmen gehört, bei denen der verarbeitete Datensatz jedes Mal in zwei Hälften geteilt wird. Algorithmuskomplexität: O(nLogn) Was schlecht ist (das heißt, was mir nicht gefallen hat), ist, dass das Buch die Zusammenführungssortierung am Rande erwähnt, aber kein Beispiel oder Code bereitstellt. Weitere Details finden Sie hier: „ Informatik. Such- und Sortieralgorithmen: Sortierung zusammenführen “. Aus Gründen der Konsistenz machen wir es daher selbst. Der Algorithmus selbst ist natürlich von Natur aus einfach und unkompliziert:

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);
}

Wir bestimmen die Mitte und teilen das Array in zwei Hälften. Für jede Hälfte machen wir dasselbe und so weiter. Stoppbedingung oder Basisfall – wir müssen mehr als ein Element haben, da wir ein Element nicht in zwei teilen können. Jetzt müssen wir die Zusammenführung implementieren, das heißt zusammenführen:

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);
}

Hier gibt es nicht viel zu kommentieren. Aus den Namen der Variablen printlnist alles klar. Nun, um zu überprüfen:

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

Hash-Tabellen

Das Buch geht auch auf Hash-Tabellen ein. Sie müssen es nicht selbst implementieren und die Essenz von Hash-Tabellen ist recht einfach. Schließlich verfügt Java auch über eine Implementierung von Hash-Tabellen, java.util.HashTable. Wenn wir uns das HashTable-Gerät ansehen, werden wir sehen, dass sich darin das Entry-Array befindet. Der Eintrag ist ein Datensatz, der eine Kombination aus Schlüssel und Wert darstellt. HashTable hat initialCapacity, also die Anfangsgröße. Und LoadFactor – Lastfaktor. Der Standardwert ist 0,75. Diese Zahl gibt an, bei welcher Auslastung des Arrays (Anzahl der Elemente/Gesamtmenge) die Größe erhöht werden muss. In Java erhöht es sich um das Zweifache. Das Buch erklärt, dass Hash-Tabellen Hash-Tabellen genannt werden, weil basierend auf der Hash-Funktion die Array-Zelle (Korb), in der die Entry. Mehr können Sie auch hier lesen: Datenstrukturen in Bildern. HashMap und LinkedHashMap . Man kann es auch in Büchern lesen. Zum Beispiel hier: „ HashTable-Grundlagen “

Diagramme, Breitensuche (Suche nach kürzestem Weg)

Eines der wahrscheinlich interessantesten Themen sind Grafiken. Und hier muss man fairerweise sagen, dass das Buch ihnen viel Aufmerksamkeit schenkt. Vielleicht lohnt es sich deshalb, dieses Buch zu lesen. Obwohl es vielleicht etwas klarer hätte ausgedrückt werden können)) Aber wir haben das Internet und zusätzlich zum Buch können Sie sich diese Playlist zur Theorie für „diejenigen anschauen, die zum ersten Mal von Grafiken hören“ . ” Nun, natürlich wird gleich zu Beginn des Buches der Breitensuchalgorithmus, breadth-first-searchauch bekannt als BFS, vorgestellt. Das Buch enthält die folgende Grafik: Im Buch heißt es, dass uns eine Warteschlange helfen wird. Darüber hinaus können wir am Ende Elemente hinzufügen und die Warteschlange von Anfang an verarbeiten. Solche Warteschlangen werden im Englischen Zwei-Wege-Warteschlangen oder Deque genannt. Das Buch schlägt die Verwendung einer Datenstruktur vor – einer Hash-Tabelle. Um den Namen und die Nachbarn in Beziehung zu setzen. Bei nummerierten Scheitelpunkten können Sie einfach ein Array verwenden. Diese Speicherung von Scheitelpunkten wird als „Liste benachbarter Scheitelpunkte“ bezeichnet, was im Buch nicht erwähnt wird. Das ist ein Minuspunkt für sie. Lassen Sie uns dies in Java implementieren:

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;
}

Nun die Suche selbst, basierend auf diesen Daten:

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;
}

Wie Sie sehen, nichts Kompliziertes. Wenn man es mit dem Code aus dem Buch vergleicht, ist es fast dasselbe.

Graphen, Dijkstras Algorithmus

Nachdem wir BFS mehr oder weniger verstanden haben, lädt uns der Autor des Buches ein, den Daysktra-Algorithmus und die gewichteten Diagramme zu verstehen. Zur Lösung wird folgender Graph vorgeschlagen: Zuerst müssen wir verstehen, wie wir unsere Diagramme darstellen. Wir könnten es als Matrix darstellen. Hier hilft uns ein Artikel über Habré: Dijkstras Algorithmus. Optimale Routen anhand einer Grafik finden . Verwenden wir die Adjazenzmatrix:

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;
}

Und nun die Logik selbst:

@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);
}

Das Buch schlüsselt es Schritt für Schritt auf. Wenn Sie einen Artikel über Habré im Internet hinzufügen + sich den Code ansehen, können Sie ihn sich merken. Ich fand die Schritt-für-Schritt-Analyse etwas unübersichtlich. Aber für die schrittweise Natur selbst ist es ein Plus. Insgesamt ok, hätte aber besser sein können)

Gierige Algorithmen

Der nächste Abschnitt ist den „gierigen Algorithmen“ gewidmet. Dieser Abschnitt ist interessant, weil er Sets (java.util.Set) verwendet. Endlich können wir sehen, warum es nötig sein könnte. Als Eingabe verwenden wir eine Liste von Zuständen:

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

Und auch eine Liste von Radiosendern, die einige dieser Staaten abdecken:

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")));

Das Buch weist weiter auf den Algorithmus selbst hin und erklärt ihn:

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);

Dynamische Programmierung

Das Buch beschreibt auch Probleme, auf die ein Ansatz namens „dynamische Programmierung“ angewendet wird. Die Aufgabe ist gegeben: Wir haben einen 4-Pfund-Beutel. Sie müssen die profitabelsten Artikel für ein bestimmtes Gewicht finden. Lassen Sie uns zunächst eine Liste der Elemente erstellen:

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));

Nun der Algorithmus selbst:

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));

Es gibt auch eine interessante Aufgabe, die ähnlichsten Wörter zu finden. Interessant, nicht wahr? Weitere Details hier: LongestCommonSubsequence.java

Suchen Sie nach nächsten Nachbarn

Das Buch spricht auch sehr deutlich über den k-Nächste-Nachbarn-Algorithmus: Und die Formel zur Berechnung ist angegeben:

Endeffekt

Das Buch endet mit einem interessanten Abschnitt „Was kommt als Nächstes?“, der einen schnellen Überblick über interessante Algorithmen bietet. Hier finden Sie eine kurze Beschreibung der Bedeutung von Bäumen und anderen Algorithmen. Insgesamt hat mir das Buch gefallen. Es sollte nicht als umfassende Information ernst genommen werden. Sie müssen selbst suchen und verstehen. Aber als einführende Information, um Interesse zu wecken und einen ersten Eindruck zu vermitteln, ist es ganz gut. Ja, der Code im Buch ist in Python geschrieben. Daher sind alle oben genannten Beispiele kompilierbar. Ich hoffe, diese Rezension hilft Ihnen dabei, eine Vorstellung davon zu bekommen, was das Buch enthält und ob es sich lohnt, es zu kaufen.

Zusätzlich

Sie können sich auch die folgenden Ressourcen zu diesem Thema ansehen:

1. EdX – Einführung in die Java-Programmierung: Grundlegende Datenstrukturen und Algorithmen
2. LinkedIn – Einführung in Datenstrukturen und Algorithmen in Java (kostenpflichtig)
3. 27 Websites mit Rätseln, mit denen Sie Ihre Programmierkenntnisse verbessern können
4. Java CodingBat
5. Aufgaben für Programmierer, Antworten auf Aufgaben unterschiedlicher Komplexität

#Wjatscheslaw