Algoritma grocking atau pengenalan algoritma yang tidak menyakitkan

Semakan buku "Grocking Algorithm". Sedikit pendapat peribadi, beberapa contoh. Saya harap ulasan ini akan membantu anda memahami sama ada anda mahu membaca buku ini atau sama ada ia tidak akan mengambil tempat di rak anda. AMARAN: Banyak teks)

“Grocking Algorithm” atau Pengenalan Algoritma Tanpa Sakit

pengenalan

Hampir mana-mana kekosongan peringkat Junior mempunyai keperluan seperti "pengetahuan tentang struktur data dan algoritma." Bagi mereka yang mempunyai pendidikan khusus, algoritma disertakan dalam kursus umum dan tidak sepatutnya ada masalah. Tetapi bagaimana jika pembangunan itu dibawa masuk dari padang rumput lain? Yang tinggal hanyalah belajar sendiri. Terdapat jawapan kepada soalan "siapa yang harus dipersalahkan", tetapi kepada soalan "apa yang perlu dilakukan" jawapannya mesti dicari. Jom tengok dalam buku. Dan saya ingin memberitahu anda tentang satu.

Algoritma Grok

Di antara semua karya, saya terjumpa buku seperti "Grocking Algorithm". Anda boleh mengetahui lebih lanjut di sini: " Buku "Growing Algorithm. Panduan bergambar untuk pengaturcara dan yang ingin tahu ." Saya perhatikan buku itu lama dahulu, tetapi pada ozon ia berharga 680 rubel. Mahal atau murah - semua orang memutuskan untuk dirinya sendiri. Saya sudah membeli buku kedua di Avito pada separuh harga. Jadi saya menemuinya di St. Petersburg, membelinya, dan pergi grokking. Itulah yang saya memutuskan untuk berkongsi dengan anda. Ya, tiada kod Java dalam buku itu, tetapi ada... kod lain, tetapi lebih lanjut mengenainya kemudian.

Pengenalan kepada Algoritma (Isih Pilihan)

Jadi, dalam bentuk penceritaan yang mudah, kami mencapai pengisihan pertama dalam persembahan kami. Ini ialah Isih Pemilihan. Intipatinya ialah kita melalui elemen dari kiri ke kanan (dari 0 elemen hingga yang terakhir), dan mencari yang terbesar di antara elemen yang tinggal. Jika kita menemuinya, maka kita menukar elemen di mana kita berada sekarang dan elemen terbesar. Cara paling mudah untuk mula-mula memikirkan tatasusunan ialah: [5, 3, 6, 2, 10]. Ambil sehelai kertas, pen (cara paling mudah dan paling menjimatkan kos) dan bayangkan bagaimana kita mempunyai sempadan kiri, indeks semasa (atau sempadan kanan) dan indeks elemen minimum. Dan bagaimana kita bekerja dengannya. Sebagai contoh: Algoritma sering diterangkan dalam pseudokod, sebagai contoh, di Wikipedia. Kod kami bukan pseudokod, tetapi lebih lanjut mengenainya kemudian. Buat masa ini mari kita lihat:

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

Sekarang mari kita tunjukkan dalam bentuk kod 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;
            }
        }
}

Seperti yang anda lihat, kodnya hampir sama. Kod pertama ialah contoh daripada buku. Yang kedua ialah pelaksanaan percuma saya dalam kod Java.

Rekursi

