Algoritme Grocking atau pengenalan algoritma yang mudah

Resensi buku "Algoritma Grocking". Sedikit pendapat pribadi, beberapa contoh. Saya harap ulasan ini akan membantu Anda memahami apakah Anda ingin membaca buku ini atau tidak akan ada di rak Anda. PERINGATAN: Banyak teks)

“Algoritma Berkembang” atau Pengantar Algoritma yang Tidak Menyakitkan

Perkenalan

Hampir semua lowongan tingkat Junior memiliki persyaratan seperti “pengetahuan tentang struktur data dan algoritma.” Bagi mereka yang memiliki pendidikan khusus, algoritma termasuk dalam kursus umum dan seharusnya tidak ada masalah. Namun bagaimana jika pembangunan tersebut didatangkan dari stepa lain? Yang tersisa hanyalah belajar sendiri. Ada jawaban atas pertanyaan “siapa yang harus disalahkan”, tetapi untuk pertanyaan “apa yang harus dilakukan” jawabannya harus dicari. Mari kita lihat di buku. Dan saya ingin memberi tahu Anda tentang satu hal.

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 1

Algoritma Grok

Di antara semua karya, saya menemukan buku seperti “Grocking Algorithms”. Anda dapat mengetahui lebih lanjut di sini: “ Buku “Algoritma Berkembang. Panduan bergambar untuk pemrogram dan mereka yang penasaran .” Saya sudah lama memperhatikan buku itu, tetapi untuk ozon harganya 680 rubel. Mahal atau murah - semua orang memutuskan sendiri. Saya sudah membeli buku kedua di Avito dengan setengah harga. Jadi saya menemukannya di St. Petersburg, membelinya, dan pergi mencarinya. Itulah yang saya putuskan untuk dibagikan kepada Anda. Ya, tidak ada kode Java di buku ini, tapi ada... kode lain, tapi akan dibahas lebih lanjut nanti.

Pengantar Algoritma (Seleksi Sortir)

Jadi, dalam bentuk narasi yang mudah, kami mencapai penyortiran pertama dalam penampilan kami. Ini adalah Urutan Seleksi. Esensinya adalah kita menelusuri elemen dari kiri ke kanan (dari elemen 0 hingga terakhir), dan mencari yang terbesar di antara elemen yang tersisa. Jika kita menemukannya, maka kita menukar elemen tempat kita berada sekarang dan elemen terbesar. Cara paling sederhana untuk memikirkan sebuah array adalah: [5, 3, 6, 2, 10]. Ambil selembar kertas, pena (cara paling sederhana dan paling hemat biaya) dan bayangkan bagaimana kita memiliki batas kiri, indeks saat ini (atau batas kanan), dan indeks elemen minimum. Dan bagaimana kami mengatasinya. Misalnya:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 2

Algoritma sering dijelaskan dalam pseudocode, misalnya di Wikipedia. Milik kami sebenarnya bukanlah kodesemu, tetapi akan dibahas lebih lanjut nanti. Untuk saat 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 sajikan dalam bentuk kode 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, kodenya hampir sama. Kode pertama adalah contoh dari buku. Yang kedua adalah eksekusi gratis saya dalam kode Java.

Pengulangan

Selanjutnya kita diberitahu bahwa ada yang namanya rekursi. Pertama, ada permasalahan pada seorang petani yang mempunyai lahan seluas AxB. Bidang ini perlu dibagi menjadi “kotak” yang sama. Dan kemudian setelah ini Algoritma Euclid disebutkan. Yang tidak saya sukai adalah mereka tidak mencoba menulis kodenya. Namun algoritma Euclid sederhana dan efektif:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 3

Sejujurnya, saya melewatkan beberapa detail di buku tersebut, seperti di video ini: “ Informatika. Teori algoritma. Algoritma Euclid ." Misalnya, jika a lebih kecil dari b, maka pada putaran pertama b dan a akan berpindah tempat dan kedua kalinya yang lebih besar akan dibagi dengan yang lebih kecil. Oleh karena itu, urutan argumen tidaklah penting. Seperti biasa, pertama-tama kita bisa “merasakan” algoritmanya di selembar kertas:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 4

Sekarang mari kita lihat kodenya:


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

Mari kita menulis kode yang sama di Java. Jika diinginkan, kita dapat menggunakan kompiler online :


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 disebutkan di awal buku. Faktorial suatu bilangan n (n!) adalah hasil kali bilangan dari 1 sampai n. Kenapa melakukan ini? Ada satu penerapan praktis di sini. Jika kita mempunyai n objek (misalnya n kota), maka kita dapat membuat n objek! Kombinasi. Anda dapat membaca lebih lanjut tentang rekursi di sini: " Rekursi. Tugas pelatihan ." Perbandingan pendekatan iteratif dan rekursif: " Rekursi ".

