Algorytmy grockingowe, czyli bezbolesne wprowadzenie do algorytmów

Recenzja książki „Algorytmy Grockingu”. Trochę osobistej opinii, kilka przykładów. Mam nadzieję, że ta recenzja pomoże Ci zrozumieć, czy chcesz przeczytać tę książkę, czy też nie zajmie ona miejsca na Twojej półce. OSTRZEŻENIE: dużo tekstu)

„Grocking Algorithms”, czyli bezbolesne wprowadzenie do algorytmów

Wstęp

Prawie każdy wakat na poziomie Junior ma wymagania takie jak „znajomość struktur danych i algorytmów”. Dla tych, którzy mają wykształcenie specjalistyczne, algorytmy są uwzględnione w kursie ogólnym i nie powinno być problemów. Ale co, jeśli zabudowa została sprowadzona z innych stepów? Nie pozostaje nic innego jak uczyć się samodzielnie. Na pytanie „kto jest winny” istnieje odpowiedź, ale na pytanie „co robić” należy szukać odpowiedzi. Poszukajmy w książkach. I chcę Ci opowiedzieć o jednym.

Algorytmy Groka

Wśród wszystkich prac natknąłem się na taką książkę jak „Grocking Algorithms”. Więcej dowiesz się tutaj: „ Książka „Growing Algorithms. Ilustrowany przewodnik dla programistów i ciekawskich ”. Książkę zauważyłem dawno temu, ale na ozonie kosztowała 680 rubli. Drogie czy tanie - każdy decyduje sam. Drugą książkę kupuję już na Avito za połowę ceny. Znalazłem go więc w Petersburgu, kupiłem i pogrążyłem się w groku. Tym właśnie postanowiłam się z Wami podzielić. Tak, w książce nie ma kodu Java, ale jest... inny kod, ale o tym później.

Wprowadzenie do algorytmów (sortowanie przez wybór)

Tak więc, w prostej formie narracji, dochodzimy w naszym spektaklu do pierwszego sortowania. To jest sortowanie przez wybór. Jego istota polega na tym, że przechodzimy przez elementy od lewej do prawej (od elementu 0 do ostatniego) i szukamy największego spośród pozostałych elementów. Jeśli go znajdziemy, to zamieniamy element, na którym teraz jesteśmy, z elementem największym. Najprostszy sposób, aby najpierw pomyśleć o tablicy, to: [5, 3, 6, 2, 10]. Weź kartkę papieru, długopis (najprościej i najtaniej) i wyobraź sobie, że mamy lewą ramkę, bieżący indeks (lub prawą ramkę) i indeks elementu minimalnego. I jak z tym pracujemy. Na przykład: Algorytmy są często opisywane w pseudokodzie, na przykład w Wikipedii. Nasz nie jest dokładnie pseudokodem, ale o tym później. Na razie zobaczmy:

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

Teraz przedstawmy to w postaci kodu 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;
            }
        }
}

Jak widać, kod jest prawie taki sam. Pierwszy kod to przykład z książki. Drugie to moje darmowe wykonanie w kodzie Java.

Rekurencja

Następnie dowiadujemy się, że istnieje coś takiego jak rekurencja. Po pierwsze jest problem z rolnikiem, który ma pole o wielkości AxB. Konieczne jest podzielenie tego pola na równe „kwadraty”. A potem wspomniany jest algorytm Euklidesa. Nie podoba mi się to, że nie próbowali napisać jego kodu. Ale algorytm Euklidesa jest prosty i skuteczny: Szczerze mówiąc, w książce pominąłem pewne szczegóły, jak na przykład w tym filmie: „ Informatyka. Teoria algorytmów. Algorytm Euklidesa .” Na przykład, jeśli a jest mniejsze niż b, to podczas pierwszego przebiegu b i a zamienią się miejscami, a za drugim razem większe zostanie podzielone przez mniejsze. Dlatego kolejność argumentów nie jest istotna. Jak zwykle, najpierw możemy „poczuć” algorytm na kartce papieru: Teraz spójrzmy na kod:

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

Napiszmy ten sam kod w Javie. W razie potrzeby możemy skorzystać z kompilatora online :

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

Silnia została również wspomniana na początku książki. Silnia liczby n (n!) jest iloczynem liczb od 1 do n. Czemu to robić? Jest tu jedno praktyczne zastosowanie. Jeśli mamy n obiektów (na przykład n miast), to możemy stworzyć n z nich! Kombinacje. Więcej o rekurencji możesz przeczytać tutaj: „ Rekurencja. Zadania szkoleniowe ”. Porównanie podejść iteracyjnych i rekurencyjnych: „ Rekurencja ”.

Szybkie sortowanie

