Qısqanc alqoritmlər və ya alqoritmlərə ağrısız bir giriş

"Grocking Alqoritmləri" kitabının icmalı. Bir az şəxsi fikir, bir neçə nümunə. Ümid edirəm ki, bu baxış bu kitabı oxumaq istəyib-istəmədiyinizi və ya onun rəfinizdə yerini tutmayacağını anlamağa kömək edəcək. XƏBƏRDARLIQ: Çoxlu mətn)

"Grocking Alqoritmləri" və ya Alqoritmlərə Ağrısız Giriş

Giriş

Demək olar ki, hər hansı bir Junior səviyyəli vakansiya "məlumat strukturları və alqoritmlər haqqında bilik" kimi tələblərə malikdir. İxtisas təhsili olanlar üçün alqoritmlər ümumi kursa daxildir və heç bir problem olmamalıdır. Bəs inkişaf başqa çöllərdən gətirilsəydi? Qalan tək şey öz başına öyrənməkdir. “Kim günahkardır” sualının cavabı var, amma “nə etməli” sualına cavab axtarmaq lazımdır. Gəlin kitablara baxaq. Və sizə bir şey haqqında danışmaq istəyirəm.

Grok alqoritmləri

Bütün əsərlər arasında “Grocking Alqoritmləri” kimi kitabla rastlaşdım. Daha çox məlumatı burada tapa bilərsiniz: " "Böyümə alqoritmləri. Proqramçılar və maraqlananlar üçün illüstrasiyalı bələdçi" kitabı . Kitabı çoxdan gördüm, amma ozonda 680 rubla başa gəldi. Bahalı və ya ucuz - hər kəs özü üçün qərar verir. Artıq Avitoda ikinci kitabı yarı qiymətə alıram. Ona görə də onu Sankt-Peterburqda tapdım, aldım və getdim. Hansı ki, sizinlə bölüşmək qərarına gəldim. Bəli, kitabda Java kodu yoxdur, amma... başqa kod var, lakin bu barədə daha sonra.

Alqoritmlərə Giriş (Seçimlərin Sıralaması)

Beləliklə, asan rəvayət formasında ifamızda ilk sıralamaya çatırıq. Bu Seçim Sortudur. Onun mahiyyəti ondan ibarətdir ki, biz elementləri soldan sağa (0 elementdən sonuncuya) keçirik və qalan elementlər arasında ən böyüyü axtarırıq. Əgər onu tapsaq, onda indi olduğumuz elementi və ən böyük elementi dəyişdiririk. Massiv haqqında düşünməyin ən sadə yolu: [5, 3, 6, 2, 10]. Bir kağız parçası, qələm (ən sadə və ən sərfəli yol) götürün və təsəvvür edin ki, bizdə necə sol haşiyə, cari indeks (və ya sağ sərhəd) və minimum element indeksi var. Və onunla necə işləyirik. Misal üçün: Alqoritmlər tez-tez psevdokodda təsvir olunur, məsələn, Vikipediyada. Bizimki tam olaraq psevdokod deyil, daha sonra bu barədə. Hələlik baxaq:

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

İndi onu Java kodu şəklində təqdim edək:

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

Gördüyünüz kimi kod demək olar ki, eynidir. Birinci kod kitabdan bir nümunədir. İkincisi, mənim Java kodunda pulsuz icramdır.

Rekursiya

Sonra bizə deyirlər ki, rekursiya kimi bir şey var. İlk növbədə AxB ölçüsündə tarlası olan fermerin problemi var. Bu sahəni bərabər “kvadratlara” bölmək lazımdır. Bundan sonra Evklid alqoritmi xatırlanır. Sevmədiyim odur ki, onun kodunu yazmağa cəhd etmədilər. Ancaq Evklid alqoritmi sadə və effektivdir: Düzünü desəm, bu videodakı kimi kitabda bəzi detalları qaçırdım: “ İnformatika. Alqoritmlər nəzəriyyəsi. Evklidin alqoritmi ." Məsələn, a b-dən kiçikdirsə, birinci qaçış zamanı b və a yerlərini dəyişəcək və ikinci dəfə daha böyük olan kiçikə bölünəcəkdir. Buna görə də arqumentlərin ardıcıllığı vacib deyil. Həmişə olduğu kimi, əvvəlcə alqoritmi bir kağız üzərində “hiss edə” bilərik: İndi koda baxaq:

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

