Grocking algorithm o isang walang sakit na pagpapakilala sa mga algorithm

Pagsusuri ng aklat na "Grocking Algorithms". Isang maliit na personal na opinyon, ilang mga halimbawa. Umaasa ako na ang pagsusuri na ito ay makakatulong sa iyo na maunawaan kung gusto mong basahin ang aklat na ito o kung hindi ito gagana sa iyong istante. BABALA: Maraming text)

"Growing Algorithms" o isang Walang Sakit na Panimula sa Algorithms

Panimula

Halos anumang bakante sa antas ng Junior ay may mga kinakailangan tulad ng "kaalaman sa mga istruktura at algorithm ng data." Para sa mga may espesyal na edukasyon, ang mga algorithm ay kasama sa pangkalahatang kurso at dapat walang mga problema. Ngunit paano kung ang pag-unlad ay dinala mula sa iba pang mga steppes? Ang natitira na lang ay matuto nang mag-isa. May sagot sa tanong na "sino ang dapat sisihin", ngunit sa tanong na "ano ang gagawin" ang sagot ay dapat hanapin. Tingnan natin sa mga libro. At gusto kong sabihin sa iyo ang tungkol sa isa.

Mga algorithm ng Grok

Sa lahat ng mga gawa, nakita ko ang isang libro tulad ng "Grocking Algorithms". Maaari mong malaman ang higit pa dito: " Ang aklat na "Growing Algorithms. Isang may larawang gabay para sa mga programmer at mga mausisa ." Napansin ko ang libro ng matagal na ang nakalipas, ngunit sa ozone nagkakahalaga ito ng 680 rubles. Mahal o mura - lahat ay nagpapasya para sa kanyang sarili. Bumibili na ako ng pangalawang libro sa Avito sa kalahati ng presyo. Kaya natagpuan ko ito sa St. Petersburg, binili ko ito, at nag-grokking. Na kung ano ang napagpasyahan kong ibahagi sa iyo. Oo, walang Java code sa aklat, ngunit mayroong... ibang code, ngunit higit pa tungkol doon sa ibang pagkakataon.

Panimula sa Algorithms (Selection Sort)

Kaya, sa isang madaling paraan ng pagsasalaysay, naabot namin ang unang pag-uuri sa aming pagganap. Ito ay Selection Sort. Ang kakanyahan nito ay dumaan tayo sa mga elemento mula kaliwa hanggang kanan (mula 0 elemento hanggang sa huli), at hanapin ang pinakamalaki sa mga natitirang elemento. Kung nahanap natin ito, pagkatapos ay pinapalitan natin ang elemento kung saan tayo ngayon at ang pinakamalaking elemento. Ang pinakasimpleng paraan para mag-isip muna ng array ay: [5, 3, 6, 2, 10]. Kumuha ng isang piraso ng papel, isang panulat (ang pinakasimpleng at pinakamurang paraan) at isipin kung paano tayo may kaliwang hangganan (kaliwa), isang kasalukuyang index (o kanang hangganan), mayroong isang index ng pinakamababang elemento. At kung paano namin ito ginagawa. Halimbawa: Ang mga algorithm ay madalas na inilarawan sa pseudocode, halimbawa, sa Wikipedia. Ang sa amin ay hindi eksaktong pseudocode, ngunit higit pa sa susunod. Sa ngayon tingnan natin:

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

Ngayon, ipakita natin ito sa anyo ng Java code:

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

Tulad ng nakikita mo, ang code ay halos pareho. Ang unang code ay isang halimbawa mula sa aklat. Ang pangalawa ay ang aking libreng pagpapatupad sa Java code.

Recursion

Susunod na sinabi sa amin na mayroong isang bagay tulad ng recursion. Una sa lahat, may problema tungkol sa isang magsasaka na may larangan ng laki ng AxB. Kinakailangan na hatiin ang patlang na ito sa pantay na "mga parisukat". At pagkatapos nito ay binanggit ang Euclid Algorithm. Ang hindi ko gusto ay hindi nila sinubukang isulat ang code nito. Ngunit ang Euclid algorithm ay simple at epektibo: Sa totoo lang, nakaligtaan ko ang ilang detalye sa libro, tulad ng sa video na ito: “ Informatics. Teorya ng mga algorithm. algorithm ni Euclid ." Halimbawa, kung ang a ay mas mababa sa b, pagkatapos ay sa unang pagtakbo b at a ay magbabago ng mga lugar at sa pangalawang pagkakataon ang mas malaki ay hahatiin ng mas maliit. Samakatuwid, ang pagkakasunud-sunod ng mga argumento ay hindi mahalaga. Gaya ng dati, maaari muna nating "maramdaman" ang algorithm sa isang piraso ng papel: Ngayon tingnan natin ang code:

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

