JavaRush /Java Blog /Random-IT /Algoritmi di Grocking o un'introduzione indolore agli alg...

Livello 3

28 febbraio 2021
40 views
0 comments

Algoritmi di Grocking o un'introduzione indolore agli algoritmi

Recensione del libro "Grocking Algorithms". Una piccola opinione personale, qualche esempio. Spero che questa recensione ti aiuti a capire se vuoi leggere questo libro o se non prenderà il suo posto sul tuo scaffale. ATTENZIONE: molto testo)

"Algoritmi in crescita" o un'introduzione indolore agli algoritmi

introduzione

Quasi tutti i posti vacanti di livello Junior hanno requisiti come "conoscenza di strutture dati e algoritmi". Per chi ha una formazione specialistica gli algoritmi sono inclusi nel corso generale e non dovrebbero esserci problemi. Ma cosa accadrebbe se lo sviluppo provenisse da altre steppe? Non resta che imparare da solo. Alla domanda “di chi è la colpa” c’è una risposta, ma alla domanda “cosa fare” la risposta va cercata. Diamo un'occhiata ai libri. E voglio parlarvene di uno.

Algoritmi di Grok

Tra tutti i lavori, mi sono imbattuto in un libro come "Grocking Algorithms". Puoi saperne di più qui: " Il libro "Algoritmi in crescita. Una guida illustrata per programmatori e curiosi ". Ho notato il libro molto tempo fa, ma con l'ozono costava 680 rubli. Costoso o economico: ognuno decide da solo. Sto già acquistando il secondo libro su Avito a metà prezzo. Così l'ho trovato a San Pietroburgo, l'ho comprato e sono andato a grokkare. Questo è ciò che ho deciso di condividere con te. Sì, nel libro non c'è il codice Java, ma c'è... altro codice, ma ne parleremo più avanti.

Introduzione agli algoritmi (ordinamento di selezione)

Quindi, in una forma facile di narrazione, raggiungiamo il primo ordinamento della nostra performance. Questo è l'ordinamento della selezione. La sua essenza è che esaminiamo gli elementi da sinistra a destra (dall'elemento 0 all'ultimo) e cerchiamo il più grande tra gli elementi rimanenti. Se lo troviamo, scambiamo l'elemento su cui ci troviamo ora con l'elemento più grande. Il modo più semplice per pensare innanzitutto a un array è: [5, 3, 6, 2, 10]. Prendiamo un pezzo di carta, una penna (il modo più semplice ed economico) e immagina come abbiamo un bordo sinistro (sinistra), un indice corrente (o bordo destro), c'è un indice dell'elemento minimo. E come lo utilizziamo. Per esempio:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 2

Gli algoritmi sono spesso descritti in pseudocodice, ad esempio su Wikipedia. Il nostro non è esattamente uno pseudocodice, ma ne parleremo più avanti. Per ora vediamo:


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

Ora presentiamolo sotto forma di codice 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;
            }
        }
}

Come puoi vedere, il codice è quasi lo stesso. Il primo codice è un esempio tratto dal libro. Il secondo è la mia esecuzione gratuita in codice Java.

Ricorsione

Successivamente ci viene detto che esiste qualcosa come la ricorsione. Innanzitutto, c’è il problema di un agricoltore che ha un campo di dimensioni AxB. È necessario dividere questo campo in “quadrati” uguali. E poi viene menzionato l'algoritmo di Euclide. Quello che non mi piace è che non abbiano provato a scriverne il codice. Ma l’algoritmo di Euclide è semplice ed efficace:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 3

A dire il vero, nel libro mi sono persi alcuni dettagli, come in questo video: “ Informatica. Teoria degli algoritmi. L'algoritmo di Euclide ." Ad esempio, se a è inferiore a b, durante la prima esecuzione b e a si scambieranno di posto e la seconda volta quello più grande verrà diviso per quello più piccolo. Pertanto, l’ordine degli argomenti non è importante. Come al solito, prima possiamo “sentire” l’algoritmo su un pezzo di carta:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 4

Ora diamo un'occhiata al codice:


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

Scriviamo lo stesso codice in Java. Se lo si desidera, possiamo utilizzare il compilatore online :

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

Anche il fattoriale è stato menzionato all'inizio del libro. Il fattoriale di un numero n (n!) è il prodotto dei numeri da 1 a n. Perché farlo? C'è un'applicazione pratica qui. Se abbiamo n oggetti (ad esempio n città), allora possiamo crearne n! Combinazioni. Puoi leggere ulteriori informazioni sulla ricorsione qui: " Ricorsione. Attività di formazione ". Confronto tra approcci iterativi e ricorsivi: " La ricorsione ".

