Алгоритмы сортировки, которые работают с большим объемом данных

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

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

Я думаю, что это хорошее решение (со сложностью O (nx log (n)), но мне любопытно узнать, есть ли другие (возможно, более быстрые) алгоритмы сортировки, которые могут работать с большими наборами данных, которые не помещаются в основную память.

РЕДАКТИРОВАТЬ

Вот некоторые подробности, как того требуют ответы:

• Данные необходимо сортировать периодически, например, раз в месяц. Мне не нужно вставлять несколько записей и сортировать данные постепенно.
• Мой пример текстового файла составляет около 1 ГБ текста UTF-8, но я хотел решить проблему в целом, даже если файл был, скажем, 20 ГБ.
• Его нет в базе данных, и из-за других ограничений этого не может быть.
• Данные сбрасываются другими в виде текстового файла, у меня есть свой код для чтения этого текстового файла.
• Формат данных - текстовый файл: символы новой строки являются разделителями записей.

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

Каноническая ссылка на сортировку и поиск - Knuth, Vol. 3 . Начни там.

Первоначально книга была написана в то время, когда компьютеры были намного меньше и медленнее, чем сейчас, что делало методы сортировки из памяти более важными, чем сегодня.

Внешнее слияние R-Way, как в команде UNIX, sortявляется хорошей альтернативой. Исходя из вашей формулировки, я не уверен, что это тот алгоритм, который вы имели в виду с помощью сортировки слиянием, и если вы не знаете его, посмотрите.

Без дополнительных подробностей «Merge Sort», вероятно, будет лучшим ответом, который вы получите, однако вы можете реализовать что-то более умное в зависимости от ваших требований.

Например, вы можете просто создать индекс файла в памяти, а затем скопировать все значения сразу, кэшируя расположение различных значений ключа? Умещается ли 1/2 в памяти сразу, или 1/1000000? Если это второй, то вы не сможете разместить индекс в памяти, если первый, то вы можете отсортировать обе половины более эффективно, а затем объединить их в один последний шаг.

Черт, так как вы не указали это, возможно, что все ваши данные находятся в базе данных, если это так, вы можете просто создать индексную таблицу и назвать ее хорошей (я предполагаю, что это не так, но просто указав, что Ваша ситуация имеет решающее значение для решения сложной проблемы, как это).

Если вы хотите сделать это только один раз и ищете очень быстрый взлом, похоже, что эта внешняя сортировка слиянием будет хорошим началом, если вы работаете с Unix (так как он, очевидно, встроен)

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

Можете ли вы контролировать код, который «читает» данные? Если это так, то многие формы индексации (а не сортировки путем перемещения данных на диске) помогут ОЧЕНЬ МНОГО (фактически будут абсолютным требованием).

Так:

• На месте или несколько файлов?
• Один раз в периодическом издании или держать его отсортированным на все времена?
• Насколько больше памяти (Сколько загружается памяти, чтобы пройти через весь набор данных)?
• Это в базе данных? Может ли это быть?
• Контролируете ли вы код, который читает данные, или другие будут напрямую выгружать файл?
• Формат файла? (Текст? Фиксированная запись?)
• Какие-то особые обстоятельства, о которых я не спрашивал?

Если вы действительно хотите масштабируемое решение, вам стоит взглянуть на TeraSort, стандартную реализацию сортировки с map-redund; более подробная информация о StackOverflow .

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

= O (n + d) n: количество элементов и d = длина наибольшего числа, если у вас есть интуиция о ваших данных, т.е. Если вы знаете, сколько цифр длиннее, это ваше наибольшее число. Так что, если у вас есть 2 миллиона 6-значных чисел => 0 (n), таким образом, линейный.

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

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

1. Каким-то образом закажите свою «базу данных»
2. Назначьте целое число для каждой записи (1, 2, 3, 4, ..., n) (лучше: используйте несколько разреженных индексов)
3. При добавлении приращения просто найдите пробел, в котором левое число меньше или равно, а правое число больше или равно (это не должно быть затруднительно при использовании некоторой модифицированной версии двоичного поиска)
4. Вставьте, пока пробелы достаточно велики, если нет: просто переиндексируйте (никогда не сортируйте снова) :-)

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

Я могу отсортировать данные 128 ГБ (каждый элемент по 100 байт) за 9 часов на одной машине, а затем выполнить двоичный поиск отсортированных данных практически без времени.

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