Isulat natin ang parehong code sa Java. Kung nais, maaari naming gamitin ang online compiler :

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

Nabanggit din ang factorial sa simula ng libro. Ang factorial ng isang numero n (n!) ay ang produkto ng mga numero mula 1 hanggang n. Bakit gagawin ito? Mayroong isang praktikal na aplikasyon dito. Kung mayroon tayong n mga bagay (halimbawa, n mga lungsod), maaari tayong gumawa ng n sa kanila! Mga kumbinasyon. Maaari kang magbasa ng higit pa tungkol sa recursion dito: " Recursion. Mga gawain sa pagsasanay ." Paghahambing ng umuulit at recursive approach: " Recursion ".

Mabilis na pag-uuri

Ang mabilis na pag-uuri ay isang medyo kawili-wiling algorithm. Hindi siya masyadong pinapansin ng libro. Bukod dito, ibinibigay lamang ang code para sa pinakamasamang kaso, kapag napili ang unang elemento. Gayunpaman, marahil para sa isang unang kakilala ang halimbawang ito ay mas madaling matandaan. At mas mainam na magsulat ng isang masamang quicksort kaysa hindi magsulat ng isa. Narito ang isang halimbawa mula sa aklat:

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)

Lahat dito ay sobrang simple. Kung mayroon kaming isang array ng 0 o 1 elemento, hindi na kailangang ayusin ito. Kung ito ay mas malaki, kukunin namin ang unang elemento ng array at isaalang-alang itong "pivot element". Gumagawa kami ng 2 bagong array - ang isa ay naglalaman ng mga elementong mas malaki kaysa sa pivot, at ang pangalawa ay naglalaman ng mga elementong mas maliit. At inuulit namin nang paulit-ulit. Hindi ang pinakamahusay na pagpipilian, ngunit muli, mas mahusay na maalala. Ipatupad natin ang algorithm na ito sa Java, ngunit mas tama. Ang materyal mula sa pagsusuri na " Computer Science sa JavaScript: Quicksort " ay makakatulong sa amin dito . At bago isulat ang code, gumuhit tayo muli upang "maramdaman" ang algorithm: Una, gumuhit tayo muli sa isang piraso ng papel upang maunawaan ang algorithm: Para sa akin, ang isa sa mga pinaka-mapanganib na sandali ay ang ganap na paglutas ng mga problema. Samakatuwid, isasagawa namin ang pagpapatupad sa ilang maliliit na hakbang:

• Kailangan nating makapagpalit ng mga elemento sa isang array:

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




• Kailangan namin ng isang paraan na naghahati sa array sa tinukoy na agwat sa 3 bahagi

  
  

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

  Mga detalye sa link sa itaas. Sa madaling salita, inililipat namin ang kaliwang cursor hanggang ang elemento ay mas mababa sa pivot. Katulad nito, ilipat ang kanang cursor mula sa kabilang dulo. At gagawa kami ng swap kung hindi magkatugma ang mga cursor. Nagpapatuloy kami hanggang sa magtagpo ang mga cursor. Nagbabalik kami ng index na naghahati sa karagdagang pagproseso sa 2 bahagi.

• Mayroong isang paghihiwalay, kailangan namin ang pag-uuri mismo:

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

  Iyon ay, kung ang array ay binubuo ng hindi bababa sa dalawang elemento, maaari na silang ayusin. Una, hinati namin ang buong array sa dalawang bahagi, mga elementong mas maliit kaysa sa pivot at mga elementong mas malaki. Pagkatapos ay nagsasagawa kami ng mga katulad na pagkilos para sa bawat isa sa mga resultang bahagi.

  At para sa pagsubok:

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