Seterusnya kita diberitahu bahawa terdapat perkara seperti rekursi. Pertama sekali, ada masalah tentang seorang petani yang mempunyai sawah saiz AxB. Ia adalah perlu untuk membahagikan medan ini ke dalam "persegi" yang sama. Dan kemudian selepas ini Algoritma Euclid disebut. Apa yang saya tidak suka ialah mereka tidak cuba menulis kodnya. Tetapi algoritma Euclid adalah mudah dan berkesan: Sejujurnya, saya terlepas beberapa butiran dalam buku, seperti dalam video ini: “ Informatik. Teori algoritma. Algoritma Euclid ." Sebagai contoh, jika a kurang daripada b, maka semasa larian pertama b dan a akan bertukar tempat dan kali kedua yang lebih besar akan dibahagikan dengan yang lebih kecil. Oleh itu, susunan hujah tidak penting. Seperti biasa, mula-mula kita boleh "merasakan" algoritma pada sekeping kertas: Sekarang mari kita lihat kod:

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

Mari kita tulis kod yang sama dalam Java. Jika dikehendaki, kita boleh menggunakan pengkompil dalam talian :

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

Faktorial juga disebut pada permulaan buku. Faktorial bagi suatu nombor n (n!) ialah hasil darab nombor dari 1 hingga n. Mengapa melakukan ini? Terdapat satu aplikasi praktikal di sini. Jika kita mempunyai n objek (contohnya, n bandar), maka kita boleh membuat n daripadanya! Gabungan. Anda boleh membaca lebih lanjut tentang rekursi di sini: " Rekursi. Tugas latihan ." Perbandingan pendekatan berulang dan rekursif: " Rekursi ".

Isih cepat

Isih pantas ialah algoritma yang agak menarik. Buku itu tidak begitu memberi perhatian kepadanya. Selain itu, kod diberikan hanya untuk kes terburuk, apabila elemen pertama dipilih. Walau bagaimanapun, mungkin untuk kenalan pertama contoh ini akan lebih mudah diingati. Dan adalah lebih baik untuk menulis quicksort yang buruk daripada tidak menulis sama sekali. Berikut adalah contoh dari buku tersebut:

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)

Segala-galanya di sini sangat mudah. Jika kita mempunyai tatasusunan 0 atau 1 elemen, tidak perlu mengisihnya. Jika ia lebih besar, kami mengambil elemen pertama tatasusunan dan menganggapnya sebagai "elemen pangsi". Kami mencipta 2 tatasusunan baharu - satu mengandungi elemen yang lebih besar daripada pangsi, dan yang kedua mengandungi elemen yang lebih kecil. Dan kami ulangi secara rekursif. Bukan pilihan terbaik, tetapi sekali lagi, lebih diingati. Mari kita laksanakan algoritma ini dalam Java, tetapi dengan lebih betul. Bahan daripada ulasan " Sains Komputer dalam JavaScript: Quicksort " akan membantu kami dengan ini . Dan sebelum menulis kod, mari kita lukis semula untuk "merasakan" algoritma: Pertama, mari kita lukis semula pada sehelai kertas untuk memahami algoritma: Nampaknya salah satu momen yang paling berbahaya adalah untuk menyelesaikan masalah sepenuhnya. Oleh itu, kami akan melaksanakan pelaksanaan dalam beberapa langkah kecil:

• Kita perlu dapat menukar elemen dalam tatasusunan:

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




• Kami memerlukan kaedah yang membahagikan tatasusunan dalam selang yang ditentukan kepada 3 bahagian

  
  

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

  Butiran di pautan di atas. Ringkasnya, kami menggerakkan kursor kiri sehingga elemen kurang daripada pangsi. Begitu juga, gerakkan kursor kanan dari hujung yang lain. Dan kami melakukan pertukaran jika kursor tidak sepadan. Kami meneruskan sehingga kursor bertumpu. Kami mengembalikan indeks yang membahagikan pemprosesan selanjutnya kepada 2 bahagian.

• Terdapat pemisahan, kita memerlukan pengisihan itu sendiri:

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

  Iaitu, jika tatasusunan terdiri daripada sekurang-kurangnya dua elemen, maka ia sudah boleh diisih. Pertama, kami membahagikan keseluruhan tatasusunan kepada dua bahagian, elemen yang lebih kecil daripada pangsi dan elemen yang lebih besar. Kemudian kami melakukan tindakan yang serupa untuk setiap bahagian yang terhasil.

  Dan untuk ujian:

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