Eyni kodu Java-da yazaq. İstəsəniz, onlayn tərtibçidən istifadə edə bilərik :

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

Kitabın əvvəlində faktorial da qeyd olundu. N (n!) ədədinin faktorialı 1-dən n-ə qədər olan ədədlərin hasilidir. Niyə bunu edirsən? Burada bir praktik tətbiq var. Əgər n obyektimiz varsa (məsələn, n şəhər), onda biz onlardan n ədəd edə bilərik! Kombinasiyalar. Rekursiya haqqında daha ətraflı burada oxuya bilərsiniz: " Rekursiya. Təlim tapşırıqları ." İterativ və rekursiv yanaşmaların müqayisəsi: “ Rekursiya ”.

Tez çeşidləmə

Tez çeşidləmə olduqca maraqlı bir alqoritmdir. Kitabda ona çox diqqət yetirilmir. Üstəlik, kod yalnız ilk element seçildikdə ən pis halda verilir. Ancaq bəlkə də ilk tanışlıq üçün bu nümunəni xatırlamaq daha asan olacaq. Və ümumiyyətlə yazmamaqdansa, pis növbə yazmaq daha yaxşıdır. Kitabdan bir nümunə:

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)

Burada hər şey çox sadədir. Əgər 0 və ya 1 elementli massivimiz varsa, onu çeşidləməyə ehtiyac yoxdur. Daha böyükdürsə, massivin birinci elementini götürürük və onu “pivot element” hesab edirik. Biz 2 yeni massiv yaradırıq - birində pivotdan daha böyük elementlər, ikincisində isə daha kiçik elementlər var. Və biz rekursiv təkrar edirik. Ən yaxşı seçim deyil, amma yenə də daha yaxşı xatırlanır. Gəlin bu alqoritmi Java-da tətbiq edək, amma daha düzgün. “ JavaScript-də kompüter elmləri: Quicksort ” icmalının materialı bu işdə bizə kömək edəcək . Və kodu yazmazdan əvvəl alqoritmi “hiss etmək” üçün yenidən çəkək: Əvvəlcə alqoritmi başa düşmək üçün yenidən kağız parçasına çəkək: Mənə elə gəlir ki, ən təhlükəli məqamlardan biri problemləri tamamilə həll etməkdir. Beləliklə, biz bir neçə kiçik addımda həyata keçirəcəyik:

• Massivdə elementləri dəyişdirməyi bacarmalıyıq:

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




• Göstərilən intervalda massivi 3 hissəyə bölən metoda ehtiyacımız var

  
  

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

  Təfərrüatlar yuxarıdakı linkdə. Bir sözlə, element pivotdan kiçik olana qədər sol kursoru hərəkət etdiririk. Eynilə, sağ kursoru digər tərəfdən hərəkət etdirin. Kursorlar uyğun gəlmirsə, dəyişdirmə edirik. Kursorlar birləşənə qədər davam edirik. Sonrakı emalları 2 hissəyə bölən indeksi qaytarırıq.

• Ayrılıq var, çeşidləmənin özünə ehtiyacımız var:

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

  Yəni massiv ən azı iki elementdən ibarətdirsə, onda onlar artıq sıralana bilər. Birincisi, biz bütün massivi iki hissəyə bölürük, elementləri pivotdan kiçik və daha böyük elementlər. Sonra yaranan hissələrin hər biri üçün oxşar hərəkətləri edirik.

  Və test üçün:

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