Penyortiran cepat

Penyortiran cepat adalah algoritma yang cukup menarik. Buku itu tidak terlalu memperhatikannya. Selain itu, kode tersebut hanya diberikan untuk kasus terburuk, ketika elemen pertama dipilih. Namun, mungkin bagi yang baru pertama kali mengenal contoh ini akan lebih mudah diingat. Dan lebih baik menulis quicksort yang buruk daripada tidak menulisnya sama sekali. Berikut ini 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)

Semuanya di sini sangat sederhana. Jika kita memiliki array dengan elemen 0 atau 1, tidak perlu mengurutkannya. Jika lebih besar, kita mengambil elemen pertama dari array dan menganggapnya sebagai “elemen pivot”. Kami membuat 2 array baru - satu berisi elemen yang lebih besar dari pivot, dan yang kedua berisi elemen yang lebih kecil. Dan kami ulangi secara rekursif. Bukan pilihan terbaik, tapi sekali lagi, lebih baik diingat. Mari kita terapkan algoritma ini di Java, tetapi lebih tepat. Materi dari ulasan “ Ilmu Komputer dalam JavaScript: Quicksort ” akan membantu kami dalam hal ini . Dan sebelum menulis kodenya, mari kita menggambar lagi untuk “merasakan” algoritmanya: Pertama, mari kita menggambar lagi di selembar kertas untuk memahami algoritmanya:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 5

Bagi saya, salah satu momen paling berbahaya adalah menyelesaikan masalah sepenuhnya. Oleh karena itu, kami akan melakukan penerapannya dalam beberapa langkah kecil:

Kita harus bisa menukar elemen dalam array:


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

Kita memerlukan suatu metode yang membagi array pada interval yang ditentukan menjadi 3 bagian


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

Detailnya ada di tautan di atas. Singkatnya, kita gerakkan kursor kiri hingga elemen tersebut kurang dari pivot. Demikian pula, gerakkan kursor kanan dari ujung yang lain. Dan kami melakukan swap jika kursor tidak cocok. Kami melanjutkan sampai kursor bertemu. Kami mengembalikan indeks yang membagi pemrosesan lebih lanjut menjadi 2 bagian.

Ada pemisahan, kita perlu penyortiran 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);
            }
        }
}

Artinya, jika array terdiri dari minimal dua elemen, maka elemen tersebut sudah dapat diurutkan. Pertama, kita membagi seluruh array menjadi dua bagian, elemen yang lebih kecil dari pivot dan elemen yang lebih besar. Kemudian kami melakukan tindakan serupa untuk setiap bagian yang dihasilkan.

Dan untuk ujiannya:


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 tersebut menyatakan bahwa algoritma ini termasuk dalam apa yang disebut algoritma “Divide and Conquer”, ketika kumpulan data yang diproses dibagi dua setiap kali. Kompleksitas algoritma: O(nLogn)

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 6

Yang buruk (yang tidak saya sukai) adalah buku tersebut menyebutkan pengurutan gabungan secara sepintas, tetapi tidak memberikan contoh atau kode apa pun. Detail lebih lanjut dapat ditemukan di sini: " Informatika. Algoritma pencarian dan pengurutan: Gabungkan pengurutan ". Oleh karena itu, demi konsistensi, mari kita lakukan sendiri. Algoritmenya sendiri, tentu saja, sederhana dan mudah dimengerti:


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 bagian tengah dan membagi array menjadi dua. Untuk setiap bagian kami melakukan hal yang sama dan seterusnya. Kondisi penghentian atau kasus dasar - kita harus memiliki lebih dari satu elemen, karena kita tidak dapat membagi satu elemen menjadi dua. Sekarang kita perlu melaksanakan merger, yaitu merger:


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 bisa dikomentari di sini. Dari nama variabelnya printlnsemuanya jelas. Nah, untuk memeriksanya:


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

Tabel hash

Buku ini juga menyentuh tabel hash. Anda tidak perlu menerapkannya sendiri, dan inti dari tabel hash cukup sederhana. Lagipula, Java juga memiliki implementasi tabel hash, java.util.HashTable. Jika kita melihat perangkat HashTable, kita akan melihat bahwa array Entry ada di dalamnya. Entry merupakan record yang merupakan kombinasi Key – Value. HashTable memiliki InitialCapacity - yaitu ukuran awal. Dan loadFactor – faktor beban. Standarnya adalah 0,75. Angka ini memberi tahu Anda berapa beban array (jumlah elemen/jumlah total) yang ukurannya perlu ditingkatkan. Di Pulau Jawa meningkat 2 kali lipat. Buku tersebut menjelaskan bahwa tabel Hash disebut tabel hash karena berdasarkan fungsi hash, sel array (keranjang) di mana Entry. Anda juga dapat membaca lebih lanjut di sini: Struktur data dalam gambar. HashMap dan LinkedHashMap . Anda juga bisa membacanya di buku. Misalnya di sini: " Dasar-dasar HashTable "

