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

«Грокаем алгоритмы» или безболезненное введение в алгоритмы

Введение

Практически любая вакансия уровня Junior имеет требования вида «знание структур данных и алгоритмов». У кого есть профильное образование, то алгоритмы входят в общий курс и проблем быть не должно. Но что если в разработку «занесло» из других степей? Остаётся только учиться самому. На вопрос «кто виноват» ответ есть, а вот на вопрос «что делать» ответ надо искать. Будем искать в книгах. И про одну я хочу рассказать.

Грокаем алгоритмы

Наткнулся среди всех трудов на такую книгу, как «Грокаем алгоритмы». Подробнее можно будет узнать тут: "Книга «Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих". Книгу приметил давно, но на озоне она стоила 680 рублей. Дорого или дёшево – каждый решает для себя сам. Я уже вторую книгу на авито беру за пол цены. Так что нашёл её в СПб, купил, и пошёл грокать. О чём и решил поделиться с Вами. Да, в книге нет кода на Java, но есть… другой код, но об этом позже.

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

Итак, в лёгкой форме повествования мы доходим до первой в нашем исполнении сортировки. Это сортировка выбором (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 этот алгоритм, но более правильно. В этом нам поможет материал из обзора «Информатика в JavaScript: Быстрая сортировка (Quicksort)». И прежде чем писать код, снова порисуем, чтобы «ощутить» алгоритм: Для начала, опять порисуем на бумажке, чтобы осознать алгоритм:
Мне кажется, один из самых опасных моментов – решать задачи целиком. Поэтому, выполним реализацию как несколько маленьких этапов:
  • Нам нужно уметь менять местами элементы в массиве:


    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 он увеличивается в 2 раза. В книге рассказывается, что Hash-таблицы хэш-таблицами называются потому, что на основе хэш-функции вычисляется ячейка массива (корзина), в которую будут помещены Entry. Подробнее можно прочитать так же здесь: Структуры данных в картинках. HashMap и LinkedHashMap. А так же можно прочитать в книгах. Например, здесь: "HashTable basics"

Графы, Поиск в ширину (поиск кратчайшего пути)

Наверно, одна из самых интересных тем – это графы. И тут, надо отдать должно, в книге уделено им много внимания. Возможно, ради этого стоит прочитать эту книгу. Хотя, возможно, можно было бы изложить чуть понятнее )) Но, у нас есть интернет и в добавку к книге можно посмотреть вот этот плэйлист по теории для «впервые слышащих о графах». Ну, и естественно, в самом начале книги даётся алгоритм поиска в ширину, breadth-first-search, он же BFS. В книге приведён следующий граф:
В книге указано, что нам поможет очередь. Причём такая, чтобы мы могли добавлять элементы в конец, а обрабатывать очередь с начала. Такие очереди называются двусторонними или Deque на английском. В книге предлагают воспользоваться структурой данных – hash-таблица. Чтобы соотносить имя и соседей. При нумерованных вершинах, использовать можно просто массив. Такое хранение вершин называется «Список смежных вершин», о чём в книге не сказано. За этом им минус. Реализуем это на 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;
}
Теперь и сам поиск, построенный на этих данных:
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;
}
Как видно, ничего сложного. Если сравнить с кодом из книги, то почти тоже самое.

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

Разобравшись более менее с 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<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);

Динамическое программирование

В книге так же описывается такие задачи, к которым применяется подход, называемый «динамическим программированием». Даётся задача:
У нас есть мешок вместимостью 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
  5. Задачи для программистов, ответы на задания различной сложности
#Viacheslav