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

БИНАРНОЕ. ДЕРЕВО ПОИСКА
ОСЦуО О 0-°з "О



У
бинарных деревьев поиска есть и свои недостатки: во-первых, они не под­держивают произвольный доступ. Вы не сможете потребовать: «Выдайте мне i-й элемент этого дерева». Кроме того, в таблице приведено среднее время выполнения операций; оно зависит от сбалансированности дерева. Допустим, ваше дерево не сбалансировано, как на следующем рисунке.
Видите, как дерево перекошено вправо? Эффективность такого дерева оставляет желать лучшего, потому что это дерево не сбалансировано. Су­ществуют специальные бинарные деревья поиска, способные к самобалан­сировке (как, например, красно-черные деревья).
Где же используются бинарные деревья поиска? В-деревья, особая разно­видность бинарных деревьев, обычно используются для хранения инфор­мации в базах данных.
Если вас интересуют базы данных или более сложные структуры данных, поищите информацию по следующим темам:

• 
  в-деревья:
  
• 
  красно-черные деревья;
  
• 
  кучи;
  
• 
  скошенные (splay) деревья.
  

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

HI	А,е>
1 THEM	А. С
) ADIT	&
| (36	С
	С

остроим хеш-таблицу для этого содержимого.
Ключами хеш-таблицы являются слова, а значения указывают, на каких страницах встречается каждое слово. Теперь предположим, что пользователь ищет слово hi. Посмотрим, на каких страницах это слово встречается.
Ага, слово встречается на страницах А и В. Выведем эти страницы в ре­зультатах поиска. Или предположим, что пользователь ищет слово there. Вы знаете, что это слово встречается на страницах А и С. Несложно, верно? Это очень полезная структура данных: хеш-таблица, связывающая слова с местами, в которых эти слова встречаются. Такая структура данных, на­зываемая инвертированным индексом, часто используется для построения поисковых систем. Если вас интересует область поиска, эта тема станет хорошей отправной точкой для дальнейшего изучения.
Преобразование Фурье
Преобразование Фурье — действительно выдающийся алгоритм: вели­колепный, элегантный и имеющий миллион практических применений. Лучшая аналогия для преобразования Фурье приводится на сайте Better Explained (отличный веб-сайт, на котором просто объясняется математиче­ская теория): если у вас есть коктейль, преобразование Фурье сообщает, из каких ингредиентов он состоит¹. Или для заданной песни преобразование разделяет ее на отдельные частоты.
Оказывается, эта простая идея находит множество практических приме­нений. Например, если песню можно разложить на частоты, вы можете усилить тот диапазон, который вас интересует, — скажем, усилить низкие частоты и приглушить высокие. Преобразование Фурье прекрасно под­ходит для обработки сигналов. Также оно может применяться для сжатия музыки: сначала звуковой файл разбивается на составляющие. Преобразо­вание Фурье сообщает, какой вклад вносит каждая составляющая в музыку, что позволяет исключить несущественные составляющие. Собственно, именно так работает музыкальный формат MP3!
Музыка — не единственный вид цифровых сигналов. Графический фор­мат JPG также использует сжатие и работает по тому же принципу. Преоб­разование Фурье также применяется для прогнозирования землетрясений и анализа ДНК.
С его помощью можно построить аналог Shazam — приложение, которое на­ходит песни по отрывкам. Преобразование Фурье очень часто применяется на практике. Почти наверняка вы с ним еще столкнетесь!
' Kalid, «Ап Interactive Guide to the Fourier Transform,» Better Explained, http://mng. bx/874X.
Параллельные алгоритмы
Следующие три темы связаны с масштабируемостью и обработкой больших объемов данных. Когда-то компьютеры становились все быстрее и быстрее. Если вы хотели, чтобы ваш алгоритм работал быстрее, можно было подо­ждать несколько месяцев и запустить программу на более мощном компью­тере. Но сейчас этот период подошел к концу. Современные компьютеры и ноутбуки оснащаются многоядерными процессорами. Чтобы алгоритм заработат быстрее, необходимо преобразовать его в форму, подходящую для параллельного выполнения сразу на всех ядрах!
Рассмотрим простой пример. Лучшее время выполнения для алгоритма сортировки равно приблизительно 0(п log п). Известно, что массив не­возможно отсортировать за время 0(п), если только не воспользоваться параллельным алгоритмом! Существует параллельная версия быстрой сор­тировки, которая сортирует массив за время 0(п).
Параллельный алгоритм трудно разработать. И так же трудно убедиться в том, что он работает правильно, и понять, какой прирост скорости он обеспечивает. Одно можно заявить твердо: выигрыш по времени не линеен. Следовательно, если процессор вашего компьютера имеет два ядра вместо одного, из этого не следует, что ваш алгоритм по волшебству заработает вдвое быстрее. Это объясняется несколькими причинами.

• 
  Затраты ресурсов на управление параллелизмом — допустим, нужно отсортировать массив из 1000 элементов. Как разбить эту задачу для выполнения на двух ядрах? Выделить каждому ядру 500 элементов, а затем объединить два отсортированных массива в один большой отсор­тированный массив? Слияние двух массивов требует времени.
  
• 
  Распределение нагрузки — допустим, необходимо выполнить 10 задач, и вы назначаете каждому ядру 5 задач. Однако ядру А достаются все простые задачи, поэтому оно выполняет свою работу за 10 секунд, тогда как ядро В справится со сложными задачами только за минуту. Это оз­начает, что ядро А целых 50 секунд простаивает, пока ядро В выполняет всю работу! Как организовать равномерное распределение работы, чтобы оба ядра трудились с одинаковой интенсивностью?
  

Если вас интересует теоретическая сторона производительности и мас­штабируемости, возможно, параллельные алгоритмы — именно то, что вам нужно!
MapReduce
Одна разновидность параллельных алгоритмов в последнее время становит­ся все более популярной: распределенные алгоритмы. Конечно, параллель­ный алгоритм удобно запустить на компьютере, если для его выполнения потребуется от двух до четырех ядер, а если нужны сотни ядер? Тогда ал­горитм записывается так, чтобы он мог выполняться на множестве машин. Алгоритм MapReduce — известный представитель семейства распределен­ных алгоритмов. Для работы с ним можно воспользоваться популярной системой с открытым кодом Apache Hadoop.
Для чего нужны распределенные алгоритмы?
Предположим, имеется таблица с миллиардами или триллионами запи­сей и вы хотите применить к ней сложный вопрос SQL. Выполнить его в MySQL не удастся, потому что MySQL начнет «тормозить» уже после нескольких миллиардов записей. Используйте MapReduce через Hadoop!
Или, предположим, вам нужно обработать длинный список заданий. Об­работка каждого задания занимает 10 секунд, всего требует обработки 1 миллион заданий. Если выполнять эту работу на одном компьютере, она займет несколько месяцев! Если бы ее можно было выполнить на 100 ма­шинах, работа завершилась бы за несколько дней.
Распределенные алгоритмы хорошо работают в тех ситуациях, когда вам нужно выполнить большой объем работы и вы хотите сократить время ее выполнения. В основе технологии MapReduce лежат две простые идеи: функция отображения тар и функция свертки reduce.
Функция тар
Функция тар проста: она получает массив и применяет одну функцию к каждому элементу массива. Скажем, в следующем примере происходит удваивание каждого элемента в массиве:
>>> arrl = [1, 2, 3, 4j 5]