Kitabda deyilir ki, bu alqoritm işlənmiş məlumat dəsti hər dəfə yarıya bölündükdə “Böl və Qələt et” adlanan alqoritmlərə aiddir. Alqoritm mürəkkəbliyi: O(nLogn) Pis olan (yəni, bəyənmədiyim şey) kitabda keçiddə birləşmə çeşidi qeyd olunur, lakin heç bir nümunə və ya kod təqdim etmir. Ətraflı məlumatı burada tapa bilərsiniz: " İnformatika. Axtarış və çeşidləmə alqoritmləri: Birləşdirmə çeşidi ". Ona görə də ardıcıllıq naminə bunu özümüz edək. Alqoritmin özü, əlbəttə ki, mahiyyətcə sadə və sadədir:

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

Ortasını təyin edirik və massivi yarıya bölürük. Hər yarım üçün eyni şeyi edirik və s. Dayanma şərti və ya əsas vəziyyət - bir elementi ikiyə bölə bilməyəcəyimiz üçün birdən çox elementə sahib olmalıyıq. İndi birləşməni, yəni birləşməni həyata keçirməliyik:

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

Burada şərh etmək üçün çox şey yoxdur. Dəyişənlərin adlarından printlnhər şey aydındır. Yaxşı, yoxlamaq üçün:

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

Hash cədvəlləri

Kitabda hash cədvəllərinə də toxunulur. Bunu özünüz həyata keçirməyinizə ehtiyac yoxdur və hash cədvəllərinin mahiyyəti olduqca sadədir. Bütün bunlardan sonra Java da hash cədvəllərinin tətbiqinə malikdir, java.util.HashTable. HashTable cihazına baxsaq, Entry massivinin içəridə yaşadığını görərik. Giriş Açar – Dəyər birləşməsindən ibarət qeyddir. HashTable'ın başlanğıcCapacity var - yəni ilkin ölçüsü. Və loadFactor – yük faktoru. Defolt 0,75-dir. Bu rəqəm sizə massivin hansı yükündə (elementlərin sayı/ümumi kəmiyyət) ölçüsünün artırılması lazım olduğunu bildirir. Java-da 2 dəfə artır. Kitab izah edir ki, Hash cədvəlləri hash cədvəlləri adlanır, çünki hash funksiyasına əsaslanan massiv hüceyrəsi (səbət) Entry. Daha ətraflı burada oxuya bilərsiniz: Şəkillərdə məlumat strukturları. HashMap və LinkedHashMap . Bunu kitablarda da oxuya bilərsiniz. Məsələn, burada: " HashTable əsasları "

Qrafiklər, Genişlik İlk Axtarış (ən qısa yol axtarışı)

Yəqin ki, ən maraqlı mövzulardan biri qrafiklərdir. Və burada, insaf üçün, kitabda onlara çox diqqət yetirilir. Bəlkə də buna görə bu kitabı oxumağa dəyər. Baxmayaraq ki, bəlkə də, bunu bir az daha aydın ifadə etmək olardı)) Ancaq bizdə İnternet var və kitabdan əlavə, "qrafiklər haqqında ilk dəfə eşidənlər " üçün nəzəriyyədə bu pleylistə baxa bilərsiniz . ” Yaxşı, təbii ki, kitabın ən əvvəlində breadth-first-searchBFS olaraq da bilinən genişlik-birinci axtarış alqoritmi verilir. Kitabda aşağıdakı qrafik var: Kitabda növbənin bizə kömək edəcəyi bildirilir. Üstəlik, biz elementləri sonuna əlavə edə və növbəni əvvəldən emal edə bilək. Belə növbələr iki tərəfli növbələr və ya ingiliscə Deque adlanır. Kitab məlumat strukturundan - hash cədvəlindən istifadə etməyi təklif edir. Adı və qonşuları əlaqələndirmək üçün. Nömrələnmiş təpələrlə siz sadəcə olaraq massivdən istifadə edə bilərsiniz. Təpələrin bu saxlanması kitabda qeyd olunmayan “Qonşu təpələrin siyahısı” adlanır. Bu onlar üçün minusdur. Bunu Java-da həyata keçirək:

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

İndi bu məlumat əsasında axtarışın özü:

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

Gördüyünüz kimi, mürəkkəb bir şey yoxdur. Kitabdakı kodla müqayisə etsəniz, demək olar ki, eynidir.

