Algoritmlar yoki algoritmlarga og'riqsiz kirish

"Grocking Algoritms" kitobiga sharh. Bir oz shaxsiy fikr, bir nechta misol. Umid qilamanki, ushbu sharh sizga ushbu kitobni o'qishni xohlaysizmi yoki u sizning javoningizda o'z o'rnini egallamaydimi yoki yo'qligini tushunishga yordam beradi. OGOHLANTIRISH: Ko'p matn)

"Grocking Algoritmlari" yoki Algoritmlarga og'riqsiz kirish

Kirish

Junior darajadagi deyarli har qanday vakansiyada "ma'lumotlar tuzilmalari va algoritmlarni bilish" kabi talablar mavjud. Maxsus ma'lumotga ega bo'lganlar uchun algoritmlar umumiy kursga kiritilgan va hech qanday muammo bo'lmasligi kerak. Ammo rivojlanish boshqa dashtlardan olib kelingan bo'lsa-chi? Qolgan narsa - o'zingiz o'rganish. "Kim aybdor" degan savolga javob bor, ammo "nima qilish kerak" degan savolga javob izlash kerak. Keling, kitoblarni ko'rib chiqaylik. Va men sizga bitta haqida aytib bermoqchiman.

Grok algoritmlari

Barcha ishlar orasida men "Grocking Algoritms" kabi kitobga duch keldim. Siz bu yerda koʻproq maʼlumot olishingiz mumkin: “ “Oʻsish algoritmlari. Dasturchilar va qiziquvchilar uchun tasvirlangan qoʻllanma” kitobi . Men kitobni uzoq vaqt oldin payqadim, lekin ozonda uning narxi 680 rubl edi. Qimmat yoki arzon - har kim o'zi uchun qaror qiladi. Men Avito bo'yicha ikkinchi kitobni yarim narxga sotib olaman. Shunday qilib, men uni Sankt-Peterburgda topdim, sotib oldim va gurkirab ketdim. Bu men siz bilan baham ko'rishga qaror qildim. Ha, kitobda Java kodi yo'q, lekin ... boshqa kod bor, lekin bu haqda keyinroq.

Algoritmlarga kirish (tanlovni saralash)

Shunday qilib, rivoyatning oson shaklida, biz ijroimizda birinchi saralashga erishamiz. Bu tanlash saralash. Uning mohiyati shundaki, biz elementlarni chapdan o'ngga (0 elementdan oxirgigacha) o'tkazamiz va qolgan elementlardan eng kattasini qidiramiz. Agar biz uni topsak, biz hozir bo'lgan elementni va eng katta elementni almashtiramiz. Massiv haqida o'ylashning eng oddiy usuli: [5, 3, 6, 2, 10]. Bir parcha qog'oz, qalam (eng oddiy va eng arzon yo'l) oling va bizda qanday qilib chap chegara (chapda), joriy indeks (yoki o'ng chegara) borligini tasavvur qiling, minimal element indeksi mavjud. Va biz u bilan qanday ishlaymiz. Masalan: Algoritmlar ko'pincha psevdokodda tasvirlangan, masalan, Vikipediyada. Bizniki aniq psevdokod emas, lekin bu haqda keyinroq. Hozircha ko'rib chiqamiz:

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

Endi uni Java kodi shaklida taqdim etamiz:

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

Ko'rib turganingizdek, kod deyarli bir xil. Birinchi kod kitobdan namunadir. Ikkinchisi - Java kodida bepul bajarilishim.

Rekursiya

Keyin bizga rekursiya kabi narsa borligi aytiladi. Avvalo, AxB o'lchamdagi dalaga ega bo'lgan fermerning muammosi bor. Bu maydonni teng "kvadratlarga" bo'lish kerak. Shundan so'ng Evklid algoritmi esga olinadi. Menga yoqmagan tomoni shundaki, ular uning kodini yozishga harakat qilishmagan. Ammo Evklid algoritmi oddiy va samarali: Rostini aytsam, men kitobdagi ba'zi tafsilotlarni o'tkazib yubordim, masalan, ushbu videodagi: " Informatika. Algoritmlar nazariyasi. Evklid algoritmi ." Misol uchun, agar a b dan kichik bo'lsa, u holda birinchi yugurishda b va a o'rnini o'zgartiradi va ikkinchi marta kattasi kichikroqqa bo'linadi. Shuning uchun argumentlar tartibi muhim emas. Odatdagidek, avval biz algoritmni qog'oz varag'ida "his qilishimiz" mumkin: Endi kodni ko'rib chiqamiz:

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

Keling, xuddi shu kodni Java-da yozamiz. Agar xohlasangiz, onlayn kompilyatordan foydalanishimiz mumkin :

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

Kitob boshida faktorial ham tilga olingan. n (n!) sonining faktoriali 1 dan n gacha bo‘lgan sonlarning ko‘paytmasidir. Nega buni qilyapti? Bu erda bitta amaliy dastur mavjud. Agar bizda n ta ob'ekt (masalan, n ta shahar) bo'lsa, biz ulardan n tasini yasay olamiz! Kombinatsiyalar. Rekursiya haqida koʻproq maʼlumotni bu yerda oʻqishingiz mumkin: “ Rekursiya. Trening vazifalari ”. Iterativ va rekursiv yondashuvlarni taqqoslash: " Rekursiya ".

Tez tartiblash

Tez tartiblash juda qiziqarli algoritmdir. Kitobda unga unchalik ahamiyat berilmagan. Bundan tashqari, kod faqat eng yomon holatda, birinchi element tanlanganda beriladi. Biroq, ehtimol, birinchi tanishish uchun bu misolni eslab qolish osonroq bo'ladi. Va umuman yozmaslikdan ko'ra yomon tezkor yozish yaxshidir. Mana kitobdan bir misol:

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)