Sortowanie szybkie jest dość interesującym algorytmem. Książka nie poświęca mu zbyt wiele uwagi. Ponadto kod podawany jest tylko dla najgorszego przypadku, gdy wybrany zostanie pierwszy element. Być może jednak przy pierwszej znajomości ten przykład będzie łatwiejszy do zapamiętania. I lepiej napisać zły szybki sort, niż nie napisać go wcale. Oto przykład z książki:

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)

Wszystko tutaj jest niezwykle proste. Jeśli mamy tablicę zawierającą 0 lub 1 element, nie ma potrzeby jej sortowania. Jeśli jest większy, bierzemy pierwszy element tablicy i uważamy go za „element obrotowy”. Tworzymy 2 nowe tablice – jedna zawiera elementy większe od osi obrotu, a druga zawiera elementy mniejsze. I powtarzamy rekurencyjnie. Nie jest to najlepsza opcja, ale znowu lepiej zapamiętana. Zaimplementujmy ten algorytm w Javie, ale bardziej poprawnie. Pomoże nam w tym materiał z recenzji „ Informatyka w JavaScript: Quicksort ” . A przed napisaniem kodu narysujmy jeszcze raz, żeby „wyczuć” algorytm: Najpierw narysujmy jeszcze raz na kartce papieru, żeby zrozumieć algorytm: Wydaje mi się, że jednym z najniebezpieczniejszych momentów jest całkowite rozwiązanie problemów. Dlatego wdrożenie przeprowadzimy w kilku małych krokach:

• Musimy mieć możliwość zamiany elementów w tablicy:

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




• Potrzebujemy metody, która podzieli tablicę w określonym przedziale na 3 części

  
  

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

  Szczegóły w linku powyżej. Krótko mówiąc, przesuwamy lewy kursor, aż element będzie mniejszy niż oś obrotu. Podobnie przesuń prawy kursor z drugiego końca. I dokonujemy zamiany, jeśli kursory nie pasują. Kontynuujemy, aż kursory się zbiegną. Zwracamy indeks dzielący dalsze przetwarzanie na 2 części.

• Jest separacja, potrzebujemy samego sortowania:

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

  Oznacza to, że jeśli tablica składa się z co najmniej dwóch elementów, to można je już posortować. Najpierw dzielimy całą tablicę na dwie części, elementy mniejsze od osi obrotu i elementy większe. Następnie wykonujemy podobne czynności dla każdej z powstałych części.

  A dla testu:

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

W książce podano, że algorytm ten należy do tzw. algorytmów „dziel i zwyciężaj”, gdy przetwarzany zbiór danych jest każdorazowo dzielony na pół. Złożoność algorytmu: O(nLogn) Wadą (czyli tym, co mi się nie podobało) jest to, że książka mimochodem wspomina o sortowaniu przez scalanie, ale nie podaje żadnego przykładu ani kodu. Więcej szczegółów znajdziesz tutaj: " Informatyka. Algorytmy wyszukiwania i sortowania: Sortowanie przez scalanie ". Dlatego dla zachowania spójności zróbmy to sami. Sam algorytm jest oczywiście z natury prosty i bezpośredni:

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

Wyznaczamy środek i dzielimy tablicę na pół. Dla każdej połowy robimy to samo i tak dalej. Warunek zatrzymania lub przypadek bazowy - musimy mieć więcej niż jeden element, ponieważ nie możemy podzielić jednego elementu na dwa. Teraz musimy wdrożyć fuzję, czyli scalić:

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

Nie ma tu za bardzo co komentować. Z nazw zmiennych printlnwszystko jest jasne. Cóż, aby sprawdzić:

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

Tabele mieszające

Książka porusza także kwestię tablic skrótów. Nie musisz tego implementować samodzielnie, a istota tablic skrótów jest dość prosta. W końcu Java ma również implementację tablic skrótów, java.util.HashTable. Jeśli spojrzymy na urządzenie HashTable, zobaczymy, że wewnątrz znajduje się tablica Entry. Wpis to rekord będący kombinacją Klucz – Wartość. HashTable ma początkowyCapacity - czyli początkowy rozmiar. Oraz LoadFactor – współczynnik obciążenia. Wartość domyślna to 0,75. Liczba ta informuje, przy jakim obciążeniu tablicy (liczba elementów/całkowita ilość) należy zwiększyć rozmiar. W Javie wzrasta 2 razy. Książka wyjaśnia, że ​​tabele skrótów nazywane są tabelami skrótów, ponieważ w oparciu o funkcję skrótu komórka tablicy (koszyk), w której znajduje się plik Entry. Więcej możesz przeczytać także tutaj: Struktury danych na obrazkach. HashMap i LinkedHashMap . Można to też przeczytać w książkach. Na przykład tutaj: „ Podstawy HashTable ”

Wykresy, wyszukiwanie wszerz (wyszukiwanie najkrótszą ścieżką)

