Algorithmes Grocking ou une introduction indolore aux algorithmes

Critique du livre "Grocking Algorithms". Un petit avis personnel, quelques exemples. J'espère que cette critique vous aidera à comprendre si vous souhaitez lire ce livre ou s'il ne prendra pas sa place sur votre étagère. ATTENTION : Beaucoup de texte)

« Growing Algorithms » ou une introduction indolore aux algorithmes

Introduction

Presque tous les postes vacants au niveau junior comportent des exigences telles que « la connaissance des structures de données et des algorithmes ». Pour ceux qui ont une formation spécialisée, les algorithmes sont inclus dans le cours général et il ne devrait y avoir aucun problème. Et si le développement venait d’autres steppes ? Il ne reste plus qu'à apprendre par soi-même. Il y a une réponse à la question « qui est à blâmer », mais à la question « que faire », il faut chercher la réponse. Regardons dans les livres. Et je veux vous en parler d'un.

Algorithmes de Grok

Parmi tous les ouvrages, je suis tombé sur un livre tel que « Grocking Algorithms ». Vous pouvez en savoir plus ici : " Le livre " Growing Algorithms. Un guide illustré pour les programmeurs et les curieux ". J'ai remarqué le livre il y a longtemps, mais sur l'ozone, il coûtait 680 roubles. Cher ou bon marché - chacun décide pour lui-même. J'achète déjà le deuxième livre sur Avito pour la moitié du prix. Alors je l'ai trouvé à Saint-Pétersbourg, je l'ai acheté et je suis allé chercher. C'est ce que j'ai décidé de partager avec vous. Oui, il n'y a pas de code Java dans le livre, mais il y a... un autre code, mais nous en reparlerons plus tard.

Introduction aux algorithmes (tri par sélection)

Ainsi, dans une forme de narration simple, nous arrivons au premier tri de notre performance. Il s’agit du tri par sélection. Son essence est que nous parcourons les éléments de gauche à droite (de 0 élément au dernier) et recherchons le plus grand parmi les éléments restants. Si nous le trouvons, alors nous échangeons l'élément sur lequel nous nous trouvons actuellement et l'élément le plus grand. La façon la plus simple de penser d’abord à un tableau est : [5, 3, 6, 2, 10]. Prenez un morceau de papier, un stylo (le moyen le plus simple et le moins coûteux) et imaginez comment nous avons une bordure gauche (gauche), un index actuel (ou bordure droite), il y a un index de l'élément minimum. Et comment nous travaillons avec. Par exemple: Les algorithmes sont souvent décrits en pseudocode, par exemple sur Wikipédia. Le nôtre n’est pas exactement un pseudocode, mais nous y reviendrons plus tard. Pour l'instant, voyons :

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

Présentons-le maintenant sous forme de code 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;
            }
        }
}

Comme vous pouvez le constater, le code est presque le même. Le premier code est un exemple tiré du livre. La seconde est mon exécution gratuite en code Java.

Récursion

Ensuite, on nous dit qu’il existe une récursivité. Tout d’abord, il y a le problème d’un agriculteur qui possède un champ de taille AxB. Il est nécessaire de diviser ce champ en « carrés » égaux. Et puis après cela, l’algorithme d’Euclide est mentionné. Ce que je n'aime pas, c'est qu'ils n'ont pas essayé d'écrire son code. Mais l’algorithme d’Euclide est simple et efficace : Pour être honnête, j'ai raté certains détails dans le livre, comme dans cette vidéo : « Informatique. Théorie des algorithmes. L'algorithme d'Euclide ." Par exemple, si a est inférieur à b, alors lors de la première exécution, b et a changeront de place et la deuxième fois, le plus grand sera divisé par le plus petit. L’ordre des arguments n’a donc pas d’importance. Comme d’habitude, nous pouvons d’abord « sentir » l’algorithme sur un morceau de papier : Regardons maintenant le code :

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

Écrivons le même code en Java. Si on le souhaite, on peut utiliser le compilateur en ligne :

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

Factorial a également été mentionné au début du livre. La factorielle d'un nombre n (n!) est le produit des nombres de 1 à n. Pourquoi faire ceci? Il y a ici une application pratique. Si nous avons n objets (par exemple n villes), alors nous pouvons en créer n ! Combinaisons. Vous pouvez en savoir plus sur la récursivité ici : " Récursion. Tâches de formation . " Comparaison des approches itératives et récursives : " Récursion ".

Tri rapide

