Нагруженные бэкэнды
4,0
рейтинг
3 сентября 2010 в 17:16

Разработка → MapReduce или подсчеты за пределами возможностей памяти и процессора (попробую без зауми)

Давно хотел рассказать про MapReduce, а то как ни взгляшешь на подобное — такая заумь, что просто ужас берет, а на самом деле очень простой и полезный подход для многих целей. И реализовать самому — не так уж и сложно.

Сразу скажу — топик — для тех, кто не разобрался что такое MapReduce. Для тех, кто разобрался — полезного тут ничего не будет.

Начнем с того как собственно родилась лично у меня идея MapReduce (хотя я и не знал, что он так называется, и, разумеется, пришла она мне куда позже чем Гугловсцам).

Сначала опишу как она рождалась (подход был неправильный), а потом как надо правильно делать.

Как посчитать все слова в Википедии (неправильный подход)


А родилась она, как и, наверное, везде — для подсчета частоты слов, когда обычной памяти не хватает (подсчет частоты всех слов в Википедии). Вместо слова «частота» тут скорее должно быть «количество вхождений», но для простоты оставлю «частота».

В самом простом случае мы можем завести хеш (dict, map, hash, ассоциативный массив, array() в PHP) и считать в нем слова.

$dict['word1'] += 1

Но что делать когда память под хеш кончится, а мы посчитали только одну сотую всех слов?

Я решил эту проблему тем, что считал часть слов, пока не кончится память, делал сохранение хеша на диск. То есть прямо построчно в файл:

aardvark | 5
aachen | 2


Возникла проблема — а как объединять-то эти файлы? Ведь каждый из них занимает всю оперативку.

Сначала была идея брать только самые популярные 1 000 000 слов из каждого файла и объединить их — это влезет в оперативку и посчитает хотя бы верхнюю часть списка (самые популярные слова). Это, конечно, сработало, но получилось что миллионы нижних слов терялись, а их было куда больше.

Пришла идея сортировать файлы.

Берем потом 20 сортированных файлов, читаем из каждого них первые 1000 строк, они будут примерно про одни и те же слова (отсортированные же файлы). Суммируем и формируем новый хеш, в нем будут только слова, начинающиеся на «aaa...» и подобные, сохраняем в новые файлы. Читаем следующие 1000 строк, все то же. Там примерно во всех файлах будут слова «aab...»

Таким образом формируется новый файл уже куда меньшего размера. Однако в нем все равно будут повторяться слова. Опять сортируем его, читаем его по 1000 строк, суммируем. Получится почти правильный файл (некоторые слова все же могут находится за гранью 1000 строк), еще пару раз повторяем… в конце концов получаем файл, в котором очень мало ошибок (но они есть).

Муторно, долго, но лучше варианта в голову не пришло.

Слабое место неправильного подхода

В этом подходе было одно слабое место — а именно — объединение первоначальных 20 файлов. Как его сделать лучше?

Проблема возникает из того, что некоторых слов не будет в каких-то файлах или они будут в разных блоках по 1000 строк. То есть если бы я мог из всех 20 файлов брать не первые 1000 строк, а только по одной строке, но с одним и тем же словом — я бы смог все 20 файлов объединять за один проход.



Как это сделать? Вообще это ↑ последний шаг алгоритма MergeSort — объединение сортированных списков. Если знаете — пропускайте.

Берем по первой строке из всех 20 файлов, ищем минимальный первый элемент (слово) — он будет самый минимальный вообще во всем, поскольку у нас файлы отсортированы. Допустим это будет слово «aardvark» Берем из всех 20 строк, что мы прочитали только те, которые относятся к этому слову «aardvark». А оттуда, откуда мы его изымаем — только в тех файлах читаем вторую строку. Опять ищем минимальную среди этих 20. По аналогии — дальше, пока конца всех файлов не достигнем.

MapReduce в простейшем виде


Собственно, вот я почти и изобрел для себя то, что Google изобрело до меня десятилетие назад и назвало MapReduce.

Изобретение велосипедов продолжается и по сей день.

Итак есть строка: "foo bar baz bar".

Надо получить на выходе: { foo: 1, bar: 2, baz: 1 }.

Шаг первый, берем строку, разбиваем на слова и выдаем вот такие массивы (ну или вернее: «tuples» — «кортежи»):

[ 'foo', 1 ]
[ 'bar', 1 ]
[ 'baz', 1 ]
[ 'bar', 1 ]


