Page 262 - Bkhargava_-_Grokaem_algoritmy

MapReduce 261

MapReduce

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

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

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

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

Функция map

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

>>> arrl = [1, 2, З, 4, 5]
>>> arr2 = map(lambda х: 2 * х, arrl)
[2, 4, б, 8, 10]

www.trk.kg