Самый быстрый способ сортировки огромных (50-100 ГБ) файлов, когда у вас достаточно памяти

В Интернете много обсуждений по теме сортировки огромных файлов в Unix, когда данные не помещаются в память. Как правило, использование mergesort и вариантов.

Как бы там ни было, если бы было достаточно памяти, чтобы вместить в нее все данные, что может быть самым эффективным/самым быстрым способом сортировки? Файлы csv составляют ~ 50 ГБ ( > 1 миллиард строк), и для хранения всех данных достаточно памяти (5x размера данных).

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

Спасибо заранее.

Ответы

Ответ 2

Как насчет QuickSort? Ты пробовал? std:: sort обычно реализуется quicksort (точнее introsort, который переключается на heapsort, если производительность quicksort будет плоха), поэтому вы можете попробовать с ним. quicksort, как правило, самый быстрый вариант (хотя наихудшая сложность - O (n ^ 2), но в обычных случаях она превосходит все другие алгоритмы сортировки).

Сложность пространства quicksort не должна быть слишком плохой, для этого требуется пространство стека log2 (N), которое составляет около 30 кадров стека для 1 миллиарда элементов.

Однако это неустойчивый алгоритм сортировки (порядок "равных" элементов не сохраняется), поэтому это зависит, если вы в порядке с этим.

Btw. Тип Unix, похоже, реализуется с помощью сортировки слиянием, что обычно не является самым быстрым вариантом для сортировки в RAM.