Sinasabi ng aklat na ang algorithm na ito ay kabilang sa tinatawag na "Divide and Conquer" na mga algorithm, kapag ang naprosesong set ng data ay nahahati sa kalahati sa bawat oras. Pagiging kumplikado ng algorithm: O(nLogn) Ang masama (iyon ay, kung ano ang hindi ko nagustuhan) ay binanggit ng aklat ang merge sort in passing, ngunit hindi nagbibigay ng anumang halimbawa o code. Higit pang mga detalye ang makikita dito: " Informatics. Search and sorting algorithms: Merge sort ". Samakatuwid, para sa kapakanan ng pagkakapare-pareho, gawin natin ito sa ating sarili. Ang algorithm mismo, siyempre, ay likas na simple at prangka:

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

Tinutukoy namin ang gitna at hatiin ang array sa kalahati. Para sa bawat kalahati ginagawa namin ang parehong at iba pa. Paghinto ng kundisyon o base case - dapat ay mayroon tayong higit sa isang elemento, dahil hindi natin mahahati ang isang elemento sa dalawa. Ngayon kailangan nating ipatupad ang pagsasama, iyon ay, pagsamahin:

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

Walang gaanong maikomento dito. Mula sa mga pangalan ng mga variable printlnang lahat ay malinaw. Well, upang suriin:

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

Hash table

Hinahawakan din ng libro ang mga hash table. Hindi mo kailangang ipatupad ito sa iyong sarili, at ang kakanyahan ng mga hash table ay medyo simple. Pagkatapos ng lahat, ang Java ay mayroon ding pagpapatupad ng mga hash table, java.util.HashTable. Kung titingnan natin ang HashTable device, makikita natin na ang Entry array ay nabubuhay sa loob. Ang entry ay isang talaan na kumbinasyon ng Key – Value. Ang HashTable ay may initialCapacity - iyon ay, ang paunang laki. At loadFactor – load factor. Ang default ay 0.75. Sinasabi sa iyo ng numerong ito kung anong load ng array (bilang ng mga elemento/kabuuang dami) ang kailangang dagdagan. Sa Java ito ay tumataas ng 2 beses. Ipinapaliwanag ng aklat na ang mga Hash table ay tinatawag na hash table dahil batay sa hash function, ang array cell (basket) kung saan ang Entry. Maaari ka ring magbasa ng higit pa dito: Mga istruktura ng data sa mga larawan. HashMap at LinkedHashMap . Mababasa mo rin ito sa mga libro. Halimbawa dito: " Mga pangunahing kaalaman sa HashTable "

Mga Graph, Breadth First Search (pinakamaikling paghahanap ng landas)

Marahil ang isa sa mga pinakakawili-wiling paksa ay ang mga graph. At dito, upang maging patas, ang libro ay nagbabayad ng maraming pansin sa kanila. Siguro kaya sulit na basahin ang librong ito. Bagaman, marahil, ito ay maaaring nasabi nang mas malinaw ng kaunti)) Ngunit, mayroon kaming Internet at bilang karagdagan sa aklat, maaari mong tingnan ang playlist na ito sa teorya para sa "mga taong nakakarinig tungkol sa mga graph sa unang pagkakataon . ” Well, natural, sa pinakadulo simula ng libro, ang breadth-first search algorithm, breadth-first-searchna kilala rin bilang BFS, ay ibinibigay. Ang aklat ay naglalaman ng sumusunod na graph: Nakasaad sa libro na makakatulong sa atin ang isang pila. Higit pa rito, tulad na maaari naming magdagdag ng mga elemento sa dulo at iproseso ang queue mula sa simula. Ang ganitong mga pila ay tinatawag na two-way queues o Deque sa Ingles. Iminumungkahi ng aklat ang paggamit ng istraktura ng data - isang hash table. Upang iugnay ang pangalan at mga kapitbahay. Sa mga may bilang na vertex, maaari kang gumamit ng array. Ang imbakan na ito ng mga vertices ay tinatawag na "Listahan ng mga katabing vertices," na hindi binanggit sa aklat. Ito ay isang minus para sa kanila. Ipatupad natin ito sa 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;
}

Ngayon ang paghahanap mismo, na binuo sa data na ito:

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

