Viacheslav
3 уровень
Санкт-Петербург

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

Пост из группы Random
937272 участников
Обзор книги "Грокаем алгоритмы". Немного личного мнения, немного примеров. Надеюсь, данный обзор поможет понять, хочется ли вам читать данную книгу или она не займёт своё место на вашей полке. 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. Задачи для программистов, ответы на задания различной сложности
Комментарии (0)
  • популярные
  • новые
  • старые
Для того, что бы оставить комментарий вы должны авторизироваться
У этой страницы еще нет ни одного комментария