Алгоритмы сортировки

[shipr]

Уважаемые руссо программисто.

В ходе обыденного былокодинга нарисовалась задачка.
Есть файл размером в +100500 мегабайт, файл состоит из строчек одинаковым размером по 100 байт/символов + символ переноса на новую строчку.
Надо отсортировать строчки в файле по первым 20 символам в возрастающей последовательности.
Файл заведомо большего размера, чем есть в компьютере памяти, т.е. загрузить весь файл в память нельзя.

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

PS про Hadoop и Terabyte in 62 Seconds в курсе.

[axotnik88]

http://habrahabr.ru/blogs/php/127569/

[Архон]

PS про Hadoop и Terabyte in 62 Seconds в курсе.

ух ты, а что это

Роберт Седжвик "Фундаментальные алгоритмы на С++" - где-то в районе 7, 8 главы по твоему случаю

а вообще я бы не парился:

1) конвертнул бы файл в какую нибудь DBF-ку, типа таблица с 1-м полем - длинная строка
2) закинул бы в какую-нибудь СУБД-шку (предпочитаю Oracle); или если без DBF-ки парсил бы файл и заливал построчно
3) на стороне БД отработал бы обычный ORDER BY и вылил обратно в файл; если мало оперативки, выгружал бы порциоанльно, скажем по 10 000 строк с сохранением

как-то так

[shipr]

Немного погуглив был найден следующий вариант сортировки:
1. Сначала читаем "большой" файл с данными построчно в память, насколько хватит памяти. Потом этот кусочек сортируется в памяти, потом отсортированную порцию данных сливаем в "маленький" файл. В результате у нас должно появиться много "маленьких" отсортированных кусочков "большого" файла.
2. Читаем по строчке из "маленьких" файлов и находим "минимальную" строчку и пишем её в результирующий файл, вместо "минимальной" строчки читаем следующую строчку из соотвественного файла.

По сути данный алгоритм - это классика гомнокодинга - сортировка делением наполовину.
В терминах map/reduce - первая часть алгоритма - это map, а вторая часть - это собственно reduce. Hadoop - это реализация map/reduce на линухе и жабе.

эх перевелись знатоки на форуме.

[Архон]

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

а то спасите, помогите, фе ...

[shurikwg]

А если так?

Читаем в память только первые N символов каждой строки и запоминаем с номером строки.
N зависит от объема доступной памяти и размера файла.
Сортируем.
Пишем результирующий файл читая из исходного номера строк в порядке сортировки.
Если имеем группу строк с одинаковым набором первых N символов то для этих строк вычитываем в память по 20 символов и делаем более детальную сортировку.

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

Или еще лучше вариант, вычитываем по одному символу, сортируем, добавляем к каждой строке в памяти еще по одному, сортируем по уже сформированным группам, и так дальше до 20, но читая только если в группе больше одной строки, если строка остается одна, например начинающаяся на ABCDEF, то дальше для нее уже ничего читать не надо.
А вот если уже и в таком варианте не хватит памяти на полную сортировку, то тогда промежуточные результаты нужно будет кешировать во временном файле.

В общем это так... полет мысли...

[Шериха]

Решал я похожие задачки, у меня было по 250M записей на ноду.

Варианты такие.
1. делаешь mmap на все файло. Даешь mmap_madvise на read ahead.
В чем плюс - скорость последовательного доступа мало отличается от скорости памяти.
В чем минус - qsort можешь забыть как класс.
В качестве файловой системы лучше XFS.
Причем место сразу создаешь через posix_fallocate - иначе добавление к файлу долгое.
Сортируешь через radix sort - это несколько проходов с составлением гистограмм, что очень долго, но - последовательным доступом, т.е. диск не дергается лишний раз.
И такой момент. Если распределение символов сильно неравномерное то про radix sort можешь забыть - будет медленнее чем quick sort.
Поэтому последние кусочки досортировываешь уже quick sort'ом. - они скорее всего в память и поместятся.
Мы еще свои кеши добавляли, но это уже под наши распределения, ad hoc.

2. Строишь вспомогательное файло, где записаны только первые 20 байт и номер записи в оригинальном файле.
Т.е. объем уменьшаешь в 5 раз.
Может в память и поместится.

3. Куришь доку по разнообразным методам сортировки (а там реально целый мир и курить будешь недели две минимум).
Выбираешь чтто-то типа BurstSort или аналог cache-friendly.
Или что-то типа hyperquicksort если можешь задействовать машины коллег