Bu erda hamma narsa juda oddiy. Agar bizda 0 yoki 1 elementli massiv bo'lsa, uni saralashning hojati yo'q. Agar u kattaroq bo'lsa, biz massivning birinchi elementini olamiz va uni "burilish elementi" deb hisoblaymiz. Biz ikkita yangi massiv yaratamiz - birida pivotdan kattaroq elementlar, ikkinchisida esa kichikroq elementlar mavjud. Va biz takroriy takrorlaymiz. Eng yaxshi variant emas, lekin yana yaxshi eslab qoling. Keling, ushbu algoritmni Java-da amalga oshiraylik, lekin to'g'riroq. Bunda bizga “ JavaScript-da kompyuter fanlari: Quicksort ” sharhidagi material yordam beradi . Va kodni yozishdan oldin, algoritmni "his qilish" uchun yana chizamiz: Avval algoritmni tushunish uchun qog'ozga yana chizamiz: Menimcha, eng xavfli daqiqalardan biri bu muammolarni butunlay hal qilishdir. Shuning uchun biz amalga oshirishni bir necha kichik bosqichlarda amalga oshiramiz:

• Biz massivdagi elementlarni almashtira olishimiz kerak:

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




• Belgilangan oraliqdagi massivni 3 qismga ajratadigan usul kerak

  
  

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

  Tafsilotlar yuqoridagi havolada. Qisqacha aytganda, chap kursorni element pivotdan kamroq bo'lguncha harakatlantiramiz. Xuddi shunday, o'ng kursorni boshqa uchidan siljiting. Va agar kursorlar mos kelmasa, biz almashtiramiz. Kursorlar birlashguncha davom etamiz. Biz keyingi ishlov berishni 2 qismga ajratadigan indeksni qaytaramiz.

• Ajratish bor, bizga saralashning o'zi kerak:

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

  Ya'ni, agar massiv kamida ikkita elementdan iborat bo'lsa, ularni allaqachon tartiblash mumkin. Birinchidan, biz butun massivni ikki qismga ajratamiz, elementlar pivotdan kichikroq va elementlar kattaroqdir. Keyin olingan qismlarning har biri uchun shunga o'xshash harakatlarni bajaramiz.

  Va sinov uchun:

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