Tulad ng nakikita mo, walang kumplikado. Kung ihahambing mo ito sa code mula sa aklat, halos pareho ito.

Mga Graph, Algorithm ni Dijkstra

Sa pagkakaroon ng higit pa o hindi gaanong naiintindihan ang BFS, iniimbitahan kami ng may-akda ng aklat na maunawaan ang algorithm ng Daysktra at mga weighted graph. Ang sumusunod na graph ay iminungkahi para sa solusyon: Una, kailangan nating maunawaan kung paano kinakatawan ang ating mga graph. Maaari naming katawanin ito bilang isang matrix. Ang isang artikulo sa Habré ay makakatulong sa amin dito: Dijkstra's algorithm. Paghahanap ng mga pinakamainam na ruta sa isang graph . Gamitin natin ang adjacency matrix:

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

At ngayon ang lohika mismo:

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

Ibinahagi ito ng libro nang sunud-sunod. Kung nagdagdag ka ng artikulo sa Habré sa Internet + tingnan ang code, maaalala mo ito. Nakita kong medyo kalat ang step-by-step analysis. Ngunit para sa step-by-step na kalikasan mismo ito ay isang plus. Sa pangkalahatan, ok, kahit na ito ay maaaring mas mahusay)

Mga sakim na algorithm

Ang susunod na seksyon ay nakatuon sa "matakaw na mga algorithm". Ang seksyong ito ay kawili-wili dahil gumagamit ito ng mga set (java.util.Set). Sa wakas makikita natin kung bakit maaaring kailanganin ito. Gumagamit kami ng listahan ng mga estado bilang input:

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

At isang listahan din ng mga istasyon ng radyo na sumasaklaw sa ilan sa mga estadong ito:

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

Ang libro ay nagpatuloy upang ituro at ipaliwanag ang algorithm mismo:

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

Dynamic na programming

Inilalarawan din ng aklat ang mga problema kung saan inilalapat ang isang diskarte na tinatawag na "dynamic programming". Ang gawain ay ibinigay: Mayroon kaming 4 lb na bag. Kailangan mong mahanap ang pinaka-pinakinabangang mga item para sa isang naibigay na timbang. Una, gumawa tayo ng listahan ng mga item:

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

Ngayon ang algorithm mismo:

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

Mayroon ding isang kawili-wiling gawain upang mahanap ang pinakakatulad na mga salita. Kawili-wili, hindi ba? Higit pang mga detalye dito: LongestCommonSubsequence.java

Maghanap ng mga pinakamalapit na kapitbahay

Malinaw ding pinag-uusapan ng aklat ang tungkol sa algorithm ng k-pinakamalapit na mga kapitbahay: At ang formula para sa pagkalkula ay ibinigay:

Bottom line

Nagtatapos ang aklat sa isang kawili-wiling seksyong "Ano ang Susunod?", na nagbibigay ng mabilis na pangkalahatang-ideya ng mga kawili-wiling algorithm. Narito ang isang maikling paglalarawan ng kung ano ang kahulugan ng mga puno at iba pang mga algorithm. Sa pangkalahatan, nagustuhan ko ang libro. Hindi ito dapat seryosohin bilang isang uri ng komprehensibong impormasyon. Kailangan mong maghanap at maunawaan para sa iyong sarili. Ngunit bilang panimulang impormasyon sa interes at nagbibigay ng paunang ideya, ito ay medyo maganda. Oo, ang code sa libro ay nakasulat sa Python. Kaya lahat ng mga halimbawa sa itaas ay compilable) Umaasa ako na ang pagsusuri na ito ay makakatulong sa iyo na magkaroon ng ideya kung ano ang nilalaman ng libro at kung ito ay nagkakahalaga ng pagbili.

Bukod pa rito

Maaari mo ring tingnan ang mga sumusunod na mapagkukunan sa paksang ito:

1. EdX - Panimula sa Java Programming: Mga Pangunahing Istruktura ng Data at Algorithm
2. LinkedIn - Panimula sa Mga Structure ng Data at Algorithm sa Java (bayad)
3. 27 mga site na may mga puzzle upang patalasin ang iyong mga kasanayan sa programming
4. Java CodingBat
5. Mga gawain para sa mga programmer, mga sagot sa mga gawain na may iba't ibang kumplikado

#Viacheslav