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

Видите, как дерево перекошено вправо? Эффективность такого дерева оставляет желать лучшего, потому что это дерево не сбалансировано. Существуют специальные бинарные деревья поиска, способные к самобалансировке (как, например, красно-черные деревья).

Где же используются бинарные деревья поиска? B-деревья, особая разновидность бинарных деревьев, обычно используются для хранения информации в базах данных.

Если вас интересуют базы данных или более сложные структуры данных, поищите информацию по следующим темам:

• в-деревья;

• красно-черные деревья;

• кучи;

• скошенные (splay) деревья.

Перед вами сильно упрощенное объяснение того, как работает поисковая система. Допустим, имеются три веб-страницы с простым содержимым.

Построим хеш-таблицу для этого содержимого.

Ключами хеш-таблицы являются слова, а значения указывают, на каких страницах встречается каждое слово. Теперь предположим, что пользователь ищет слово hi. Посмотрим, на каких страницах это слово встречается.

Ага, слово встречается на страницах А и B. Выведем эти страницы в результатах поиска. Или предположим, что пользователь ищет слово there. Вы знаете, что это слово встречается на страницах A и C. Несложно, верно? Это очень полезная структура данных: хеш-таблица, связывающая слова с местами, в которых эти слова встречаются. Такая структура данных, называемая инвертированным индексом, часто используется для построения поисковых систем. Если вас интересует область поиска, эта тема станет хорошей отправной точкой для дальнейшего изучения.

Преобразование Фурье — действительно выдающийся алгоритм: великолепный, элегантный и имеющий миллион практических применений. Лучшая аналогия для преобразования Фурье приводится на сайте Better Explained (отличный веб-сайт, на котором просто объясняется математическая теория): если у вас есть коктейль, преобразование Фурье сообщает, из каких ингредиентов он состоит[5]. Или для заданной песни преобразование разделяет ее на отдельные частоты.

Оказывается, эта простая идея находит множество практических применений. Например, если песню можно разложить на частоты, вы можете усилить тот диапазон, который вас интересует, — скажем, усилить низкие частоты и приглушить высокие. Преобразование Фурье прекрасно подходит для обработки сигналов. Также оно может применяться для сжатия музыки: сначала звуковой файл разбивается на составляющие. Преобразование Фурье сообщает, какой вклад вносит каждая составляющая в музыку, что позволяет исключить несущественные составляющие. Собственно, именно так работает музыкальный формат MP3!

Музыка — не единственный вид цифровых сигналов. Графический формат JPG также использует сжатие и работает по тому же принципу. Преобразование Фурье также применяется для прогнозирования землетрясений и анализа ДНК.

С его помощью можно построить аналог Shazam — приложение, которое находит песни по отрывкам. Преобразование Фурье очень часто применяется на практике. Почти наверняка вы с ним еще столкнетесь!

Следующие три темы связаны с масштабируемостью и обработкой больших объемов данных. Когда-то компьютеры становились все быстрее и быстрее. Если вы хотели, чтобы ваш алгоритм работал быстрее, можно было подождать несколько месяцев и запустить программу на более мощном компьютере. Но сейчас этот период подошел к концу. Современные компьютеры и ноутбуки оснащаются многоядерными процессорами. Чтобы алгоритм заработал быстрее, необходимо преобразовать его в форму, подходящую для параллельного выполнения сразу на всех ядрах!

Рассмотрим простой пример. Лучшее время выполнения для алгоритма сортировки равно приблизительно O(n log n). Известно, что массив невозможно отсортировать за время O(n), если только не воспользоваться параллельным алгоритмом! Существует параллельная версия быстрой сор­тировки, которая сортирует массив за время O(n).

Параллельный алгоритм трудно разработать. И так же трудно убедиться в том, что он работает правильно, и понять, какой прирост скорости он обеспечивает. Одно можно заявить твердо: выигрыш по времени не линеен. Следовательно, если процессор вашего компьютера имеет два ядра вместо одного, из этого не следует, что ваш алгоритм по волшебству заработает вдвое быстрее. Это объясняется несколькими причинами.