Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 53
Если что-то не понятно — спрашивайте в комментариях, буду править в статье на более понятное.
спасибо. познавательно :)
Если кому интересно более полностью углубиться в концепцию MapReduce, все её возможности, матбазу, которая стоит под MapReduce, и таким образом полностью осознать, какое разнообразие операций вы можете с этой технологией сотворить — есть замечательная статья Павла Самолысова. Рекомендую.
habrastorage.org/storage/e4125f40/928853e6/d0f1b749/7b3a8f6e.png
Эта статья имеет полное право на существование, но не для таких бестолковых, как я. (Автор топика)
Это все хорошо академикам и людям с докторскими степенями, а мне простому программисту нужны объяснения по-проще…
Эта статья имеет полное право на существование, но не для таких бестолковых, как я. (Автор топика)
Это все хорошо академикам и людям с докторскими степенями, а мне простому программисту нужны объяснения по-проще…
Вот блин оладушек. А у меня, по-вашему, пять научных степеней, премия Филдса, личная кафедра в MIT и жилет Вассермана.
Вы вот очень и очень неглупый человек, по топикам же видно с первого взгляда. А записи в статье ясны и доступны, если в них вдумываться, читая, а не воспринимать, как еще одну копилку из 10 примеров по HTML5.
Чуть оффтопну. Вот пришел к нам в универ первый курс только что. Сразу после ЗНО (украинский аналог ЕГЭ). Попали ребята на первую в жизни пару дискретной математики. Им начинают рассказывать про операции матлогики — конъюнкцию (&&, and) и дизъюнкцию (||, or). Ребята услышали два заумных слова, увидели на доске «страффные» значки и все, повыпадали в осадок, понять что-то даже не пытаются, с первой же пары признают, что попали в филиал ада на Земле. А мозги включить хоть на секундочку — хрен вам!
Вы вот очень и очень неглупый человек, по топикам же видно с первого взгляда. А записи в статье ясны и доступны, если в них вдумываться, читая, а не воспринимать, как еще одну копилку из 10 примеров по HTML5.
Чуть оффтопну. Вот пришел к нам в универ первый курс только что. Сразу после ЗНО (украинский аналог ЕГЭ). Попали ребята на первую в жизни пару дискретной математики. Им начинают рассказывать про операции матлогики — конъюнкцию (&&, and) и дизъюнкцию (||, or). Ребята услышали два заумных слова, увидели на доске «страффные» значки и все, повыпадали в осадок, понять что-то даже не пытаются, с первой же пары признают, что попали в филиал ада на Земле. А мозги включить хоть на секундочку — хрен вам!
А я весь первый курс и решал дискретку 20 человекам на нашем потоке («прикладная математика» в одном из Топ-10 ВУЗов столицы). Ее так никто и не понял :)
Но статья та все равно в некий ужас приводит. Может конечно соберусь и прочитаю ее, но такие статьи все же пишут академики для академиков. (До сих пор с ужасом вспоминаю как изучал самостоятельно компьютерное зрение — все эти «Возьмем переменную א» («алеф») снились… что еще хуже — даже толком не знаешь как ее искать-то эту букву, а ведь могли бы назвать «x»).
Но статья та все равно в некий ужас приводит. Может конечно соберусь и прочитаю ее, но такие статьи все же пишут академики для академиков. (До сих пор с ужасом вспоминаю как изучал самостоятельно компьютерное зрение — все эти «Возьмем переменную א» («алеф») снились… что еще хуже — даже толком не знаешь как ее искать-то эту букву, а ведь могли бы назвать «x»).
Гм. У меня вот один из Топ-3 вузов, но другой столицы — Киева, специальность «системный анализ» — реально направление то же, что у вас, математика+IT. И ничего, дискретку 80% потока нормально шарили, а 30% потока было даже интересно :)
А вообще я понял проблему. Пора исполнять свою давнишнюю мечту и писать для хабрааудитории цикл статей по theoretical computer science. Потому что как-то это неправильно, когда к любой статье с математическими символами программист относится как к недоступному кошмару, но между тем продолжает интересоваться любыми новинками своей области (ну я имею в виду серьезные вещи, тот же MapReduce, а не всякие там
Кстати, букву «алеф», насколько мне известно, впервые использовал в математике Кантор годах эдак в 1874-1884. Ему надо обозначать очень специфичные объекты — кардинальные числа (разные виды бесконечностей), и сэр очень не хотел боянить :) Поэтому выбрал изощренный алфавит — иврит. Буква так проперла некоторых математиков, что стала использоваться во всяких экстравагантных случаях :)
Если верить mraleph, от которого я впервые это услышал, то ходят слухи, что Чебышев использовал в своих работах букву «Ы».
Так что наезжать на обозначения в математике уже давно бессмысленно — что море вычерпывать =)
А вообще я понял проблему. Пора исполнять свою давнишнюю мечту и писать для хабрааудитории цикл статей по theoretical computer science. Потому что как-то это неправильно, когда к любой статье с математическими символами программист относится как к недоступному кошмару, но между тем продолжает интересоваться любыми новинками своей области (ну я имею в виду серьезные вещи, тот же MapReduce, а не всякие там
box-shadow). Однако применить эти новинки в полном объеме не может в силу невладения материалом.Кстати, букву «алеф», насколько мне известно, впервые использовал в математике Кантор годах эдак в 1874-1884. Ему надо обозначать очень специфичные объекты — кардинальные числа (разные виды бесконечностей), и сэр очень не хотел боянить :) Поэтому выбрал изощренный алфавит — иврит. Буква так проперла некоторых математиков, что стала использоваться во всяких экстравагантных случаях :)
Если верить mraleph, от которого я впервые это услышал, то ходят слухи, что Чебышев использовал в своих работах букву «Ы».
Так что наезжать на обозначения в математике уже давно бессмысленно — что море вычерпывать =)
Вот хорошо китайским математикам: привычных символов хватит для любых обозначений, сколько ни потребуется.
Ы — это круто :)
А вообще лучше конечно practical computer science. Такого вот уровня объяснения нужны: www.youtube.com/watch?v=0PahtaFK640 Кстати, пошел смотреть это именно после статьи про формат JPEG, где упоминались коды Хафмана, которые я так и не понимал что такое. Посмотрел — все понял.
А так да — такие статьи нужны! :)
А вообще лучше конечно practical computer science. Такого вот уровня объяснения нужны: www.youtube.com/watch?v=0PahtaFK640 Кстати, пошел смотреть это именно после статьи про формат JPEG, где упоминались коды Хафмана, которые я так и не понимал что такое. Посмотрел — все понял.
А так да — такие статьи нужны! :)
Я в задачах по функану использовал букву Щ )
Спасибо тебе добрый человек за статью. Наверное я ничего не понимаю в этой жизни, но мне не по себе когда пирамидальную сортировку называют MergeSort(что на самом деле совсем другая вещь: en.wikipedia.org/wiki/Merge_sort). И иметь на практики данные вида [bar, [1,1]] — может стать крайне накладно по памяти, нужно стараться начать этап reduce раньше.
Я не являюсь автором данной статьи. Так что ваше замечание лучше было бы переадресовать Павлу в Blogspot.
Скорее к автору статьи Extracting and implementing list homomorphisms in parallel program development — S. Gorlatch.
По теории MapReduce — рекомендую отчет о реинженеринге методики MapReduce (на Haskell) — Ralf Lammel Googles MapReduce Programming Model — Revisited (pdf придется поискать)
По теории MapReduce — рекомендую отчет о реинженеринге методики MapReduce (на Haskell) — Ralf Lammel Googles MapReduce Programming Model — Revisited (pdf придется поискать)
Вспомнилось как сам пытался понять что есть кластеризация, и как она работает еще не читав никаких книг и материалов, зная о ней что это — «что-то параллельное». Замечательная статья, спасибо.
Так можно ли MapReduce бесплатно пользовать?
Если никто не видит :) По идее пока что, насколько я знаю, за MapReduce никого не засудили. Но все же я бы остерегся упоминать в рекламе какой-нибудь коммерческой организации, что «мы существуем только благодаря MapReduce!» А так внутренне — думаю, что без проблем можно.
Вопрос вот о чём — где взять бесплатный кластер?
Во-первых, наверняка у Вас 2 ядра, а может и 4 — вот вам уже и кластер 4 машин :)
Во-вторых, лично я использую это для того, что 1) сложно посчитать не выйдя за пределы памяти, 2) что вообще другими методами считать сложно. Например, синонимы из второго топика.
Во-вторых, лично я использую это для того, что 1) сложно посчитать не выйдя за пределы памяти, 2) что вообще другими методами считать сложно. Например, синонимы из второго топика.
Посмотрите CouchDb
Один я считаю, что патентовать алгоритмы подобного рода в наше время — такой же маразм, как если бы Пифагор запатентовал свою формулу?
Они его в 2004 опубликовали еще. Многие фирмы держат защитные патенты — типа «не судись со мной, а то я их достану и тебя засужу». А так вопрос отмены software patents — уже который год ОЧЕНЬ ГОРЯЧИЙ.
Скажем так, если бы они его не запатентовали, то запатентовали другие бы.
И с очень большой вероятностью эти другие бы захотели бы покушать чуть чуть тортика Google :)
Да, это войны, в которых нет хороших или плохих, и будут пока не отменят патентное право на IT хотя бы (а слухи разные ходят, говорят что в U.S. может все-таки дойти до этого).
И с очень большой вероятностью эти другие бы захотели бы покушать чуть чуть тортика Google :)
Да, это войны, в которых нет хороших или плохих, и будут пока не отменят патентное право на IT хотя бы (а слухи разные ходят, говорят что в U.S. может все-таки дойти до этого).
Честно говоря, тоже очень удивлен. В ACM на это даже целый класс подобных задач есть, да и самим map и reduce в ФП бог знает сколько лет уже…
Ну если Microsoft недавно запатентовала процесс выключения операционки, то чему удивляться. :)
www.conceivablytech.com/2530/products/microsoft-patents-operating-system-shutdown/
www.conceivablytech.com/2530/products/microsoft-patents-operating-system-shutdown/
Пифагор, кстати, расространял знания только среди закрытой группы последователей, и общественным достоянием они стали спустя примерно век после его смерти.
я бы на B-деревьях пытался сделать…
правда смутно представляю сейчас как именно но…
правда смутно представляю сейчас как именно но…
Ну как бы индексы в RDMS под частую на них и делаются :)
Не забывайте, что основные задачи MapReduce — обойти ограничение по памяти и максимально запаралелить.
А с деревьями проблема, что надо дерево иметь в распоряжении во время индексирования (добавления/поиска). И если очень большое дерево или надо чтоб обработка шла одновременно на распределенной системе, деревья не оправдывают возложенных на них задач.
Не забывайте, что основные задачи MapReduce — обойти ограничение по памяти и максимально запаралелить.
А с деревьями проблема, что надо дерево иметь в распоряжении во время индексирования (добавления/поиска). И если очень большое дерево или надо чтоб обработка шла одновременно на распределенной системе, деревья не оправдывают возложенных на них задач.
Скажите, а есть ли аналогичные реализации на C++ с распределением рабочей функции по процессам?
Судя по ru.wikipedia.org/wiki/MapReduce
есть labs.trolltech.com/page/Projects/Threads/QtConcurrent
Сам не пробовал.
есть labs.trolltech.com/page/Projects/Threads/QtConcurrent
Сам не пробовал.
Спасибо, только вот эта штука, как и все остальные, которые мне удалось найти использует потоки, а не процессы.
Тогда Вы можете использовать Hadoop Streaming. Там по сути отдельно компилируется map, отдельно reduce, вход у обоих — stdin, выход — stdout. Компилировать на каком угодно языке можно. А Hadoop — он не только по процессам разделен — а может даже и по машинам.
И вот еще интересную штуку нашел:
www.craighenderson.co.uk/mapreduce/
www.craighenderson.co.uk/mapreduce/
Вы случаем между делом русский вариант aadvark не пишете? ;-) А то что-то часто слово встречается, да и википедию парсили.
Не, просто это слово, которое всегда в словарях английского первым попадалось :) Честно говоря что такое aardvark в компьютером смысле я даже и не знаю.
А Википедию я в других целях парсил — об этом тоже писал на Хабре в паре топиков "Толпы против Веб — 2:0"
А Википедию я в других целях парсил — об этом тоже писал на Хабре в паре топиков "Толпы против Веб — 2:0"
Я правильно понимаю что «миллиарды уникальных слов в википедии» это гипербола?
Ну как бы я сказал «миллиарды слов», а не «уникальных» :)
http://en.wikipedia.org/wiki/Wikipedia:Size_comparisons — 1.5 млрд слов
imonad.com/seo/wikipedia-word-frequency-list/ — около 5 млн. уникальных
imonad.com/seo/wikipedia-word-frequency-list/ — около 5 млн. уникальных
тогда не понятно при чем это в контексте map[слово] +=1
Хмм, Вы правы, там должно быть миллионы. Точнее говоря, сотни миллионов — я не исключал цифры и слова с цифрами, так что у меня получались сотни миллионов уникальных. Исправлю. Спасибо.
в 8ой строчке класса MapReduce у вас следующее:
if cur_key == prev_key or prev_key is None:
и prev_key перед циклом приравнян к None, дык как цикл сможет пойти по else если в любом случае (даже если cur_key неравно prev_key) его значение будет True?
if cur_key == prev_key or prev_key is None:
и prev_key перед циклом приравнян к None, дык как цикл сможет пойти по else если в любом случае (даже если cur_key неравно prev_key) его значение будет True?
Почему в конце не использовать пары ((-15, слово), null)? Нам ведь по-существу нужна только сортировка.
Когда-нибудь я соберусь с силами и расскажу про Flume, предварительно поняв, про что говорить можно, а про что — не стоит.
Спасибо большое, здорово и понятно :-)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
MapReduce или подсчеты за пределами возможностей памяти и процессора (попробую без зауми)