Ordinamento rapido

L'ordinamento rapido è un algoritmo piuttosto interessante. Il libro non gli presta molta attenzione. Inoltre il codice viene fornito solo nel caso peggiore, quando viene selezionato il primo elemento. Tuttavia, forse per una prima conoscenza questo esempio sarà più facile da ricordare. Ed è meglio scrivere un cattivo quicksort piuttosto che non scriverne affatto. Ecco un esempio dal libro:


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)

Tutto qui è semplicissimo. Se abbiamo un array di 0 o 1 elemento, non è necessario ordinarlo. Se è maggiore, prendiamo il primo elemento dell'array e lo consideriamo “elemento pivot”. Creiamo 2 nuovi array: uno contiene elementi più grandi del pivot e il secondo contiene elementi più piccoli. E lo ripetiamo ricorsivamente. Non è l'opzione migliore, ma ancora una volta, ricordata meglio. Implementiamo questo algoritmo in Java, ma più correttamente. In questo ci aiuterà il materiale della recensione " Informatica in JavaScript: Quicksort " . E prima di scrivere il codice, disegniamo di nuovo per “sentire” l'algoritmo: Per prima cosa, disegniamo di nuovo su un pezzo di carta per capire l'algoritmo:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 5

Mi sembra che uno dei momenti più pericolosi sia risolvere completamente i problemi. Pertanto, eseguiremo l’implementazione in diversi piccoli passaggi:

Dobbiamo essere in grado di scambiare elementi in un array:

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

Abbiamo bisogno di un metodo che divida l'array nell'intervallo specificato in 3 parti

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

Dettagli al link sopra. In breve spostiamo il cursore sinistro finché l'elemento non risulta inferiore al pivot. Allo stesso modo, sposta il cursore destro dall'altra estremità. E facciamo uno scambio se i cursori non corrispondono. Continuiamo finché i cursori non convergono. Restituiamo un indice che divide l'ulteriore elaborazione in 2 parti.

C'è una separazione, abbiamo bisogno dell'ordinamento stesso:

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

Cioè, se l'array è composto da almeno due elementi, è già possibile ordinarli. Per prima cosa dividiamo l'intero array in due parti, elementi più piccoli del pivot ed elementi più grandi. Quindi eseguiamo azioni simili per ciascuna delle parti risultanti.

E per la prova:

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

Nel libro si afferma che questo algoritmo appartiene ai cosiddetti algoritmi “Divide and Conquer”, quando il set di dati elaborato viene diviso a metà ogni volta. Complessità dell'algoritmo: O(nLogn)

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 6

Ciò che è negativo (ovvero ciò che non mi è piaciuto) è che il libro menziona di sfuggita il merge sort, ma non fornisce alcun esempio o codice. Maggiori dettagli possono essere trovati qui: " Informatica. Algoritmi di ricerca e ordinamento: Merge sort ". Pertanto, per motivi di coerenza, facciamolo da soli. L’algoritmo stesso, ovviamente, è intrinsecamente semplice e diretto:

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

Determiniamo il centro e dividiamo l'array a metà. Per ogni metà facciamo lo stesso e così via. Condizione di arresto o caso base: dobbiamo avere più di un elemento, poiché non possiamo dividere un elemento in due. Ora dobbiamo implementare la fusione, ovvero unire:

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

Non c'è molto da commentare qui. Dai nomi delle variabili printlntutto è chiaro. Bene, per verificare:

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

Tabelle hash

Il libro tocca anche le tabelle hash. Non è necessario implementarlo da soli e l'essenza delle tabelle hash è abbastanza semplice. Dopotutto, Java ha anche un'implementazione di tabelle hash, java.util.HashTable. Se guardiamo il dispositivo HashTable, vedremo che al suo interno risiede l'array Entry. La voce è un record che è una combinazione di Chiave – Valore. HashTable ha la capacità iniziale, ovvero la dimensione iniziale. E loadFactor – fattore di carico. L'impostazione predefinita è 0,75. Questo numero indica a quale carico dell'array (numero di elementi/quantità totale) è necessario aumentare la dimensione. In Java aumenta di 2 volte. Il libro spiega che le tabelle Hash sono chiamate tabelle hash perché basate sulla funzione hash, la cella dell'array (cestino) in cui si trova il file Entry. Puoi anche leggere di più qui: Strutture dati nelle immagini. HashMap e LinkedHashMap . Puoi leggerlo anche nei libri. Ad esempio qui: " Nozioni di base su HashTable "