Le tri rapide est un algorithme plutôt intéressant. Le livre ne lui prête pas beaucoup d'attention. De plus, le code n'est donné que pour le pire des cas, lorsque le premier élément est sélectionné. Cependant, cet exemple sera peut-être plus facile à retenir pour une première connaissance. Et il vaut mieux écrire un mauvais tri rapide que de ne pas en écrire du tout. Voici un exemple tiré du livre :

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)

Tout ici est super simple. Si nous avons un tableau de 0 ou 1 élément, il n’est pas nécessaire de le trier. S'il est supérieur, nous prenons le premier élément du tableau et le considérons comme « l'élément pivot ». Nous créons 2 nouveaux tableaux : l'un contient des éléments plus grands que le pivot et le second contient des éléments plus petits. Et nous répétons récursivement. Ce n’est pas la meilleure option, mais encore une fois, on s’en souvient mieux. Implémentons cet algorithme en Java, mais plus correctement. Le matériel de la revue « Computer Science in JavaScript: Quicksort » nous y aidera . Et avant d’écrire le code, dessinons à nouveau pour « ressentir » l’algorithme : Tout d’abord, dessinons à nouveau sur une feuille de papier pour comprendre l’algorithme : Il me semble que l’un des moments les plus dangereux est celui de résoudre complètement les problèmes. Par conséquent, nous réaliserons la mise en œuvre en plusieurs petites étapes :

• Nous devons pouvoir échanger des éléments dans un tableau :

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




• Nous avons besoin d'une méthode qui divise le tableau dans l'intervalle spécifié en 3 parties

  
  

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

  Détails sur le lien ci-dessus. Bref, on déplace le curseur gauche jusqu'à ce que l'élément soit inférieur au pivot. De même, déplacez le curseur droit depuis l’autre extrémité. Et on fait un échange si les curseurs ne correspondent pas. Nous continuons jusqu'à ce que les curseurs convergent. Nous renvoyons un index qui divise le traitement ultérieur en 2 parties.

• Il y a une séparation, nous avons besoin du tri lui-même :

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

  Autrement dit, si le tableau se compose d'au moins deux éléments, ils peuvent déjà être triés. Tout d’abord, nous divisons l’ensemble du tableau en deux parties, les éléments plus petits que le pivot et les éléments plus grands. Ensuite, nous effectuons des actions similaires pour chacune des pièces résultantes.

  Et pour le 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));
  }

Le livre indique que cet algorithme appartient aux algorithmes dits « Diviser pour régner », lorsque l’ensemble de données traitées est divisé en deux à chaque fois. Complexité de l'algorithme : O(nLogn) Ce qui est mauvais (c'est-à-dire ce que je n'ai pas aimé), c'est que le livre mentionne le tri par fusion au passage, mais ne fournit aucun exemple ni code. Plus de détails peuvent être trouvés ici : " Informatique. Algorithmes de recherche et de tri : tri par fusion ". Par conséquent, par souci de cohérence, faisons-le nous-mêmes. L’algorithme lui-même, bien entendu, est intrinsèquement simple et direct :

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

Nous déterminons le milieu et divisons le tableau en deux. Pour chaque moitié, nous faisons la même chose et ainsi de suite. Condition d'arrêt ou cas de base : nous devons avoir plus d'un élément, car nous ne pouvons pas diviser un élément en deux. Nous devons maintenant mettre en œuvre la fusion, c'est-à-dire fusionner :

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

Il n'y a pas grand chose à commenter ici. D'après les noms des variables, printlntout est clair. Bon, pour vérifier :

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

Tables de hachage

Le livre aborde également les tables de hachage. Vous n’êtes pas obligé de l’implémenter vous-même et l’essence des tables de hachage est assez simple. Après tout, Java dispose également d'une implémentation de tables de hachage, java.util.HashTable. Si nous regardons le périphérique HashTable, nous verrons que le tableau Entry réside à l'intérieur. L’entrée est un enregistrement qui est une combinaison de clé – valeur. HashTable a initialCapacity, c'est-à-dire la taille initiale. Et loadFactor – facteur de charge. La valeur par défaut est 0,75. Ce nombre vous indique à quelle charge du tableau (nombre d'éléments/nombre total) la taille doit être augmentée. En Java, cela augmente de 2 fois. Le livre explique que les tables de hachage sont appelées tables de hachage car, en fonction de la fonction de hachage, la cellule du tableau (panier) dans laquelle le fichier Entry. Vous pouvez également en savoir plus ici : Structures de données en images. HashMap et LinkedHashMap . Vous pouvez également le lire dans des livres. Par exemple ici : " Bases de HashTable »

Graphiques, recherche en largeur d'abord (recherche du chemin le plus court)

