Здравствуйте, vsb, Вы писали:

МГ>>при ограничении по памяти — внешняя сортировка
vsb>Ты точно понимаешь, что такое mmap? Ты можешь сделать mmap на файл любого размера (на 64-битной ОС) имея память любого размера. И ОС будет загружать/выгружать всё сама. От тебя требуется только обеспечить правильный паттерн доступа (например сортировка пузырьком это плохой вариант).

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

Здравствуйте, CreatorCray, Вы писали:

S>>То, что влезло в RAM, как-то странно называть большим объёмом данных, даже если у кого-то очень много RAM.
CC>Терабайт это много или мало? Нынче у машин и по терабайту рамы бывает.

Всё относительно, но вообще терабайт, конечно, мелочь.

Здравствуйте, Codealot, Вы писали:

C>А что с ним не так? Если нужно сортировать большие объемы данных, то радикс и его варианты — единственный адекватный алгоритм.

3 слова: внешняя сортировка слиянием. Куски до слияния можно хоть поразрядной сортировкой сортировать, хоть на несколько ядер параллелить (если RAM позволяет), хоть что делать, пока не упёрлись в I/O.

Или применить обратный подход: зная распределение данных по разрядам (нас интересует, с какого символа данные реально отличаются), распиливаем входные данные на файлы по нескольким первым разрядам, каждый файл сортируем в памяти, после этого склеиаем отсортированные файлы.

Пока все данные помещаются в оперативную память, это не большие объёмы, это баловство. Я распиливанием и слиянием 300 Гб сортировал на машине с 8 Гб.

Здравствуйте, Мирный герцог, Вы писали:

МГ>как бы ты например отсортировал 2^32 32-битных целых?

Сортировка подсчётом. Надо всего-то 16 Гб памяти

Здравствуйте, karbofos42, Вы писали:

vsb>>А как надо? По-моему очень изящное решение. Мне нравится такой подход.

K>Зачем ему MMF, если он весь файл в память читает?

Во-первых это просто очень удобно, гораздо удобней, чем руками читать. Во-вторых MMF позволяет делать swap в исходный файл.

Здравствуйте, Мирный герцог, Вы писали:

vsb>>А как надо? По-моему очень изящное решение. Мне нравится такой подход.

МГ>при ограничении по памяти — внешняя сортировка

Ты точно понимаешь, что такое mmap? Ты можешь сделать mmap на файл любого размера (на 64-битной ОС) имея память любого размера. И ОС будет загружать/выгружать всё сама. От тебя требуется только обеспечить правильный паттерн доступа (например сортировка пузырьком это плохой вариант).

Здравствуйте, Codealot, Вы писали:

C>Кстати, можно ссылку?

https://news.ycombinator.com/item?id=23113656

Здравствуйте, Codealot, Вы писали:

МГ>>радикс-сорт (ну это воще круть, можно в яндекс устраиваться)

C>А что с ним не так? Если нужно сортировать большие объемы данных, то радикс и его варианты — единственный адекватный алгоритм.

То, что влезло в RAM, как-то странно называть большим объёмом данных, даже если у кого-то очень много RAM.

Здравствуйте, karbofos42, Вы писали:

K>С такими возможности по памяти я бы скорее всего считал строки в какое-нибудь бинарное дерево поиска и потом из дерева уже слил назад в файл в отсортированном виде.

Для дофига длинных строк я бы подумал про префиксное дерево

Здравствуйте, vsb, Вы писали:

vsb>Ты точно понимаешь, что такое mmap? Ты можешь сделать mmap на файл любого размера (на 64-битной ОС) имея память любого размера. И ОС будет загружать/выгружать всё сама. От тебя требуется только обеспечить правильный паттерн доступа (например сортировка пузырьком это плохой вариант).

вот как раз таки потому что я точно понимаю что такое mmap, я понимаю что сортировка файла, отмапленного в память это клиника. Подумай на досуге сколько io операций потребуется если ты отмаппил файл и отсортировал vs скопировал в память, отсортировал и записал обратно в файл.

