“Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.”
Aditya Y. Bhargava / Адитья Бхаргава
Алгоритмы – это всего лишь пошаговые инструкции решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузится в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу и вы сразу поймете, что алгоритмы – это просто. А грокать алгоритмы – это веселое и увлекательное занятие.
Первая мною прочитанная книга в стиле т.н. “деских объяснялок”. Очень и очень впечатляет.
Материал изобилует иллюстрациями, примерами, упражнениями и действительно доходчивым описание основных алгоритмов. При этом автор не поленился указать в каких областях наиболее востребованы и привести большой ряд ссылок на более сложные или специализированные алгоритмы (например фильтры Блума, преобразование Фурье, алгоритм Диффи-Хеллмана.
Книга легко читается в дороге, часть примеров и задач – вполне проходимы в путевых условиях.
Весьма полезна для разработчиков и технических манагеров, которые хотят разобраться со спецификой, в т.ч. поисковых систем, больших данных и машинного обучения.
Примеры (Python 2.7): https://github.com/egonSchiele/grokking_algorithms
Шпаргалка.
Глава 1:
- Бинарный поиск работает намного быстрее простого.
- Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.
- Скорость алгоритмов не измеряется в секундах.
- Время выполнения алгоритма описывается ростом количества операций.
- Время выполнения алгоритмов выражается как “О-большое“
Глава 2:
- Память компьютера напоминает огромный шкаф с ящиками.
- Если требуется сохранить набор элементов, используют массив или список.
- В массиве все элементы хранятся рядом друг с другом
- В списке элементы распределяются в произвольных местах памяти, при этом в одном элементе хранится адрес следующего
- Массивы обеспечивают быстрое чтение
- Списки обеспечивают быструю вставку и выполнение
- Все элементы массива должны быть однотипными
Глава 3:
- Когда функция вызывает саму себя, это называется рекурсией
- В каждой рекурсивной функции должно быть два случая: базовый и рекурсивный
- Стек поддерживает две операции: занесение и извлечение элементов
- Все вызовы функций сохраняются в стеке вызовов
- Если стек вызовов станет очень большим, он займет слишком много памяти (переполнение стека).
Глава 4:
- Стратегия “разделяй и властвуй” основана на разбиении задачи на уменьшающиеся фрагменты. Если вы используете стратегию “разделяй и властвуй” со списком, то базовым случаем, скорее всего, будет пустой массив или массив из одного элемента.
- Если вы реализуете алгоритм быстрой сортировки, выберите в качестве опорного случайный элемент. Среднее время выполнения быстрой сортировки составляет O(n log n)
- Константы в “О-большое” иногда могут иметь значение. Именно по этой причине быстрая сортировка быстрее сортировки слиянием.
- При сравнении простой сортировки с бинарной константа почти никогда роли не играет, потому что O(log n) слишком сильно превосходит O(n) по скорости при большом размере списка.
Глава 5:
- Хеш-таблица создается объединением хеш-функции с массивом
- Коллизии нежелательны. Хеш-функция должна свести к минимуму количество коллизий
- Хеш-таблицы обеспечивают очень быстрое выполнение поиска, вставки и удаления.
- Хеш-таблицы хорошо подходят для моделирования отношений между объектами
- Как только коэффициент заполнения превышает 0.7, пора изменять размер хеш-таблицы.
- Хеш-таблицы используются для кеширования данных
- Хеш-таблицы хорошо подходят для обнаружения дубликатов.