Prawdopodobnie jednym z najciekawszych tematów są wykresy. I tutaj, trzeba przyznać, książka poświęca im wiele uwagi. Może dlatego warto przeczytać tę książkę. Chociaż może można było to powiedzieć trochę jaśniej)) Ale mamy Internet i oprócz książki możesz zajrzeć do tej playlisty z teorii dla „tych, którzy pierwszy raz słyszą o wykresach” . ” Cóż, oczywiście, na samym początku książki breadth-first-searchpodany jest algorytm przeszukiwania wszerz, znany również jako BFS. W książce znajduje się następujący wykres: W książce jest napisane, że kolejka nam pomoże. Co więcej, tak, że możemy dodawać elementy na końcu i przetwarzać kolejkę od początku. Takie kolejki nazywane są kolejkami dwukierunkowymi lub w języku angielskim Deque. Książka sugeruje użycie struktury danych - tablicy mieszającej. Aby powiązać nazwę i sąsiadów. W przypadku ponumerowanych wierzchołków możesz po prostu użyć tablicy. To przechowywanie wierzchołków nazywa się „Listą sąsiednich wierzchołków”, o czym nie wspomina się w książce. To dla nich minus. Zaimplementujmy to w Javie:

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

Teraz samo wyszukiwanie, zbudowane na tych danych:

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

Jak widać nic skomplikowanego. Jeśli porównać go z kodem z książki, jest prawie taki sam.

Wykresy, algorytm Dijkstry

Mając mniej lub bardziej zrozumiałe BFS, autor książki zaprasza nas do zrozumienia algorytmu Daysktra i wykresów ważonych. Jako rozwiązanie proponuje się następujący wykres: Najpierw musimy zrozumieć, jak przedstawić nasze wykresy. Moglibyśmy przedstawić to jako macierz. Pomoże nam w tym artykuł o Habré: Algorytm Dijkstry. Znajdowanie optymalnych tras na wykresie . Skorzystajmy z macierzy sąsiedztwa:

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

A teraz sama logika:

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

Książka opisuje to krok po kroku. Jeśli dodasz artykuł o Habré w Internecie + spójrz na kod, możesz go zapamiętać. Analiza krok po kroku wydała mi się nieco zagmatwana. Ale już samo to, że jest krok po kroku, jest zaletą. Ogólnie ok, chociaż mogło być lepiej)

Chciwe algorytmy

Kolejna część poświęcona jest „algorytmom zachłannym”. Ta sekcja jest interesująca, ponieważ używa zestawów (java.util.Set). Wreszcie możemy zobaczyć, dlaczego może być to potrzebne. Jako danych wejściowych używamy listy stanów:

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

A także lista stacji radiowych obsługujących niektóre z tych stanów:

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

Książka dalej wskazuje i wyjaśnia sam algorytm:

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

Programowanie dynamiczne

W książce opisano także problemy, do których stosuje się podejście zwane „programowaniem dynamicznym”. Podano zadanie: Mamy worek 4-funtowy. Musisz znaleźć najbardziej opłacalne przedmioty dla danej wagi. Na początek zróbmy listę rzeczy:

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

Teraz sam algorytm:

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

Ciekawym zadaniem jest także znalezienie najbardziej podobnych słów. Ciekawe, prawda? Więcej szczegółów tutaj: LongestCommonSubsequence.java

Wyszukaj najbliższych sąsiadów

Książka również bardzo wyraźnie mówi o algorytmie k-najbliższych sąsiadów: Podano wzór do obliczeń:

Konkluzja

Książkę kończy interesująca sekcja „Co dalej?”, która zawiera szybki przegląd interesujących algorytmów. Oto krótki opis znaczenia drzew i innych algorytmów. Ogólnie książka mi się podobała. Nie należy go traktować poważnie jako pewnego rodzaju wyczerpującej informacji. Będziesz musiał sam poszukać i zrozumieć. Ale jako informacje wprowadzające, które mogą zainteresować i dać wstępny pomysł, jest całkiem niezłe. Tak, kod w książce jest napisany w Pythonie. Zatem wszystkie powyższe przykłady da się skompilować). Mam nadzieję, że ta recenzja pomoże Wam zorientować się, co zawiera dana książka i czy warto ją kupić.

Dodatkowo

Możesz także zapoznać się z następującymi zasobami na ten temat:

1. EdX - Wprowadzenie do programowania w języku Java: podstawowe struktury danych i algorytmy
2. LinkedIn – Wprowadzenie do struktur danych i algorytmów w Javie (płatne)
3. 27 stron z łamigłówkami, które pozwolą Ci udoskonalić Twoje umiejętności programowania
4. Kodowanie JavaBat
5. Zadania dla programistów, odpowiedzi na zadania o różnym stopniu złożoności

#Wiaczesław