(Дальше буду скобочки и кавычки опускать там, где и так будет понятно)
Берем их, сортируем:

bar, 1
bar, 1
baz, 1
foo, 1


Замечаем, что bar идет два раза подряд, так что объединяем в такой вид:

bar, (1,1)
baz, (1)
foo, (1)


(1,1) — это как бы вложенный массив, то есть технически — это так: ["bar", [1,1]].

Дальше просто складываем вторые элементы массивов. Получаем:

bar, 2
baz, 1
foo, 1


Именно то, что и хотели.

Главный вопрос — нафига козе баян… или что мы тут вообще делали и зачем?

Назад в прошлое


Если представить что у нас компьютер в который влезает только 2 строки и он может выполнять только одну операцию со строкой в минуту. (Отставить хихикать! После того как хотя бы раз посчитаете все слова в Википедии — будете иметь право смеяться над поставленными ограничениями памяти, все равно не влезет, хоть у Вас сколько гигов будет, а если влезет — считайте во всем Интернете :) ).

Мы можем (из "foo bar baz bar") сделать два файла таким образом:

file1.txt
[ 'bar', 1 ]
[ 'foo', 1 ]

file2.txt
[ 'bar', 1 ]
[ 'baz', 1 ]


У нас в памяти по две строки — все в порядке, уложились в ограничения по памяти.

Теперь используя шаг из MergeSort, мы можем объединять построчно эти файлы:

bar, (1,1)
baz, (1)
foo, (1)


При этом в памяти каждый раз у нас только две строки хранятся из 2 файлов — больше и не надо.

Собственно, то, что мы сделали — это уже MapReduce.

Тот шаг, который из слов выдает массивы с единичками (слово, 1) — этот шаг называется «Map».
Тот шаг, который суммирует (1,1) — это шаг «Reduce».

Остальные шаги сделает сам алгоритм (сортировку и объединение через MergeSort).

Map, Reduce? Что это?



Сами эти шаги не обязательно заключаются в том, чтобы выдавать единички в случае «Map» или складывать в случае «Reduce». Это просто функции, которые могут что-то принять и что-то выдать. В зависимости от цели.

В данном случае «Map» — это написанная Вами функция, которая берет отдельное слово и выдает (слово, 1).

А «Reduce» — это написанная Вами функция, которая берет массив (слово, (1,1)) и выдает (слово, 2).

Проще говоря в Python:

words = ["foo", "bar", "baz"]
def map1(word):
  return [word, 1]

arr = ["foo", [1,1]]
def reduce1(arr):
  return [ arr[0], sum(arr[1]) ]


или PHP:

$words = array("foo", "bar", "baz")
function map1($word) {
  return array($word, 1);
}

arr = array("foo", array(1,1))
function reduce1(arr) {
  return array( $arr[0], array_sum($arr[1]) );
}


Итак, мы обошли ограничение по памяти, но как обойти ограничение по скорости?

Представим что у нас два таких компьютера. Каждому из них мы даем исходную строку и говорим первому (точнее MapReduce говорит): считай только слова на нечетных местах, а второму — считай слова только на четных местах.

Первый выдает:
"foo bar baz bar":
foo, 1
baz, 1


Второй выдает:
"foo bar baz bar":
bar, 1
bar, 1


Мы (точнее MapReduce) забираем результаты у обоих, сортируем, потом прогоняем через MergeSort, как и выше:

bar, (1,1)
baz, (1)
foo, (1)


Ровно тот же результат, как и когда считал один компьютер!

Теперь это мы (MapReduce) раздаем опять двум компьютерам: первому даем только нечетные строки, второму — четные и просим каждый компьютер делать шаг Reduce (сложить вторые цифры).

Собственно, понятно, что эти строки друг от друга не зависят, так что результат будет опять же тем, что нужно.

Главное в том, что два компьютера работали в параллель и следовательно — в два раза быстрее, чем один из них (если не считать потери времени на передачу данных от одного к другому).

Преждевременный вывод


Фуф! Итак MapReduce — он нужен для того, чтобы считать что-то, что либо нужно делать быстрее, либо на что не хватает памяти (либо и то, и то).

Более интересный пример — сортировка по популярности (каскады)


Допустим мы хотим посчитать количество слов в Википедии и одновременно построить список в обратном порядке их популярности — от самых популярных, к самым непопулярным.