Buku itu menyatakan bahawa algoritma ini tergolong dalam apa yang dipanggil algoritma "Divide and Conquer", apabila set data yang diproses dibahagikan kepada separuh setiap kali. Kerumitan algoritma: O(nLogn) Apa yang buruk (iaitu, perkara yang saya tidak suka) ialah buku itu menyebut isihan gabungan secara beransur-ansur, tetapi tidak memberikan sebarang contoh atau kod. Butiran lanjut boleh didapati di sini: " Informatik. Algoritma carian dan pengisihan: Gabungkan isihan ". Oleh itu, demi konsistensi, mari kita lakukan sendiri. Algoritma itu sendiri, sudah tentu, sememangnya mudah dan mudah:

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

Kami menentukan bahagian tengah dan membahagikan tatasusunan kepada separuh. Untuk setiap separuh kita melakukan perkara yang sama dan seterusnya. Keadaan penghentian atau kes asas - kita mesti mempunyai lebih daripada satu elemen, kerana kita tidak boleh membahagikan satu elemen kepada dua. Sekarang kita perlu melaksanakan penggabungan, iaitu, penggabungan:

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

Tidak banyak yang perlu diulas di sini. Dari nama pembolehubah printlnsemuanya jelas. Nah, untuk menyemak:

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

Hash jadual

Buku ini juga menyentuh jadual cincang. Anda tidak perlu melaksanakannya sendiri, dan intipati jadual hash agak mudah. Lagipun, Java juga mempunyai pelaksanaan jadual cincang, java.util.HashTable. Jika kita melihat peranti HashTable, kita akan melihat bahawa tatasusunan Kemasukan tinggal di dalam. Kemasukan ialah rekod yang merupakan gabungan Kunci – Nilai. HashTable mempunyai initialCapacity - iaitu saiz awal. Dan loadFactor - faktor beban. Lalai ialah 0.75. Nombor ini memberitahu anda pada beban tatasusunan (bilangan elemen/jumlah kuantiti) saiz yang perlu ditingkatkan. Di Jawa ia meningkat sebanyak 2 kali ganda. Buku ini menerangkan bahawa jadual Hash dipanggil jadual hash kerana berdasarkan fungsi hash, sel tatasusunan (bakul) di mana Entry. Anda juga boleh membaca lebih lanjut di sini: Struktur data dalam gambar. HashMap dan LinkedHashMap . Anda juga boleh membacanya dalam buku. Contohnya di sini: " Asas HashTable "

Graf, Breadth First Search (carian laluan terpendek)

Mungkin salah satu topik yang paling menarik ialah graf. Dan di sini, untuk bersikap adil, buku itu memberi banyak perhatian kepada mereka. Mungkin sebab itu berbaloi untuk membaca buku ini. Walaupun, mungkin, ia boleh dinyatakan dengan lebih jelas sedikit)) Tetapi, kami mempunyai Internet dan sebagai tambahan kepada buku itu, anda boleh melihat senarai main ini pada teori untuk "mereka yang mendengar tentang graf buat kali pertama . ” Sememangnya, pada awal buku, algoritma carian luas-pertama, breadth-first-searchjuga dikenali sebagai BFS, diberikan. Buku ini mengandungi graf berikut: Buku itu menyatakan bahawa barisan akan membantu kita. Lebih-lebih lagi, supaya kita boleh menambah elemen pada penghujung dan memproses baris gilir dari awal. Barisan sebegini dipanggil baris gilir dua hala atau Deque dalam bahasa Inggeris. Buku ini mencadangkan penggunaan struktur data - jadual cincang. Untuk mengaitkan nama dan jiran. Dengan bucu bernombor, anda hanya boleh menggunakan tatasusunan. Penyimpanan bucu ini dipanggil "Senarai bucu bersebelahan", yang tidak disebut dalam buku. Ini adalah tolak untuk mereka. Mari kita laksanakan ini di Jawa:

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