Здравствуйте, Мирный герцог, Вы писали:

МГ>yandex finished?

А у тебя, похоже, вообще ничего не finished?

МГ>как бы ты например отсортировал 2^32 32-битных целых?

Поразрядно, вестимо. По 16 бит за проход, например.

Здравствуйте, Codealot, Вы писали:

C>Поразрядно, вестимо. По 16 бит за проход, например.
учитывая то, что это будет на порядок медленнее сортировки подсчётом, а также что ты плюсанул vsb с его mmap твой уровень точно яндекс, не больше)

Здравствуйте, Мирный герцог, Вы писали:

МГ>учитывая то, что это будет на порядок медленнее сортировки подсчётом

Которая работает только в том случае, если можно выделить достаточно оперативки на подсчет — о чем ты не уточнял. Радикс сорт универсален и его можно втиснуть в любые ограничения по памяти.

МГ>а также что ты плюсанул vsb с его mmap твой уровень точно яндекс, не больше)

Ты так и не рассказал, чем так ужасен mmap.

Здравствуйте, Codealot, Вы писали:

C>Которая работает только в том случае, если можно выделить достаточно оперативки на подсчет — о чем ты не уточнял. Радикс сорт универсален и его можно втиснуть в любые ограничения по памяти.

я не понимаю зачем ты пишешь эти слова, причины для использования radix sort всегда можно найти, иначе его никто не использовал бы на практике, но я тебя точно ничем не ограничивал задавая вопрос о сортировке, и уж точно твоё "радикс и его варианты — единственный адекватный алгоритм." многое о тебе говорит. Большие данные ты сортировал чуть чаще чем никогда.

C>Ты так и не рассказал, чем так ужасен mmap.
я выше написал уже vsb, тем что генерирует на порядок больше i/o операций.

Здравствуйте, Мирный герцог, Вы писали:

МГ>конкретно по моему вопросу quicksort универсальней radix sort

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

МГ>counting sort быстрей radix sort.

В тех крайне редких случаях, когда его можно применить. Точнее говоря — практически не существующих в реальности случаях.

МГ>как лихо у тебя "единственный адекватный" стал вдруг "для больших данных, в общем случае".

Это и значит адекватный.

МГ>попадёшь ко мне на собеседование, я обязательно задам тебе этот вопрос. Поэтому подготовься. В контексте этого топика при любых.

А зачем мне идти на собеседование в какую-то неизвестную шарашкину контору?

Здравствуйте, Codealot, Вы писали:

МГ>>конкретно по моему вопросу quicksort универсальней radix sort
C>В каком месте он универсальней?

C>Единственные его плюсы — проще в реализации и работает быстрее на маленьких объемах.


МГ>>counting sort быстрей radix sort.
C>В тех крайне редких случаях, когда его можно применить. Точнее говоря — практически не существующих в реальности случаях.


МГ>>как лихо у тебя "единственный адекватный" стал вдруг "для больших данных, в общем случае".
C>Это и значит адекватный.


МГ>>попадёшь ко мне на собеседование, я обязательно задам тебе этот вопрос. Поэтому подготовься. В контексте этого топика при любых.
C>А зачем мне идти на собеседование в какую-то неизвестную шарашкину контору?
твой уровень мне понятен, тебе — действительно незачем.

Здравствуйте, Философ, Вы писали:

Ф>Выбор mmf заставляет сильно сомневаться в его профессионализме: там у него последовательный доступ...

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

Увидел тут такое: https://github.com/afiodorov/radixmmap

дебилушка взял меморимеп (автор слышал что это круто, видимо) и радикс-сорт (ну это воще круть, можно в яндекс устраиваться) и сортирует 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 Гб ОЗУ.

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

Здравствуйте, Мирный герцог, Вы писали:

МГ>Хипстер был так горд результатом, что аж пошёл всем рассказывать как он крут на хакернюс.

Кстати, можно ссылку?

