Грокаємо алгоритми або безболісне введення в алгоритми

Огляд книги "Грокаємо алгоритми". Небагато особистих думок, трохи прикладів. Сподіваюся, цей огляд допоможе зрозуміти, чи хочеться читати цю книгу і чи вона не займе своє місце на вашій поличці. WARNING: Дуже багато тексту)

"Грокаємо алгоритми" або безболісне введення в алгоритми

Вступ

Практично будь-яка вакансія рівня Junior має вимоги виду "знання структур даних та алгоритмів". У кого є профільна освіта, то алгоритми входять до загального курсу і проблем не повинно бути. Але що якщо у розробку занесло з інших степів? Залишається лише вчитися самому. На запитання "хто винний" відповідь є, а ось на питання "що робити" відповідь треба шукати. Шукатимемо у книгах. І про одну хочу розповісти.

Введення у алгоритми (Сортування вибором)

Отже, у легкій формі оповідання ми доходимо до першого у нашому виконанні сортування. Це сортування вибором (Selection Sort). Суть її полягає в тому, що ми йдемо по елементах зліва направо (від 0 елемента до останнього), і шукаємо серед елементів, що залишаються, найбільший. Якщо знаходимо, то міняємо місцями елемент, на якому ми зараз найбільший елемент. Найпростіший спосіб спочатку уявити собі масив: [5, 3, 6, 2, 10]. Взяти листочок, ручку (найпростіший і бюджетний спосіб) і уявити, як ми маємо ліву межу (left), поточний індекс (або правий кордон), є індекс мінімального елемента. І як ми із цим працюємо. Часто алгоритми описують у псевдокоді, наприклад, на вікіпедії. У нас не зовсім псевдокод, але про це дещо пізніше. А поки що подивимося:

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

А тепер представимо його у вигляді 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;
            }
        }
}

Як бачимо, код майже не відрізняється. Перший код – приклад із книги. Друге — моє вільне виконання у Java коді.

Рекурсія

Далі нам розповідають про те, що є така штука як рекурсія. Перш за вс, наводиться питання для фермера, у якого є поле розміру AxB. Потрібно це поле розбити на рівні квадрати. І тоді після цього згадується Алгоритм Евкліда. Що мені не подобається, то це те, що не спробували написати його код. А алгоритм Евкліда простий і ефективний, загугліть. Якщо чесно, мені не вистачило в книзі деяких подробиць. Наприклад, про те, що якщо a буде менше b, то при першому прогоні b і a поміняються місцями і вдруге більше ділитися на менше. Тому порядок аргументів не важливий. Як завжди, спочатку ми можемо алгоритм помацати на папірці: А тепер подивимося на код:

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

Цей код напишемо на Java. За бажанням можемо скористатися онлайн-компілятором:

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

На початку книги також згадувався факторіал. Факторіал числа n (n!) – це добуток чисел від 1 до n. Навіщо робити це? Тут є одне практичне застосування. Якщо ми маємо n об'єктів (наприклад, n міст), ми можемо скласти з них n! Комбінацій.

Швидке сортування

Швидке сортування – досить цікавий алгоритм. У книзі йому не дуже багато уваги приділено. Більше того, код наведено лише для найневдалішого випадку, коли вибирається перший елемент. Втім, можливо, для першого знайомства цей приклад запам'ятається легше. І краще написати погане швидке сортування, ніж не написати ніяке. Ось приклад із книги:

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)

Тут все просто. Якщо у нас масив із 0 або 1 елемента – його сортувати не потрібно. Якщо більше – ми беремо перший елемент масиву та вважаємо його опорним елементом. Складаємо 2 нових масиву – один містить елементи більші ніж pivot, а другий – елементи менші. І повторюємо рекурсивно. Не найкращий варіант, але знову ж таки, запам'ятовується краще. Давайте реалізуємо Java цей алгоритм, але більш правильно. Для початку, знову помалюємо на папірці, щоб усвідомити алгоритм: Мені здається, один із найнебезпечніших моментів – вирішувати завдання цілком. Тому виконаємо реалізацію як кілька маленьких етапів:

• Нам потрібно вміти міняти місцями елементи у масиві:

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

• Нам потрібний метод, який ділить масив у зазначеному проміжку на 3 частини

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

  Якщо коротко, то рухаємо лівий курсор, доки елемент менший ніж pivot. Аналогічно рухаємо з іншого кінця правий курсор. І робимо свап, якщо курсори не зійшлися. Продовжуємо поки що курсори не зійшлися. Повертаємо індекс, який поділяє подальшу обробку на 2 частини.

• Поділ є, потрібне саме сортування:

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

  Тобто якщо масив складається як мінімум з двох елементів, то їх вже можна відсортувати. Спочатку ділимо весь масив на дві частини, менші ніж pivot елементи та більші. Потім аналогічні дії виконуємо і кожної з отриманої частин.

  І для тесту:

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

У книзі зазначено, що даний алгоритм відноситься до так званих алгоритмів «Розділяй і володарюй», коли набір даних, що обробляється, щоразу ділиться навпіл. Складність алгоритму: O(nLogn) Що погано (тобто що мені не сподобалося), що в книзі згадується побіжно сортування злиттям (merge sort), але не наводиться жодного прикладу чи коду. Тому давайте для послідовності самі зробимо. Сам алгоритм, звичайно, за своєю суттю простий і нехитрий:

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

