дебилушка взял меморимеп (автор слышал что это круто, видимо) и радикс-сорт (ну это воще круть, можно в яндекс устраиваться) и сортирует 44-гигабайтный файл за 20 минут на 16 ядрах. Потребляя при этом 64 Гб ОЗУ. Хипстер был так горд результатом, что аж пошёл всем рассказывать как он крут на хакернюс. Похоже мы окончательно перешли в эпоху, когда обезьяна видит-обезьяна делает, не понимая сути, и нормальные инженеры вымирают как класс. Дискасс.
Здравствуйте, Мирный герцог, Вы писали:
МГ>дебилушка взял меморимеп (автор слышал что это круто, видимо) и радикс-сорт (ну это воще круть, можно в яндекс устраиваться) и сортирует 44-гигабайтный файл за 20 минут на 16 ядрах. Потребляя при этом 64 Гб ОЗУ. Хипстер был так горд результатом, что аж пошёл всем рассказывать как он крут на хакернюс. Похоже мы окончательно перешли в эпоху, когда обезьяна видит-обезьяна делает, не понимая сути, и нормальные инженеры вымирают как класс. Дискасс.
Обидно за go. Его-то авторы, как раз, нормальные инженеры, все четверо.
Здравствуйте, Мирный герцог, Вы писали:
МГ>Увидел тут такое: https://github.com/afiodorov/radixmmap
МГ>дебилушка взял меморимеп (автор слышал что это круто, видимо) и радикс-сорт...
Чрезвычайно странное сочетание.
У меня 2 вопроса: нафига ему это, и почему mmf? Выбор mmf заставляет сильно сомневаться в его профессионализме: там у него последовательный доступ...
МГ>и сортирует 44-гигабайтный файл за 20 минут на 16 ядрах.
Да, очень странно: зачем ему там 16 ядер?
Я не знаю go, но тем не менее почитал, и не увидел в его коде вообще ничего про многопоточность. Кстати, синтаксис местами прикольный.
МГ>Потребляя при этом 64 Гб ОЗУ.
Ага, я туда сходил: там он сказал, что у него столько было, и он мог себе это позволить — к этому нет вопросов.
МГ>Хипстер был так горд результатом, что аж пошёл всем рассказывать как он крут на хакернюс.
Да, очень странный товарищ, хотя вроде и взрослый дядечка. Ну что ж, не многие взрослеют с годами — мудрость не то, что само по себе с годами приходит.
МГ>Похоже мы окончательно перешли в эпоху, когда обезьяна видит-обезьяна делает, не понимая сути, и нормальные инженеры вымирают как класс. Дискасс.
Может быть всё дело в том, что он блоггер?
Всё сказанное выше — личное мнение, если не указано обратное.
Здравствуйте, Мирный герцог, Вы писали:
МГ>радикс-сорт (ну это воще круть, можно в яндекс устраиваться)
А что с ним не так? Если нужно сортировать большие объемы данных, то радикс и его варианты — единственный адекватный алгоритм.
МГ>и сортирует 44-гигабайтный файл за 20 минут на 16 ядрах. Потребляя при этом 64 Гб ОЗУ.
Если можно ускорить работу алгоритма за счет большего потребления оперативки и процессорного времени — и для задачи скорость важна, то почему нет?
Здравствуйте, Codealot, Вы писали:
МГ>>радикс-сорт (ну это воще круть, можно в яндекс устраиваться)
C>А что с ним не так? Если нужно сортировать большие объемы данных, то радикс и его варианты — единственный адекватный алгоритм.
То, что влезло в RAM, как-то странно называть большим объёмом данных, даже если у кого-то очень много RAM.
Re[3]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, Sharowarsheg, Вы писали:
S>То, что влезло в RAM, как-то странно называть большим объёмом данных, даже если у кого-то очень много RAM.
Терабайт это много или мало? Нынче у машин и по терабайту рамы бывает.
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Re[4]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, CreatorCray, Вы писали:
S>>То, что влезло в RAM, как-то странно называть большим объёмом данных, даже если у кого-то очень много RAM. CC>Терабайт это много или мало? Нынче у машин и по терабайту рамы бывает.
Всё относительно, но вообще терабайт, конечно, мелочь.
Re[5]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, Мирный герцог, Вы писали:
МГ>Увидел тут такое: https://github.com/afiodorov/radixmmap
МГ>дебилушка взял меморимеп (автор слышал что это круто, видимо) и радикс-сорт (ну это воще круть, можно в яндекс устраиваться) и сортирует 44-гигабайтный файл за 20 минут на 16 ядрах. Потребляя при этом 64 Гб ОЗУ. Хипстер был так горд результатом, что аж пошёл всем рассказывать как он крут на хакернюс. Похоже мы окончательно перешли в эпоху, когда обезьяна видит-обезьяна делает, не понимая сути, и нормальные инженеры вымирают как класс. Дискасс.
Ну, не было бы у него 64 гигов оперативки, он бы может получше подумал, а так — может себе позволить. Инженеры там, где технические ограничения, а не свобода действий.
В чём он нашёл повод для гордости — не понятно конечно. MMF использовать просто для чтения файла в память — это мощно конечно.
С такими возможности по памяти я бы скорее всего считал строки в какое-нибудь бинарное дерево поиска и потом из дерева уже слил назад в файл в отсортированном виде.
Но скорее всего и этого бы не стал делать, а просто отсортировал чем-нибудь стандартным, т.к. видимо мне было бы плевать на память и продолжительность работы, а это какая-то разовая задача, чтобы через час был результат.
Re[2]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, Codealot, Вы писали:
S>>Всё относительно, но вообще терабайт, конечно, мелочь.
C>Для сортировки квиксортом это уже многовато. Если, конечно, там не 16 элементов по 64 гига каждый.
Нет, я скорее думал про терабайт 16-байтных индексов, скажем, в массив объектов суммарным размером в петабайт. Вот это интересная штука, да.
Re[2]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, karbofos42, Вы писали:
K>С такими возможности по памяти я бы скорее всего считал строки в какое-нибудь бинарное дерево поиска и потом из дерева уже слил назад в файл в отсортированном виде.
Для дофига длинных строк я бы подумал про префиксное дерево
Re[3]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, karbofos42, Вы писали:
vsb>>А как надо? По-моему очень изящное решение. Мне нравится такой подход.
K>Зачем ему MMF, если он весь файл в память читает?
Во-первых это просто очень удобно, гораздо удобней, чем руками читать. Во-вторых MMF позволяет делать swap в исходный файл.
Re[4]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, karbofos42, Вы писали:
vsb>>>А как надо? По-моему очень изящное решение. Мне нравится такой подход.
K>>Зачем ему MMF, если он весь файл в память читает?
vsb>Во-первых это просто очень удобно, гораздо удобней, чем руками читать. Во-вторых MMF позволяет делать swap в исходный файл.
Я код не смотрел, но по описанию он вроде весь файл в память загрузил, а для этого MMF никакого профита не даёт.
Собственно потребляемая память косвенно подтверждает это, а значит проще было просто прочитать всё в память и перезаписать файл отсортированным результатом без всяких телодвижений с MMF.
Там что-то про хранение начала и конца строки. Если он в файле вручную переставлял строки местами, то MMF в этом поможет, но это наркомания какая-то.
Если конечно у него 44 гига почти упорядоченных данных, в которых нужно поменять местами всего десяток строк одинаковой длины, то можно позагоняться.
В общем же случае проще и быстрее переписать весь файл, чем бегать в нему, переставляя нужные байты.
Re[2]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, Codealot, Вы писали:
C>А что с ним не так? Если нужно сортировать большие объемы данных, то радикс и его варианты — единственный адекватный алгоритм.
3 слова: внешняя сортировка слиянием. Куски до слияния можно хоть поразрядной сортировкой сортировать, хоть на несколько ядер параллелить (если RAM позволяет), хоть что делать, пока не упёрлись в I/O.
Или применить обратный подход: зная распределение данных по разрядам (нас интересует, с какого символа данные реально отличаются), распиливаем входные данные на файлы по нескольким первым разрядам, каждый файл сортируем в памяти, после этого склеиаем отсортированные файлы.
Пока все данные помещаются в оперативную память, это не большие объёмы, это баловство. Я распиливанием и слиянием 300 Гб сортировал на машине с 8 Гб.
Re[2]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, vsb, Вы писали:
vsb>А как надо? По-моему очень изящное решение. Мне нравится такой подход.
при ограничении по памяти — внешняя сортировка
при неограниченной памяти (как у автора) — прочитать файл в память, сгенерировать 1.2 млрд пар 32-битный таймстемп+указатель на начало строки, отсортировать пары хоть квиксортом по значению таймстемпов, обойти отсортированные пары по порядку и записать значения по указателю в файл (здесь уже можно использовать ммап). Итого скорость сортировки равна скорость чтения данных с диска + скорость чтения записи на диск + мизерное время сортировки (на современном железе 1.2 млрд пар отсортировалось бы за секунды).
нормально делай — нормально будет
Re[2]: Вот так вот хипстеры сейчас на го сортируют
Здравствуйте, Codealot, Вы писали:
C>А что с ним не так? Если нужно сортировать большие объемы данных, то радикс и его варианты — единственный адекватный алгоритм.
yandex finished?
как бы ты например отсортировал 2^32 32-битных целых?