PS
Пишу с аккаунта жены, своего на форуме не имею.

[shipr]

Немного сырых фактов.
1. Последовательное чтение из файла на 1-2 порядка быстрее случайного чтения из файла.
2. Сортировка в памяти занимает несравнимо меньше времени чем чтение/запись с диска данных для сортировки.

Преимущества merge sort:
1. При вменяемой количестве памяти (2 Гб) можно сортировать файл в 2 прохода (по 2 операции чтения/записи) объёмом до 3 Тб.
2. Простота реализации.

Есть такая штука jim gray sort benchmark (гугл замечательно находит)

[Panzer]

Рассматривали вариант заменить сортировку индексацией?

[shipr]

Рассматривали вариант заменить сортировку индексацией?

нет, т.к.

1. Последовательное чтение из файла на 1-2 порядка быстрее случайного чтения из файла.

[Panzer]

Откуда берутся данные?
Для чего вам отсортированные данные?

[maxx™]

Если это надо сделать 1 раз, не имеет значения какой алгоритм использовать (в разумных пределах)
Если постоянно - вопрос откуда файл и что с ним надо делать? Может его проще импортировать в mysql например, опять же потом выборки будет проще делать.
Ну и если сильно надо сортировать самому и постоянно - сделать пару алгоритмов и сравнить их по быстродействию. Первое что приходит в голову - разделить файл на n частей (чтоб маленький кусок поместился в память), сделать n потоков. Основной поток читает файл, смотрит в какой диапазон попадает значение и отправляет его в соответствующий поток. Потом эти все файлы по очереди вычитываются, сортируются и складываются в результат. Если какой-то файл получился большим - значит не повезло и к нему применяем алгоритм с начала. Если повезет - файл просортируется за 2 чтения каждого байта.

[shipr]

Насяльника сказала надо - таджикистон сказала есть.

Данные берутся из какой-то самодельной тулзы сделаной китайскими студентами на коленке.
Для того, чтобы отсортировать файл юзать БД - это как гвозди микроскопом.
Разделить файл на n частей - так и делаем.
сделать n потоков - нельзя, т.к. памяти лимитированное количество.

[Шериха]

Если отключить своп, сделать XFS, работать через mmap и на машинке с большим количеством оперативки, то скорость последовательного чтения может быть и больше. У меня реально от скорости памяти не сильно и отличалась.
Своп вообще на HPC-инсталляциях рекомендую отключать сразу и навсегда.
Проверено.

RAID практически не помогает - скорость позиционирования головки все равно не меняется, сколько блинов не ставь.

Есть подозрение, что и GPU никак не поможет, но это имхо, не пробовал.

Базы данных вообще можно забыть как класс.
Большинство СУБД даже с отключенной транзакционностью тормозят со страшной силой - они не для этого придуманы и не так написаны, там реальная скорость ниже плинтуса.

Если у тебя мало оперативки - то это проблема, скорость будет медленная. Чем больше оперативы - тем лучше, у меня 64Г на ноде висело.

Вообще cache-friendly sort семейство достаточно интересное, но я его не писал, так что про грабли не скажу.
Интересно его замерить на таких задачах. Специфичная штука, которая может не только кеш диска учитывать, но и кеш процессора.
BurstSort - один из первых таких алгоритмов, но я думаю что уже что-то новое придумали, смотреть надо.

Ну а если задача однократная - то запускай quicksort на неделю и бери отпуск. Только аккумуляторы на ups не забудь поменять.

[maxx™]

сделать n потоков - нельзя, т.к. памяти лимитированное количество.

ПОчему вдруг нельзя? Чем больше потоков, тем меньше буфер у каждого потока, но сделать их можно столько сколько нужно.

[Hose]

т.к. памяти лимитированное количество.

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

[maxx™]

железо нынче самый дешевый ресурс.

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

[Hose]

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

Не спорю. Но ты сам сказал, что если задача разовая то без разницы как это сделать, а если такие большие файлы постоянно надо сортировать на слабом железе, то это уже, мне кажется, в консерватории править надо.
Обычно, если речь о мобильной платформе или встраиваемой системе, то и файлам 100500 мегабайт там делать нечего.
Если это логи или иной продукт жизнедеятельности ничто не помешает отсортировать на сервере.
Имхо.