Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.
Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.

«Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих.»
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, пора изменять размер хеш-таблицы.
  • Хеш-таблицы используются для кеширования данных
  • Хеш-таблицы хорошо подходят для обнаружения дубликатов.

 

 

Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

Добавить комментарий