Grafici, ricerca prima in ampiezza (ricerca del percorso più breve)

Probabilmente uno degli argomenti più interessanti sono i grafici. E qui, a onor del vero, il libro presta molta attenzione a loro. Forse è per questo che vale la pena leggere questo libro. Anche se, forse, si sarebbe potuto dirlo in modo un po' più chiaro)) Ma abbiamo Internet e oltre al libro, puoi guardare questa playlist sulla teoria per “chi sente parlare di grafici per la prima volta . " Ebbene, naturalmente, all'inizio del libro breadth-first-searchviene fornito l'algoritmo di ricerca in ampiezza, noto anche come BFS. Il libro contiene il seguente grafico:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 7

Il libro afferma che la coda ci aiuterà. Inoltre, in modo tale da poter aggiungere elementi alla fine ed elaborare la coda dall'inizio. Tali code sono chiamate code bidirezionali o Deque in inglese. Il libro suggerisce di utilizzare una struttura dati: una tabella hash. Per correlare il nome e i vicini. Con i vertici numerati, puoi semplicemente utilizzare un array. Questa memorizzazione di vertici è chiamata "Lista di vertici adiacenti", che non è menzionata nel libro. Questo è un aspetto negativo per loro. Implementiamolo in 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;
}

Ora la ricerca stessa, basata su questi dati:

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

Come puoi vedere, niente di complicato. Se lo confronti con il codice del libro, è quasi lo stesso.

Grafici, algoritmo di Dijkstra

Avendo più o meno compreso BFS, l'autore del libro ci invita a comprendere l'algoritmo Daysktra e i grafici ponderati. Per la soluzione si propone il seguente grafico:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 8

Per prima cosa dobbiamo capire come rappresentare i nostri grafici. Potremmo rappresentarlo come una matrice. Un articolo su Habré ci aiuterà qui: l'algoritmo di Dijkstra. Trovare percorsi ottimali su un grafico . Usiamo la matrice di adiacenza:

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

E ora la logica stessa:

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

Il libro lo analizza passo dopo passo. Se aggiungi un articolo su Habré su Internet + guarda il codice, puoi ricordarlo. Ho trovato l'analisi passo passo un po' confusa. Ma per la natura stessa del passo dopo passo è un vantaggio. Nel complesso, ok, anche se avrebbe potuto essere migliore)

Algoritmi golosi

La sezione successiva è dedicata agli “algoritmi golosi”. Questa sezione è interessante perché utilizza i set (java.util.Set). Finalmente possiamo capire perché potrebbe essere necessario. Usiamo un elenco di stati come input:

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

E anche un elenco di stazioni radio che coprono alcuni di questi stati:

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

Il libro prosegue sottolineando e spiegando l'algoritmo stesso:

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

Programmazione dinamica

Nel libro vengono inoltre descritti i problemi ai quali viene applicato un approccio chiamato “programmazione dinamica”. Il compito è assegnato:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 9

Abbiamo un bagaglio da 4 libbre. Devi trovare gli articoli più redditizi per un determinato peso. Innanzitutto, facciamo un elenco di elementi:

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

Ora l'algoritmo stesso:

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

C'è anche un compito interessante per trovare le parole più simili. Interessante, vero? Maggiori dettagli qui: LongestCommonSubsequence.java

Cerca i vicini più vicini

Il libro parla anche molto chiaramente dell'algoritmo dei k-vicini più vicini:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 10

E viene fornita la formula per il calcolo:

"Algoritmi grocking" o un'introduzione indolore agli algoritmi - 11

Linea di fondo

Il libro termina con un'interessante sezione "Cosa c'è dopo?", che fornisce una rapida panoramica di algoritmi interessanti. Ecco una breve descrizione del significato degli alberi e di altri algoritmi. Nel complesso, il libro mi è piaciuto. Non dovrebbe essere preso sul serio come una sorta di informazione completa. Dovrai cercare e capire da solo. Ma come informazione introduttiva per interessare e dare un’idea iniziale, è abbastanza buona. Sì, il codice nel libro è scritto in Python. Quindi tutti gli esempi sopra riportati sono compilabili) Spero che questa recensione ti aiuti a farti un'idea di cosa contiene il libro e se vale la pena acquistarlo.