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

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

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

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

Параллельные алгоритмы

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

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

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

• Затраты ресурсов на управление параллелизмом — допустим, нужно отсортировать массив из 1000 элементов. Как разбить эту задачу для выполнения на двух ядрах? Выделить каждому ядру 500 элементов, а затем объединить два отсортированных массива в один большой отсор­тированный массив? Слияние двух массивов требует времени.

• Распределение нагрузки — допустим, необходимо выполнить 10 задач, и вы назначаете каждому ядру 5 задач. Однако ядру A достаются все простые задачи, поэтому оно выполняет свою работу за 10 секунд, тогда как ядро B справится со сложными задачами только за минуту. Это означает, что ядро A целых 50 секунд простаивает, пока ядро B выполняет всю работу! Как организовать равномерное распределение работы, чтобы оба ядра трудились с одинаковой интенсивностью?

Если вас интересует теоретическая сторона производительности и масштабируемости, возможно, параллельные алгоритмы — именно то, что вам нужно!

MapReduce

Одна разновидность параллельных алгоритмов в последнее время становится все более популярной: распределенные алгоритмы. Конечно, параллельный алгоритм удобно запустить на компьютере, если для его выполнения потребуется от двух до четырех ядер, а если нужны сотни ядер? Тогда алгоритм записывается так, чтобы он мог выполняться на множестве машин. Алгоритм MapReduce — известный представитель семейства распределенных алгоритмов. Для работы с ним можно воспользоваться популярной системой с открытым кодом Apache Hadoop.

Для чего нужны распределенные алгоритмы?

Предположим, имеется таблица с миллиардами или триллионами запи­сей и вы хотите применить к ней сложный вопрос SQL. Выполнить его в MySQL не удастся, потому что MySQL начнет «тормозить» уже после нескольких миллиардов записей. Используйте MapReduce через Hadoop!

Или, предположим, вам нужно обработать длинный список заданий. Обработка каждого задания занимает 10 секунд, всего требует обработки 1 миллион заданий. Если выполнять эту работу на одном компьютере, она займет несколько месяцев! Если бы ее можно было выполнить на 100 машинах, работа завершилась бы за несколько дней.

Распределенные алгоритмы хорошо работают в тех ситуациях, когда вам нужно выполнить большой объем работы и вы хотите сократить время ее выполнения. В основе технологии MapReduce лежат две простые идеи: функция отображения map и функция свертки reduce.

Функция map

Функция map проста: она получает массив и применяет одну функцию к каждому элементу массива. Скажем, в следующем примере происходит удваивание каждого элемента в массиве:

>>> arr1 = [1, 2, 3, 4, 5]

>>> arr2 = map(lambda x: 2 * x, arr1)

[2, 4, 6, 8, 10]

Массив arr2 теперь содержит значения [2, 4, 6, 8, 10] — все элементы arr1 увеличились вдвое! Удвоение выполняется достаточно быстро. Но представьте, что выполнение применяемой функции требует больше времени. Взгляните на следующий псевдокод:

>>> arr1 = # Список URL

>>> arr2 = map(download_page, arr1)

Имеется список URL-адресов, нужно загрузить каждую страницу и сохранить содержимое в arr2. Для каждого адреса загрузка занимает пару секунд. Для 1000 адресов потребуется пара часов! А теперь представьте, что у вас имеется 100 машин и map автоматически распределяет работу между ними. Тогда в любой момент будут загружаться сразу 100 страниц одновременно, и работа пойдет намного быстрее!

Функция reduce

Функция reduce иногда сбивает людей с толку. Идея заключается в том, что весь список элементов «сокращается» до одного элемента. Напомню, что функция map переходит от одного массива к другому.

С функцией reduce массив преобразуется в один элемент.

Пример:

>>> arr1 = [1, 2, 3, 4, 5]

>>> reduce(lambda x,y: x+y, arr1)

15