Grafik, Pencarian Pertama Luas (pencarian jalur terpendek)

Mungkin salah satu topik yang paling menarik adalah grafik. Dan di sini, sejujurnya, buku ini memberikan banyak perhatian kepada mereka. Mungkin itu sebabnya buku ini layak dibaca. Meskipun, mungkin, hal itu dapat dinyatakan dengan lebih jelas)) Namun, kami memiliki Internet dan selain buku, Anda dapat melihat daftar putar teori ini untuk “mereka yang baru pertama kali mendengar tentang grafik . ” Tentu saja, di awal buku ini, algoritma pencarian luas pertama, breadth-first-searchyang juga dikenal sebagai BFS, diberikan. Buku tersebut berisi grafik berikut:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 7

Buku tersebut menyatakan bahwa antrian akan membantu kita. Apalagi kita bisa menambahkan elemen di akhir dan memproses antrian dari awal. Antrian seperti ini disebut antrian dua arah atau Deque dalam bahasa Inggris. Buku ini menyarankan penggunaan struktur data - tabel hash. Untuk mengkorelasikan nama dan tetangga. Dengan simpul bernomor, Anda cukup menggunakan array. Penyimpanan simpul-simpul ini disebut “Daftar simpul-simpul yang bertetangga”, yang tidak disebutkan dalam buku. Ini merupakan kerugian bagi mereka. Mari kita terapkan ini di 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;
}

Sekarang pencariannya sendiri, dibangun 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, tidak ada yang rumit. Jika dibandingkan dengan kode yang ada di buku, hampir sama.

Grafik, Algoritma Dijkstra

Setelah kurang lebih memahami BFS, penulis buku ini mengajak kita untuk memahami algoritma Daysktra dan grafik berbobot. Grafik berikut diusulkan untuk solusinya:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 8

Pertama, kita perlu memahami cara merepresentasikan grafik kita. Kita bisa merepresentasikannya sebagai matriks. Sebuah artikel tentang Habré akan membantu kita di sini: Algoritma Dijkstra. Menemukan rute optimal pada grafik . Mari kita gunakan matriks ketetanggaan:


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 logikanya 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 ini menguraikannya langkah demi langkah. Jika Anda menambahkan artikel tentang Habré di Internet + melihat kodenya, Anda dapat mengingatnya. Menurut saya analisis langkah demi langkah agak berantakan. Tapi untuk sifat step by stepnya sendiri itu nilai plusnya. Secara keseluruhan, oke, meskipun bisa lebih baik)

Algoritma serakah

Bagian selanjutnya dikhususkan untuk "algoritma serakah". Bagian ini menarik karena menggunakan set (java.util.Set). Akhirnya kita dapat melihat mengapa hal itu mungkin diperlukan. Kami menggunakan daftar negara bagian sebagai masukan:


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

Dan juga daftar stasiun radio yang meliput beberapa negara bagian 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 ini selanjutnya menunjukkan dan menjelaskan 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);

Pemrograman dinamis

Buku ini juga menjelaskan permasalahan yang menggunakan pendekatan yang disebut “pemrograman dinamis”. Tugas yang diberikan:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 9

Kami memiliki tas seberat 4 pon. Anda perlu menemukan item yang paling menguntungkan untuk berat tertentu. Pertama, mari kita buat daftar 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 algoritmanya 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));

Ada juga tugas menarik untuk menemukan kata-kata yang paling mirip. Menarik bukan? Detail lebih lanjut di sini: LongestCommonSubsequence.java

Cari tetangga terdekat

Buku ini juga dengan jelas berbicara tentang algoritma k-nearest neighbours:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 10

Dan rumus perhitungannya diberikan:

“Algoritma Grocking” atau Pengantar Algoritma yang Tidak Menyakitkan - 11

Intinya

Buku ini diakhiri dengan bagian "Apa Selanjutnya?" yang menarik, yang memberikan gambaran singkat tentang algoritma yang menarik. Berikut ini penjelasan singkat mengenai pengertian pohon dan algoritma lainnya. Secara keseluruhan, saya menyukai buku itu. Ini tidak boleh dianggap serius sebagai informasi yang komprehensif. Anda harus mencari dan memahaminya sendiri. Namun sebagai informasi pengantar untuk menarik dan memberi gambaran awal, cukup bagus. Ya, kode di buku itu ditulis dengan Python. Jadi semua contoh di atas dapat dikompilasi) Saya harap ulasan ini dapat membantu Anda mendapatkan gambaran tentang isi buku tersebut dan apakah layak untuk dibeli.

Selain itu

Anda juga dapat melihat sumber daya berikut tentang topik ini:

#Viacheslav