Kitobda aytilishicha, bu algoritm qayta ishlangan ma'lumotlar to'plami har safar yarmiga bo'linganda "Bo'lin va zabt et" deb ataladigan algoritmlarga tegishli. Algoritm murakkabligi: O(nLogn) Yomon tomoni (ya'ni, menga yoqmagani) kitobda birlashma tartiblash haqida so'z boradi, lekin hech qanday misol yoki kod keltirmaydi. Batafsil ma'lumotni bu yerda topishingiz mumkin: " Informatika. Qidiruv va saralash algoritmlari: Birlashtirish tartibi ". Shuning uchun, izchillik uchun, keling, buni o'zimiz qilaylik. Algoritmning o'zi, albatta, oddiy va tushunarli:

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

Biz o'rtani aniqlaymiz va massivni yarmiga ajratamiz. Har bir yarmi uchun biz xuddi shunday qilamiz va hokazo. To'xtash sharti yoki asosiy holat - bizda bir nechta element bo'lishi kerak, chunki biz bitta elementni ikkiga bo'lolmaydi. Endi biz birlashishni, ya'ni birlashishni amalga oshirishimiz kerak:

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

Bu erda izoh berish uchun ko'p narsa yo'q. O'zgaruvchilar nomlaridan printlnhamma narsa aniq. Xo'sh, tekshirish uchun:

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

Xesh jadvallari

Kitob shuningdek, hash jadvallariga ham to'xtalib o'tadi. Buni o'zingiz amalga oshirishingiz shart emas va xesh-jadvallarning mohiyati juda oddiy. Axir, Java ham java.util.HashTable xesh-jadvallarini amalga oshirishga ega. Agar biz HashTable qurilmasiga qarasak, Entry massivi ichida yashashini ko'ramiz. Kirish Key – Value birikmasidan iborat yozuvdir. HashTableda initialCapacity mavjud - ya'ni boshlang'ich hajmi. Va loadFactor - yuk omili. Standart 0,75. Bu raqam massivning qaysi yukida (elementlar soni/umumiy miqdor) hajmini oshirish kerakligini bildiradi. Java-da u 2 barobar ortadi. Kitobda xesh-jadvallar xesh-jadvallar deb ataladi, chunki xesh-funktsiyaga asoslanib, massiv katakchasi (savat) Entry. Batafsil bu yerda ham oʻqishingiz mumkin: Rasmlardagi maʼlumotlar tuzilmalari. HashMap va LinkedHashMap . Siz uni kitoblarda ham o'qishingiz mumkin. Masalan, bu erda: " HashTable asoslari "

Grafiklar, kenglikdagi birinchi qidiruv (eng qisqa yo'l qidirish)

Ehtimol, eng qiziqarli mavzulardan biri grafikalardir. Va bu erda, adolat uchun, kitob ularga katta e'tibor beradi. Balki shuning uchun ham bu kitobni o'qishga arziydi. Garchi, ehtimol, buni biroz aniqroq aytish mumkin edi)) Ammo bizda Internet bor va kitobga qo'shimcha ravishda siz ushbu pleylistni " grafiklar haqida birinchi marta eshitayotganlar " nazariyasiga ko'rib chiqishingiz mumkin . ” Tabiiyki, kitobning boshida breadth-first-searchBFS deb ham ataladigan kenglikdagi birinchi qidiruv algoritmi berilgan. Kitobda quyidagi grafik mavjud: Kitobda navbat bizga yordam berishi aytilgan. Bundan tashqari, biz oxirigacha elementlarni qo'shishimiz va navbatni boshidan qayta ishlashimiz mumkin. Bunday navbatlar ikki tomonlama navbat yoki ingliz tilida Deque deb ataladi. Kitobda ma'lumotlar strukturasi - xesh jadvalidan foydalanish taklif etiladi. Ism va qo'shnilarni o'zaro bog'lash uchun. Raqamli uchlari bilan siz oddiygina massivdan foydalanishingiz mumkin. Ushbu cho'qqilarni saqlash kitobda aytilmagan "Qo'shni cho'qqilar ro'yxati" deb ataladi. Bu ular uchun minus. Keling, buni Java-da amalga oshiramiz:

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

Endi ushbu ma'lumotlarga asoslangan qidiruvning o'zi:

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

Ko'rib turganingizdek, hech qanday murakkab narsa yo'q. Agar siz uni kitobdagi kod bilan solishtirsangiz, u deyarli bir xil.