Ясно, что все слова википедии не влезут в память, да и для обратной сортировки потом этот массив гигантский не влезет в память. Нам понадобится каскад MapReduce'ов — результат работы первого MapReduce будет поступать на вход второго MapReduce.

Если честно — я не знаю является ли слово «каскад» правильным, применимо именно к MapReduce. Это слово я использую для себя, потому что оно как никакое другое объясняет что надо сделать (результат одного водопада слов падает в MapReduce и каскадом перетекает сразу же во второй MapReduce).

Ладно, как посчитать слова — мы уже знаем:

«foo bar baz foo»

Написанный нами шаг Map выдает:
foo, 1
bar, 1
baz, 1
foo, 1


Дальше MapReduce объединяет (сам, не Вы, как программист) их в:
bar, (1)
baz, (1)
foo, (1,1)


А написанный нами шаг Reduce выдает:
bar, 1
baz, 1
foo, 2


Теперь представим, что считали мы всю Википедию и этот массив содержит миллиарды и миллиарды слов. Отсортировать его в памяти не получится. Возмем еще один MapReduce, в этот раз Map будет делать такой фокус:

[слово, 15] -> map() возвращает -> [-15, слово]
[слово2, 15] -> map() возвращает -> [-15, слово2]
[слово3, 120] -> map() возвращает -> [-120, слово3]
[слово4, 1] -> map() возвращает -> [-1, слово4]

Для чего это надо?

MapReduce, перед тем как пойдет в Ваш Reduce, — отсортирует все эти массивы по первому элементу массива (который равен отрицательному числу). MapReduce сможет отсортировать даже если весь объем данных не влезет в память все — в этом и прелесть. Для всех слов Wikipedia Вы просто не сможете сделать arsort($words), а MapReduce сможет.

Почему минус перед цифрами?

Потому что MapReduce отсортирует всегда по возрастанию, а нам надо по убыванию. Как же используя сортировку только по возрастанию отсортировать числа в порядке уменьшения? Умножить на минус один перед сортировкой и опять на минус один после.

По возрастанию положительные числа: 1, 15, 120
По возрастанию отрицательные числа: -120, -15, -1 (то что нам надо, только со знаком минус, который потом просто уберем, умножив на -1)

На вход Reduce придет такая штука:

-120, (слово3)
-15, (слово, слово2) <-- два слова на строке - MergeSort же сгруппировал все по первому ключу!
-1, (слово4)


Прелесть, но у нас два слова имели «частоту» 15 и их сгруппировал MergeSort. Будем исправлять.

Теперь нам в нашем Reduce остается только умножить первое число на -1, а затем выдать для первой строки один массив, а для второй — два массива, для третьей — опять один.

На самом деле, в зависимости от того какое воплощение MapReduce будете использовать — Вам может и не удастся в шаге Reduce выдать два массива, потому что будет требоваться только один массив на выходе — тогда просто после шага Reduce это делайте уже в своей программе.

Получаем:

120, слово3
15, слово,
15, слово2
1, слово4


Красота! То, что было надо.

Опять же помните, что главное что мы тут обходили — это то, что пример-то из четырех строк, а в Википедии миллиарды слов, которые в память не влезают.

Как сделать простейший MapReduce чтобы поиграться?


На PHP: простейший пример.
На Python простейший пример (см. ниже про Python версию).

В коде я указал что и где должно быть, чтобы сделать более-менее полноценный MapReduce с блекдж… в смысле с файлами и MergeSort'ом. Однако это так сказать эталонная реализация, который позволит поигаться и понять как MapReduce работает. Это все еще MapReduce, просто конкретно эта реализация с точки зрения памяти ничем не выгоднее обычного хеша.

Я выбрал PHP, хотя он не самый разумный для этих целей, потому что прочитать PHP может почти любой программист, а перевести на нужный язык — это уже проще будет.

Хинты и читы


Да, в файлы я рекомендую сохранять построчно JSON представление массивов (json_encode) — меньше будет проблем с пробелами в словах, с юникодом, числами и типами данных, то есть так:
["foo", 1]
["bar", 1]
["foo", 1]


Подсказка — в Python последний шаг MergeSort уже реализован — это heapq.merge(*iterables).

То есть чтобы соединить 10 файлов с JSON представлениями достаточно:

items = list(itertools.imap(json.loads, open(filename)) for filename in files)
for item in heapq.merge(*items):
  # ....reduce(item)....


