Обзор книги "Грокаем алгоритмы". Немного личного мнения, немного примеров. Надеюсь, данный обзор поможет понять, хочется ли вам читать данную книгу или она не займёт своё место на вашей полке. 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 элементы и большие. Потом аналогичные действия выполняем и для каждой из полученной частей.
В книге указано, что данный алгоритм относится к так называемым алгоритмам «Разделяй и властвуй», когда обрабатываемый набор данных каждый раз делится пополам. Сложность алгоритма: 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 всё понятно.
Ну и для проверки:
В книге также затронуты хэш-таблицы. Реализовывать самим не приходится, да и суть хэш-таблиц довольно проста. Ведь в 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 автор книги предлагает нам разобраться с алгоритмом Дейсктры и взвешенными графами. Для решения предлагается следующий граф:
@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). Наконец-то видно, зачем оно может понадобится.
Как входные данные используем список штатов:
А также список радиостанций, покрывающих некоторые из этих штатов:
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 ближайших соседей:
И приводится формула для расчёта:
Итог
Книга заканчивается интересным разделом "Что дальше?", в котором представлен беглый обзор интересных алгоритмов. Тут кратко описано, в чём заключается смысл деревьев и других алгоритмов. В целом - книга мне понравилась. Её не стоит серьёзно воспринимать, как какую-то исчерпывающую информацию. Вам придётся самим искать и допонимать. Но как вводная информация, чтобы заинтересовать и дать начальное представление - вполне неплохо. Да, код в книге написан на питоне. Так что все указанные примеры компилируемы)
Надеюсь, данный обзор поможет составить представление о наполнении книги и о том, стоит ли её покупать.
Дополнительно
В тему можно так же ознакомиться со следующими ресурсами:
В графах, чтобы не добавлять в очередь уже проверенных людей, после строки
searchQue.addLast(friend);
надо добавить
searched.add(friend);
Об этом даже компилятор подсказывает
То ли я что-то уже намудрил в создании графа и в небольших исправлениях под себя, то ли описанный в статье алгоритм Дейкстры на джава не корректно работает для графа с приложенного рисунка
Спасибо за статью, в алгоритме Быстрой сортировки из книги ошибка:
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)
а именно:
less = [i for i in array[1:] if i <= pivot]
всегда будет падать в бесконечную рекурсию, т.к. если подать массив, например, такой:
{3, 1, 1, 4, 6, 7}
тогда при разделении часть:
{3, 1, 1}
никогда не даст 1 элемент.
Просьба прокомментировать.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