Grafiklar, Deykstra algoritmi

BFS-ni ko'proq yoki kamroq tushungan holda, kitob muallifi bizni Daysktra algoritmi va vaznli grafiklarni tushunishga taklif qiladi. Yechim uchun quyidagi grafik taklif etiladi: Birinchidan, biz grafikalarimizni qanday ko'rsatishni tushunishimiz kerak. Biz uni matritsa sifatida ko'rsatishimiz mumkin. Habré haqidagi maqola bizga bu erda yordam beradi: Dijkstra algoritmi. Grafikda optimal marshrutlarni topish . Keling, qo'shnilik matritsasidan foydalanamiz:

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

Va endi mantiqning o'zi:

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

Kitob uni bosqichma-bosqich tasvirlab beradi. Agar siz Habré haqida Internetda maqola qo'shsangiz + kodga qarang, uni eslab qolishingiz mumkin. Men bosqichma-bosqich tahlilni biroz chalkash deb topdim. Ammo bosqichma-bosqich tabiatning o'zi uchun bu ortiqcha. Umuman olganda, yaxshi, garchi bu yaxshiroq bo'lishi mumkin edi)

Ochko'z algoritmlar

Keyingi bo'lim "ochko'z algoritmlar" ga bag'ishlangan. Bu bo'lim qiziqarli, chunki u to'plamlardan (java.util.Set) foydalanadi. Nihoyat, nima uchun kerak bo'lishi mumkinligini bilib olamiz. Kirish sifatida biz shtatlar ro'yxatidan foydalanamiz:

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

Shuningdek, ushbu shtatlarning ayrimlarini qamrab oluvchi radiostansiyalar ro'yxati:

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

Kitob algoritmning o'ziga ishora qiladi va tushuntiradi:

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

Dinamik dasturlash

Kitobda, shuningdek, "dinamik dasturlash" deb nomlangan yondashuv qo'llaniladigan muammolar tasvirlangan. Vazifa beriladi: Bizda 4 funtlik sumka bor. Berilgan vazn uchun eng foydali narsalarni topishingiz kerak. Birinchidan, keling, elementlar ro'yxatini tuzamiz:

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

Endi algoritmning o'zi:

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

Eng o'xshash so'zlarni topish uchun qiziqarli vazifa ham mavjud. Qiziq, shunday emasmi? Batafsil bu yerda: LongestCommonSubsequence.java

Eng yaqin qo'shnilarni qidiring

Kitobda k-eng yaqin qo'shnilar algoritmi haqida ham aniq aytilgan: Va hisoblash uchun formula berilgan:

Pastki chiziq

Kitob qiziqarli algoritmlarni qisqacha ko'rib chiqish imkonini beruvchi qiziqarli "Keyingi nima?" bo'limi bilan yakunlanadi. Bu erda daraxtlar va boshqa algoritmlarning ma'nosi nima ekanligini qisqacha tavsifi. Umuman olganda, kitob menga yoqdi. Bu qandaydir keng qamrovli ma'lumot sifatida jiddiy qabul qilinmasligi kerak. Siz o'zingiz izlashingiz va tushunishingiz kerak bo'ladi. Ammo qiziqtirish va dastlabki g'oyani berish uchun kirish ma'lumoti sifatida bu juda yaxshi. Ha, kitobdagi kod Pythonda yozilgan. Shunday qilib, yuqoridagi barcha misollar to'planadi) Umid qilamanki, ushbu sharh sizga kitobda nima borligi va uni sotib olishga arziydimi yoki yo'qligini tushunishga yordam beradi.

Qo'shimcha

Shuningdek, ushbu mavzu bo'yicha quyidagi manbalarni ko'rishingiz mumkin:

1. EdX - Java dasturlashiga kirish: asosiy ma'lumotlar tuzilmalari va algoritmlari
2. LinkedIn - Java-da ma'lumotlar tuzilmalari va algoritmlariga kirish (pullik)
3. Dasturlash mahoratingizni oshirish uchun jumboqlarga ega 27 sayt
4. Java CodingBat
5. Dasturchilar uchun topshiriqlar, turli murakkablikdagi vazifalarga javoblar

#Viacheslav