Qrafiklər, Dijkstra alqoritmi

BFS-ni az-çox başa düşərək, kitabın müəllifi bizi Daysktra alqoritmini və çəkili qrafikləri başa düşməyə dəvət edir. Həll üçün aşağıdakı qrafik təklif olunur: Əvvəlcə qrafiklərimizi necə təmsil edəcəyimizi başa düşməliyik. Biz onu matris kimi təqdim edə bilərik. Habré haqqında məqalə burada bizə kömək edəcək: Dijkstra alqoritmi. Qrafikdə optimal marşrutların tapılması . Qonşuluq matrisindən istifadə edək:

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

İndi məntiqin özü:

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

Kitab bunu olduqca addım-addım parçalayır. İnternetdə Habré haqqında məqalə əlavə etsəniz + koduna baxsanız, onu xatırlaya bilərsiniz. Addım-addım təhlili bir az qarışıq tapdım. Ancaq addım-addım təbiətin özü üçün bu, bir artıdır. Ümumiyyətlə, yaxşı, baxmayaraq ki, daha yaxşı ola bilərdi)

Acgöz alqoritmlər

Növbəti bölmə “xəsis alqoritmlərə” həsr olunub. Bu bölmə çoxluqlardan (java.util.Set) istifadə etdiyi üçün maraqlıdır. Nəhayət, bunun nə üçün lazım ola biləcəyini görə bilərik. Giriş kimi dövlətlərin siyahısını istifadə edirik:

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

Həm də bu dövlətlərin bəzilərini əhatə edən radio stansiyalarının siyahısı:

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

Kitab alqoritmin özünü göstərməyə və izah etməyə davam edir:

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 proqramlaşdırma

Kitabda həmçinin “dinamik proqramlaşdırma” adlanan yanaşmanın tətbiq olunduğu problemlər təsvir edilir. Tapşırıq verilir: 4 lb-lıq çantamız var. Müəyyən bir çəki üçün ən sərfəli əşyaları tapmaq lazımdır. Əvvəlcə maddələrin siyahısını tərtib edək:

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

İndi alqoritmin özü:

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

Ən çox oxşar sözləri tapmaq üçün maraqlı bir tapşırıq da var. Maraqlıdır, elə deyilmi? Daha ətraflı burada: LongestCommonSubsequence.java

Ən yaxın qonşuları axtarın

Kitabda k-ən yaxın qonşular alqoritmi haqqında da çox aydın şəkildə danışılır: Və hesablama düsturu verilir:

Alt xətt

Kitab maraqlı alqoritmlərin qısa icmalını təqdim edən maraqlı “Növbəti nədir?” bölməsi ilə bitir. Burada ağacların və digər alqoritmlərin mənasının qısa təsviri verilmişdir. Ümumiyyətlə, kitabı bəyəndim. Bir növ hərtərəfli məlumat kimi ciddi qəbul edilməməlidir. Özünüz axtarıb başa düşməli olacaqsınız. Ancaq maraqlanmaq və ilkin fikir vermək üçün giriş məlumatı kimi olduqca yaxşıdır. Bəli, kitabdakı kod Python dilində yazılmışdır. Beləliklə, yuxarıda göstərilən bütün nümunələr tərtib edilə bilər) Ümid edirəm ki, bu baxış kitabın nə ehtiva etdiyi və onu almağa dəyər olub-olmadığı barədə fikir əldə etməyə kömək edəcək.

əlavə olaraq

Bu mövzuda aşağıdakı resursları da yoxlaya bilərsiniz:

1. EdX - Java Proqramlaşdırmasına Giriş: Əsas Məlumat Strukturları və Alqoritmlər
2. LinkedIn - Java-da Məlumat Strukturları və Alqoritmlərinə Giriş (ödənişli)
3. Proqramlaşdırma bacarıqlarınızı kəskinləşdirmək üçün bulmacalar olan 27 sayt
4. Java CodingBat
5. Proqramçılar üçün tapşırıqlar, müxtəlif mürəkkəblikdəki tapşırıqlara cavablar

#Viaçeslav