А как надо? По-моему очень изящное решение. Мне нравится такой подход.

Здравствуйте, Sharowarsheg, Вы писали:

S>То, что влезло в RAM, как-то странно называть большим объёмом данных, даже если у кого-то очень много RAM.
Терабайт это много или мало? Нынче у машин и по терабайту рамы бывает.

Здравствуйте, Sharowarsheg, Вы писали:

S>Всё относительно, но вообще терабайт, конечно, мелочь.

Для сортировки квиксортом это уже многовато. Если, конечно, там не 16 элементов по 64 гига каждый.

Здравствуйте, Мирный герцог, Вы писали:

МГ>Увидел тут такое: https://github.com/afiodorov/radixmmap

МГ>дебилушка взял меморимеп (автор слышал что это круто, видимо) и радикс-сорт (ну это воще круть, можно в яндекс устраиваться) и сортирует 44-гигабайтный файл за 20 минут на 16 ядрах. Потребляя при этом 64 Гб ОЗУ. Хипстер был так горд результатом, что аж пошёл всем рассказывать как он крут на хакернюс. Похоже мы окончательно перешли в эпоху, когда обезьяна видит-обезьяна делает, не понимая сути, и нормальные инженеры вымирают как класс. Дискасс.

Ну, не было бы у него 64 гигов оперативки, он бы может получше подумал, а так — может себе позволить. Инженеры там, где технические ограничения, а не свобода действий.
В чём он нашёл повод для гордости — не понятно конечно. MMF использовать просто для чтения файла в память — это мощно конечно.
С такими возможности по памяти я бы скорее всего считал строки в какое-нибудь бинарное дерево поиска и потом из дерева уже слил назад в файл в отсортированном виде.
Но скорее всего и этого бы не стал делать, а просто отсортировал чем-нибудь стандартным, т.к. видимо мне было бы плевать на память и продолжительность работы, а это какая-то разовая задача, чтобы через час был результат.

Здравствуйте, vsb, Вы писали:

vsb>А как надо? По-моему очень изящное решение. Мне нравится такой подход.

Зачем ему MMF, если он весь файл в память читает?

Здравствуйте, Codealot, Вы писали:

S>>Всё относительно, но вообще терабайт, конечно, мелочь.

C>Для сортировки квиксортом это уже многовато. Если, конечно, там не 16 элементов по 64 гига каждый.

Нет, я скорее думал про терабайт 16-байтных индексов, скажем, в массив объектов суммарным размером в петабайт. Вот это интересная штука, да.

Здравствуйте, vsb, Вы писали:

vsb>Здравствуйте, karbofos42, Вы писали:

vsb>>>А как надо? По-моему очень изящное решение. Мне нравится такой подход.

K>>Зачем ему MMF, если он весь файл в память читает?

vsb>Во-первых это просто очень удобно, гораздо удобней, чем руками читать. Во-вторых MMF позволяет делать swap в исходный файл.

Я код не смотрел, но по описанию он вроде весь файл в память загрузил, а для этого MMF никакого профита не даёт.
Собственно потребляемая память косвенно подтверждает это, а значит проще было просто прочитать всё в память и перезаписать файл отсортированным результатом без всяких телодвижений с MMF.
Там что-то про хранение начала и конца строки. Если он в файле вручную переставлял строки местами, то MMF в этом поможет, но это наркомания какая-то.
Если конечно у него 44 гига почти упорядоченных данных, в которых нужно поменять местами всего десяток строк одинаковой длины, то можно позагоняться.
В общем же случае проще и быстрее переписать весь файл, чем бегать в нему, переставляя нужные байты.

Здравствуйте, vsb, Вы писали:

vsb>А как надо? По-моему очень изящное решение. Мне нравится такой подход.

при ограничении по памяти — внешняя сортировка