В PHP с реализацией MergeSort, подозреваю надо возиться в полсотни строк. Если конечно в комментах никто лучше варианта не подскажет.

В Python yield и __iter__ для MapReduce — позволят сделать очень интересные вещи! Например такие:

x = MapReduce()
for word in "foo bar bar".split():
   x.send((word, 1))

for word, ones in x:
   print word, sum(ones)


class MapReduce — придется написать Вам самим (Я уложился в 24 строки в простейшем работающем виде, можно и меньше — упростив iter_group — это аналог функции group_tuples_by_first_element из примера для PHP).

Осторожно — такой метод не совсем классический для MapReduce и его трудно будет распараллеливать на много машин (однако довольно тривиально в этом методе сделать работу с объемами данных больше чем доступно памяти). Метод map_reduce(source_data, map1, reduce1), где map1 и reduce1 — это функции — более правильный.

Воплощение MapReduce на Hadoop — самое популярное решение. (Я его не пробовал, просто знаю что самое популярное).

Послесловие


Так что вот, надеюсь мой рассказ о «MapReduce без зауми» придется полезным.

MapReduce — очень полезная штука для всяких больших масштабов расчетов. Практически любой SQL запрос, даже на несколько таблиц — не очень сложно раскладывается на MapReduce + join_iterator (об этом в другой раз).

Если будут силы — в следующем топике опишу как с помощью MapReduce считать более интересные задачки, чем банальные слова — как, например, считать ссылки в интернете, частоту слов в контексте других слов, людей в городах, товары по прайсам сотен фирм и т.п.

Да, всем ахтунг сюда! MapReduce запатентован Google, но скорее в защитных целях — тому же Hadoop они официально разрешили использовать этот метод. Так что — handle with care.

Часть вторая: более продвинутые примеры.

Йои Хаджи,
Вид, как всегда, с Хабра,
2010