Sekarang carian itu sendiri, dibina berdasarkan data ini:

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

Seperti yang anda lihat, tiada yang rumit. Jika anda membandingkannya dengan kod daripada buku, ia hampir sama.

Graf, Algoritma Dijkstra

Setelah lebih atau kurang memahami BFS, pengarang buku itu menjemput kami untuk memahami algoritma Daysktra dan graf berwajaran. Graf berikut dicadangkan untuk penyelesaian: Pertama, kita perlu memahami cara mewakili graf kita. Kita boleh mewakilinya sebagai matriks. Artikel tentang Habré akan membantu kami di sini: Algoritma Dijkstra. Mencari laluan optimum pada graf . Mari kita gunakan matriks bersebelahan:

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

Dan sekarang logiknya sendiri:

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

Buku itu menguraikannya secara berperingkat-peringkat. Jika anda menambah artikel tentang Habré di Internet + lihat kod, anda boleh mengingatinya. Saya dapati analisis langkah demi langkah agak berterabur. Tetapi untuk sifat langkah demi langkah itu sendiri ia adalah satu kelebihan. Secara keseluruhan, ok, walaupun ia mungkin lebih baik)

Algoritma tamak

Bahagian seterusnya dikhaskan untuk "algoritma tamak". Bahagian ini menarik kerana ia menggunakan set (java.util.Set). Akhirnya kita dapat melihat mengapa ia mungkin diperlukan. Kami menggunakan senarai negeri sebagai input:

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

Dan juga senarai stesen radio yang meliputi beberapa negeri ini:

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

Buku itu terus menunjukkan dan menerangkan algoritma itu sendiri:

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

Pengaturcaraan dinamik

Buku ini juga menerangkan masalah yang mana pendekatan yang dipanggil "pengaturcaraan dinamik" digunakan. Tugasan diberikan: Kami mempunyai beg 4 lb. Anda perlu mencari item yang paling menguntungkan untuk berat tertentu. Mula-mula, mari kita buat senarai 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));

Sekarang algoritma itu sendiri:

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

Terdapat juga tugas yang menarik untuk mencari perkataan yang paling serupa. Menarik, bukan? Butiran lanjut di sini: LongestCommonSubsequence.java

Cari jiran terdekat

Buku ini juga sangat jelas bercakap tentang algoritma jiran k-terdekat: Dan formula untuk pengiraan diberikan:

Pokoknya

Buku ini berakhir dengan bahagian "What's Next?" yang menarik, yang memberikan gambaran ringkas tentang algoritma yang menarik. Berikut ialah penerangan ringkas tentang maksud pokok dan algoritma lain. Secara keseluruhan, saya suka buku itu. Ia tidak boleh dianggap serius sebagai sejenis maklumat yang komprehensif. Anda perlu mencari dan memahami sendiri. Tetapi sebagai maklumat pengenalan kepada minat dan memberi idea awal, ia agak bagus. Ya, kod dalam buku itu ditulis dalam Python. Jadi semua contoh di atas boleh dikompilasi) Saya harap ulasan ini akan membantu anda mendapatkan idea tentang kandungan buku itu dan sama ada ia berbaloi untuk dibeli.

Selain itu

Anda juga boleh menyemak sumber berikut mengenai topik ini:

1. EdX - Pengenalan kepada Pengaturcaraan Java: Struktur Data Asas dan Algoritma
2. LinkedIn - Pengenalan kepada Struktur Data & Algoritma dalam Java (berbayar)
3. 27 tapak dengan teka-teki untuk mengasah kemahiran pengaturcaraan anda
4. Java CodingBat
5. Tugas untuk pengaturcara, jawapan kepada tugas yang mempunyai kerumitan yang berbeza-beza

#Viacheslav