при неограниченной памяти (как у автора) — прочитать файл в память, сгенерировать 1.2 млрд пар 32-битный таймстемп+указатель на начало строки, отсортировать пары хоть квиксортом по значению таймстемпов, обойти отсортированные пары по порядку и записать значения по указателю в файл (здесь уже можно использовать ммап). Итого скорость сортировки равна скорость чтения данных с диска + скорость чтения записи на диск + мизерное время сортировки (на современном железе 1.2 млрд пар отсортировалось бы за секунды).

Здравствуйте, Codealot, Вы писали:

C>А что с ним не так? Если нужно сортировать большие объемы данных, то радикс и его варианты — единственный адекватный алгоритм.

yandex finished?

как бы ты например отсортировал 2^32 32-битных целых?

Здравствуйте, karbofos42, Вы писали:

K>Я код не смотрел, но по описанию он вроде весь файл в память загрузил, а для этого MMF никакого профита не даёт.
Профит в том, что не надо заморачиваться с кодом для подгрузки и выгрузки — работает автоматически.

Здравствуйте, Hobbes, Вы писали:

H>3 слова: внешняя сортировка слиянием.

Эффективность у него так себе.

H>Или применить обратный подход: зная распределение данных по разрядам (нас интересует, с какого символа данные реально отличаются), распиливаем входные данные на файлы по нескольким первым разрядам, каждый файл сортируем в памяти, после этого склеиаем отсортированные файлы.

То есть, комбинация радикс сорта и любого другого алгоритма.

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, karbofos42, Вы писали:

K>>Я код не смотрел, но по описанию он вроде весь файл в память загрузил, а для этого MMF никакого профита не даёт.
CC>Профит в том, что не надо заморачиваться с кодом для подгрузки и выгрузки — работает автоматически.

Подозреваю, что в варианте, когда последовательно считывается весь файл, разницы не будет ни по удобству ни по производительности.
Что fread какой-нибудь вызывай, что через mmap читай. Плюс-минус одно и то же должно быть по идее.

Здравствуйте, Мирный герцог, Вы писали:

МГ>но я тебя точно ничем не ограничивал задавая вопрос о сортировке

Если не сказано явно, что на требования по ресурсам нам насрать — используем более универсальное решение, а не то, которое работает только в очень узких условиях.

МГ>и уж точно твоё "радикс и его варианты — единственный адекватный алгоритм."

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

МГ>я выше написал уже vsb, тем что генерирует на порядок больше i/o операций.

При каких условиях?

Здравствуйте, Codealot, Вы писали:

C>Если не сказано явно, что на требования по ресурсам нам насрать — используем более универсальное решение, а не то, которое работает только в очень узких условиях.
конкретно по моему вопросу quicksort универсальней radix sort, counting sort быстрей radix sort.

МГ>>и уж точно твоё "радикс и его варианты — единственный адекватный алгоритм."
C>Для больших данных, в общем случае — да. Сортировку слиянием тоже можно, но это уже помедленнее.
как лихо у тебя "единственный адекватный" стал вдруг "для больших данных, в общем случае". Но проблески обучаемости налицо.

C>При каких условиях?
попадёшь ко мне на собеседование, я обязательно задам тебе этот вопрос. Поэтому подготовься. В контексте этого топика при любых.

Здравствуйте, Hobbes, Вы писали:

H>Здравствуйте, Мирный герцог, Вы писали:

МГ>>как бы ты например отсортировал 2^32 32-битных целых?

H>Сортировка подсчётом. Надо всего-то 16 Гб памяти

Если числа попарно-различные (или требуется это проверить) то хватит 128 мб.

Здравствуйте, Мирный герцог, Вы писали:

C>>При каких условиях?
МГ>попадёшь ко мне на собеседование, я обязательно задам тебе этот вопрос. Поэтому подготовься. В контексте этого топика при любых.

Т.е. для ответа тебе сначала необходимо получить преимущество ?

А давай-ка наоборот!
На собеседовании сейчас ТЫ. Отвечай.

Здравствуйте, andrey.desman, Вы писали:

AD>Толку ноль от него, но и вреда столько же.

Толк очень простой — упрощение кода.