Визначаємо середину і ділимо масив навпіл. Для кожної половини виконуємо те саме і так далі. Умова зупинки чи базовий випадок – у нас має бути більше одного елемента, оскільки один елемент на два ми не розділимо. Тепер потрібно реалізувати злиття, тобто merge:

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

Тут коментувати особливо нема чого. З назв змінних і printlnвсе зрозуміло. Ну і для перевірки:

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

Хеш-таблиці

У книзі також торкнулися хеш-таблиці. Реалізовувати самим не доводиться, та й суть хеш-таблиць досить проста. Адже Java теж є реалізація хеш-таблиць, java.util.HashTable. Якщо подивитися на HashTable, ми побачимо, що всередині живе масив Entry. Entry – це деякий запис, що є зв'язуванням Key – Value. HashTable має initialCapacity – тобто початковий розмір. І loadFactor – коефіцієнт завантаження. За замовчуванням дорівнює 0.75. Це число каже, при якому завантаженні масиву (кількість елементів/загальна кількість) необхідно збільшити розмір. У Java він збільшується вдвічі. У книзі розповідається, що Hash-таблиці хеш-таблицями називаються тому, що на основі хеш-функції обчислюється осередок масиву (кошик), в який будуть поміщені Entry.

Графи, Пошук у ширину (пошук найкоротшого шляху)

Напевно, одна із найцікавіших тем – це графи. І тут у книзі приділено їм багато уваги. Можливо, заради цього варто прочитати цю книгу. Хоча, можливо, можна було б викласти трохи зрозуміліше)) Ну, і природно, на самому початку книги дається алгоритм пошуку завширшки, breadth-first-search, він же BFS. У книзі наведено такий граф: У книзі вказано, що нам допоможе черга. Причому така, щоб ми могли додавати елементи до кінця, а обробляти чергу з початку. Такі черги називаються двосторонніми, або Deque англійською. У книзі пропонують скористатися структурою даних – hash-таблиця. Щоб співвідносити ім'я та сусідів. При нумерованих вершинах використовувати можна просто масив. Таке зберігання вершин називається Список суміжних вершин, що у книзі не сказано. За це їм мінус. Реалізуємо це на Java:

private Map getGraph() {
    Map 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;
}

Тепер і сам пошук, побудований на цих даних:

private String search() {
    Map graph = getGraph();
    Set searched = new HashSet<>();
    Deque 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;
}

Очевидно, нічого складного. Якщо порівняти з кодом із книги, то майже те саме.

Графи, Алгоритм Дейкстри

Розібравшись з BFS автор книги пропонує нам розібратися з алгоритмом Дейкстри і зваженими графами. Для вирішення пропонується такий граф: Для початку потрібно зрозуміти, як уявити наші графи. Ми могли б подати їх у вигляді матриці. Скористаємося матрицею суміжності:

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

А тепер сама логіка:

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

У книзі досить покроково описано. Якщо в інтернеті почитати трохи більше і подивитись на код, можна запам'ятати. Мені покроковий розбір здався дещо захаращеним. Але за саму покроковість плюс. В цілому, нормально, хоча могло бути і краще.

Жадібні алгоритми

Наступний розділ присвячується "жадібним алгоритмам". Цей розділ цікавий тим, що він використовує множину (java.util.Set). Нарешті видно, навіщо воно може знадобитися. Як вхідні дані використовуємо список штатів:

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

А також список радіостанцій, що покривають деякі з цих штатів:

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

Далі у книзі вказується і пояснюється сам алгоритм:

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

Динамічне програмування

У книзі також описується такі завдання, до яких застосовується підхід під назвою "динамічне програмування". Дається завдання: У нас є мішок місткістю 4 фунти. Потрібно знайти максимально вигідні предмети для цієї ваги. Для початку складемо список предметів:

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

Тепер сам алгоритм:

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

Також наведено цікаве завдання на пошук найбільш схожих слів. Цікаво, чи не так? Детальніше тут: LongestCommonSubsequence.java.

Пошук найближчих сусідів

Також у книзі дуже наочно розповідає про алгоритм k найближчих сусідів: І наводиться формула для розрахунку:

Підсумок

Книга закінчується цікавим розділом "Що далі?", В якому представлений огляд цікавих алгоритмів. Тут коротко описано, у чому полягає сенс дерев та інших алгоритмів. Загалом книга мені сподобалася. Її не варто серйозно сприймати як якусь вичерпну інформацію. Вам доведеться самим шукати і розуміти. Але як вступна інформація, щоб зацікавити і дати початкове розуміння — цілком непогано. Сподіваюся, цей огляд допоможе скласти уявлення про наповнення книги і про те, чи варто її купувати.

Додатково

Можна також ознайомитися з такими ресурсами:

1. EdX — Introduction to Java Programming: Fundamental Data Structures and Algorithms
2. LinkedIn — Introduction to Data Structures & Algorithms in Java
3. 27 сайтів із завданнями для відточування навичок програмування
4. Java CodingBat