Les graphiques sont probablement l’un des sujets les plus intéressants. Et ici, pour être honnête, le livre leur accorde beaucoup d’attention. C'est peut-être pour cela que cela vaut la peine de lire ce livre. Même si, peut-être, cela aurait pu être dit un peu plus clairement)) Mais nous avons Internet et en plus du livre, vous pouvez consulter cette playlist sur la théorie pour « ceux qui entendent parler de graphiques pour la première fois ». » Eh bien, naturellement, au tout début du livre, l'algorithme de recherche en largeur d'abord, breadth-first-searchégalement connu sous le nom de BFS, est présenté. Le livre contient le graphique suivant : Le livre déclare qu'une file d'attente nous aidera. De plus, de telle sorte que nous puissions ajouter des éléments à la fin et traiter la file d'attente depuis le début. De telles files d'attente sont appelées files d'attente bidirectionnelles ou Deque en anglais. Le livre suggère d'utiliser une structure de données - une table de hachage. Pour corréler le nom et les voisins. Avec des sommets numérotés, vous pouvez simplement utiliser un tableau. Ce stockage de sommets est appelé « Liste des sommets adjacents », ce qui n'est pas mentionné dans le livre. C'est un inconvénient pour eux. Implémentons ceci en 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;
}

Maintenant, la recherche elle-même, construite sur ces données :

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

Comme vous pouvez le constater, rien de compliqué. Si vous le comparez avec le code du livre, c’est presque pareil.

Graphiques, algorithme de Dijkstra

Ayant plus ou moins compris BFS, l'auteur du livre nous invite à comprendre l'algorithme Daysktra et les graphiques pondérés. Le graphique suivant est proposé pour la solution : Tout d’abord, nous devons comprendre comment représenter nos graphiques. Nous pourrions le représenter comme une matrice. Un article sur Habré nous aidera ici : l'algorithme de Dijkstra. Trouver des itinéraires optimaux sur un graphique . Utilisons la matrice de contiguïté :

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

Et maintenant la logique elle-même :

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

Le livre le décompose étape par étape. Si vous ajoutez un article sur Habré sur Internet + regardez le code, vous pouvez vous en souvenir. J'ai trouvé l'analyse étape par étape un peu encombrée. Mais pour la nature étape par étape elle-même, c’est un plus. Dans l'ensemble, ok, même si ça aurait pu être mieux)

Algorithmes gourmands

La section suivante est consacrée aux « algorithmes gloutons ». Cette section est intéressante car elle utilise des ensembles (java.util.Set). Enfin, nous pouvons voir pourquoi cela pourrait être nécessaire. Nous utilisons une liste d'états en entrée :

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

Et aussi une liste de stations de radio couvrant certains de ces états :

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

Le livre continue en soulignant et en expliquant l'algorithme lui-même :

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

Programmation dynamique

Le livre décrit également des problèmes auxquels une approche appelée « programmation dynamique » est appliquée. La tâche est confiée : Nous avons un sac de 4 livres. Il faut trouver les articles les plus rentables pour un poids donné. Tout d'abord, faisons une liste d'éléments :

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

Maintenant l'algorithme lui-même :

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

Il existe également une tâche intéressante consistant à trouver les mots les plus similaires. Intéressant, n'est-ce pas ? Plus de détails ici : LongestCommonSubsequence.java

Rechercher les voisins les plus proches

Le livre parle également très clairement de l'algorithme des k-voisins les plus proches : Et la formule de calcul est donnée :

Conclusion

Le livre se termine par une intéressante section « Quelle est la prochaine étape ? », qui donne un aperçu rapide des algorithmes intéressants. Voici une brève description de la signification des arbres et d'autres algorithmes. Dans l'ensemble, j'ai aimé le livre. Il ne faut pas le prendre au sérieux comme une sorte d’information complète. Vous devrez chercher et comprendre par vous-même. Mais comme information introductive pour intéresser et donner une première idée, c’est plutôt bien. Oui, le code du livre est écrit en Python. Donc tous les exemples ci-dessus sont compilables) J'espère que cette critique vous aidera à avoir une idée de ce que contient le livre et s'il vaut la peine d'être acheté.

En plus

Vous pouvez également consulter les ressources suivantes sur ce sujet :

1. EdX - Introduction à la programmation Java : structures de données et algorithmes fondamentaux
2. LinkedIn - Introduction aux structures de données et aux algorithmes en Java (payant)
3. 27 sites avec des énigmes pour affiner vos compétences en programmation
4. Java CodageBat
5. Tâches pour les programmeurs, réponses à des tâches de complexité variable

#Viacheslav