(когда-нибудь я научусь объяснять кратко....)
Слава Вишняков @yoihj
карма
660,8
рейтинг 4,0
Нагруженные бэкэнды
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (53)

  • +4
    Если что-то не понятно — спрашивайте в комментариях, буду править в статье на более понятное.
  • 0
    спасибо. познавательно :)
  • +8
    Если кому интересно более полностью углубиться в концепцию MapReduce, все её возможности, матбазу, которая стоит под MapReduce, и таким образом полностью осознать, какое разнообразие операций вы можете с этой технологией сотворить — есть замечательная статья Павла Самолысова. Рекомендую.
    • +3
      habrastorage.org/storage/e4125f40/928853e6/d0f1b749/7b3a8f6e.png

      Эта статья имеет полное право на существование, но не для таких бестолковых, как я. (Автор топика)

      Это все хорошо академикам и людям с докторскими степенями, а мне простому программисту нужны объяснения по-проще…
      • +1
        Вот блин оладушек. А у меня, по-вашему, пять научных степеней, премия Филдса, личная кафедра в MIT и жилет Вассермана.

        Вы вот очень и очень неглупый человек, по топикам же видно с первого взгляда. А записи в статье ясны и доступны, если в них вдумываться, читая, а не воспринимать, как еще одну копилку из 10 примеров по HTML5.

        Чуть оффтопну. Вот пришел к нам в универ первый курс только что. Сразу после ЗНО (украинский аналог ЕГЭ). Попали ребята на первую в жизни пару дискретной математики. Им начинают рассказывать про операции матлогики — конъюнкцию (&&, and) и дизъюнкцию (||, or). Ребята услышали два заумных слова, увидели на доске «страффные» значки и все, повыпадали в осадок, понять что-то даже не пытаются, с первой же пары признают, что попали в филиал ада на Земле. А мозги включить хоть на секундочку — хрен вам!
        • 0
          А я весь первый курс и решал дискретку 20 человекам на нашем потоке («прикладная математика» в одном из Топ-10 ВУЗов столицы). Ее так никто и не понял :)

          Но статья та все равно в некий ужас приводит. Может конечно соберусь и прочитаю ее, но такие статьи все же пишут академики для академиков. (До сих пор с ужасом вспоминаю как изучал самостоятельно компьютерное зрение — все эти «Возьмем переменную א» («алеф») снились… что еще хуже — даже толком не знаешь как ее искать-то эту букву, а ведь могли бы назвать «x»).
          • +3
            Гм. У меня вот один из Топ-3 вузов, но другой столицы — Киева, специальность «системный анализ» — реально направление то же, что у вас, математика+IT. И ничего, дискретку 80% потока нормально шарили, а 30% потока было даже интересно :)

            А вообще я понял проблему. Пора исполнять свою давнишнюю мечту и писать для хабрааудитории цикл статей по theoretical computer science. Потому что как-то это неправильно, когда к любой статье с математическими символами программист относится как к недоступному кошмару, но между тем продолжает интересоваться любыми новинками своей области (ну я имею в виду серьезные вещи, тот же MapReduce, а не всякие там box-shadow). Однако применить эти новинки в полном объеме не может в силу невладения материалом.

            Кстати, букву «алеф», насколько мне известно, впервые использовал в математике Кантор годах эдак в 1874-1884. Ему надо обозначать очень специфичные объекты — кардинальные числа (разные виды бесконечностей), и сэр очень не хотел боянить :) Поэтому выбрал изощренный алфавит — иврит. Буква так проперла некоторых математиков, что стала использоваться во всяких экстравагантных случаях :)
            Если верить mraleph, от которого я впервые это услышал, то ходят слухи, что Чебышев использовал в своих работах букву «Ы».
            Так что наезжать на обозначения в математике уже давно бессмысленно — что море вычерпывать =)
            • 0
              Вот хорошо китайским математикам: привычных символов хватит для любых обозначений, сколько ни потребуется.
            • +1
              Ы — это круто :)

              А вообще лучше конечно practical computer science. Такого вот уровня объяснения нужны: www.youtube.com/watch?v=0PahtaFK640 Кстати, пошел смотреть это именно после статьи про формат JPEG, где упоминались коды Хафмана, которые я так и не понимал что такое. Посмотрел — все понял.

              А так да — такие статьи нужны! :)
            • 0
              Я в задачах по функану использовал букву Щ )
              • 0
                И было Щастье )
    • 0
      Спасибо тебе добрый человек за статью. Наверное я ничего не понимаю в этой жизни, но мне не по себе когда пирамидальную сортировку называют MergeSort(что на самом деле совсем другая вещь: en.wikipedia.org/wiki/Merge_sort). И иметь на практики данные вида [bar, [1,1]] — может стать крайне накладно по памяти, нужно стараться начать этап reduce раньше.
      • 0
        Я не являюсь автором данной статьи. Так что ваше замечание лучше было бы переадресовать Павлу в Blogspot.
        • 0
          Скорее к автору статьи Extracting and implementing list homomorphisms in parallel program development — S. Gorlatch.

          По теории MapReduce — рекомендую отчет о реинженеринге методики MapReduce (на Haskell) — Ralf Lammel Googles MapReduce Programming Model — Revisited (pdf придется поискать)
  • 0
    Вспомнилось как сам пытался понять что есть кластеризация, и как она работает еще не читав никаких книг и материалов, зная о ней что это — «что-то параллельное». Замечательная статья, спасибо.
  • 0
    Так можно ли MapReduce бесплатно пользовать?
    • 0
      Если никто не видит :) По идее пока что, насколько я знаю, за MapReduce никого не засудили. Но все же я бы остерегся упоминать в рекламе какой-нибудь коммерческой организации, что «мы существуем только благодаря MapReduce!» А так внутренне — думаю, что без проблем можно.
      • 0
        Вопрос вот о чём — где взять бесплатный кластер?
        • 0
          Во-первых, наверняка у Вас 2 ядра, а может и 4 — вот вам уже и кластер 4 машин :)

          Во-вторых, лично я использую это для того, что 1) сложно посчитать не выйдя за пределы памяти, 2) что вообще другими методами считать сложно. Например, синонимы из второго топика.
        • 0
          Посмотрите CouchDb
  • +2
    Один я считаю, что патентовать алгоритмы подобного рода в наше время — такой же маразм, как если бы Пифагор запатентовал свою формулу?
    • +1
      Они его в 2004 опубликовали еще. Многие фирмы держат защитные патенты — типа «не судись со мной, а то я их достану и тебя засужу». А так вопрос отмены software patents — уже который год ОЧЕНЬ ГОРЯЧИЙ.
      • +1
        Это понятно, я имею в виду, что именно на данном алгоритме наглядно видна вся абсурдность такого патентования.
    • +1
      Скажем так, если бы они его не запатентовали, то запатентовали другие бы.

      И с очень большой вероятностью эти другие бы захотели бы покушать чуть чуть тортика Google :)

      Да, это войны, в которых нет хороших или плохих, и будут пока не отменят патентное право на IT хотя бы (а слухи разные ходят, говорят что в U.S. может все-таки дойти до этого).
    • 0
      Честно говоря, тоже очень удивлен. В ACM на это даже целый класс подобных задач есть, да и самим map и reduce в ФП бог знает сколько лет уже…
    • 0
      Пифагор, кстати, расространял знания только среди закрытой группы последователей, и общественным достоянием они стали спустя примерно век после его смерти.
  • +1
    я бы на B-деревьях пытался сделать…
    правда смутно представляю сейчас как именно но…
    • 0
      Ну как бы индексы в RDMS под частую на них и делаются :)

      Не забывайте, что основные задачи MapReduce — обойти ограничение по памяти и максимально запаралелить.

      А с деревьями проблема, что надо дерево иметь в распоряжении во время индексирования (добавления/поиска). И если очень большое дерево или надо чтоб обработка шла одновременно на распределенной системе, деревья не оправдывают возложенных на них задач.
  • 0
    Скажите, а есть ли аналогичные реализации на C++ с распределением рабочей функции по процессам?
    • 0
      Судя по ru.wikipedia.org/wiki/MapReduce
      есть labs.trolltech.com/page/Projects/Threads/QtConcurrent
      Сам не пробовал.
      • 0
        Спасибо, только вот эта штука, как и все остальные, которые мне удалось найти использует потоки, а не процессы.
        • 0
          Тогда Вы можете использовать Hadoop Streaming. Там по сути отдельно компилируется map, отдельно reduce, вход у обоих — stdin, выход — stdout. Компилировать на каком угодно языке можно. А Hadoop — он не только по процессам разделен — а может даже и по машинам.
        • 0
          И вот еще интересную штуку нашел:
          www.craighenderson.co.uk/mapreduce/
          • 0
            Хотя она, скорее всего, все же на потоках.
  • 0
    Вы случаем между делом русский вариант aadvark не пишете? ;-) А то что-то часто слово встречается, да и википедию парсили.
    • 0
      Не, просто это слово, которое всегда в словарях английского первым попадалось :) Честно говоря что такое aardvark в компьютером смысле я даже и не знаю.

      А Википедию я в других целях парсил — об этом тоже писал на Хабре в паре топиков "Толпы против Веб — 2:0"
  • 0
    Я правильно понимаю что «миллиарды уникальных слов в википедии» это гипербола?
    • 0
      Ну как бы я сказал «миллиарды слов», а не «уникальных» :)
      • 0
        http://en.wikipedia.org/wiki/Wikipedia:Size_comparisons — 1.5 млрд слов
        imonad.com/seo/wikipedia-word-frequency-list/ — около 5 млн. уникальных
      • +1
        тогда не понятно при чем это в контексте map[слово] +=1
        • 0
          Хмм, Вы правы, там должно быть миллионы. Точнее говоря, сотни миллионов — я не исключал цифры и слова с цифрами, так что у меня получались сотни миллионов уникальных. Исправлю. Спасибо.
          • 0
            И даже если быть еще точнее — я считал н-граммы (словосочетания), вот поэтому у меня сотни миллионов и выходили.
            • 0
              ну я просто прикидывал так что в одном языке даже со всеми реально используемыми словоформами эта цифра может быть оценена сверху как «все слова» * 10.
          • 0
            сотни миллионов верю — в подобной оценке сомнений нет :)
  • 0
    в 8ой строчке класса MapReduce у вас следующее:
    if cur_key == prev_key or prev_key is None:
    и prev_key перед циклом приравнян к None, дык как цикл сможет пойти по else если в любом случае (даже если cur_key неравно prev_key) его значение будет True?
    • 0
      Значение условия «if cur_key == prev_key or prev_key is None:» всегда будет True
      • 0
        А Вы строку 14 не пропустили при просмотре?
        • +1
          ой да и правда :) но всеравно статья хорошая :)
  • +1
    Почему в конце не использовать пары ((-15, слово), null)? Нам ведь по-существу нужна только сортировка.
    • 0
      Да, в принципе, можно!
  • 0
    Когда-нибудь я соберусь с силами и расскажу про Flume, предварительно поняв, про что говорить можно, а про что — не стоит.
  • 0
    Спасибо большое, здорово и понятно :-)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.