Сортировка текстового файла с более чем 100 000 000 записей

Question

У меня есть текстовый файл 5 ГБ, который должен быть отсортирован в алфавитном порядке Какой алгоритм лучше всего использовать?

Ограничения:

Скорость - как можно быстрее

Память - ПК с 1 Гб оперативной памяти под управлением Windows XP

Answer 1

Я обычно сортирую текстовые файлы> 2 ГБ с помощью команды sort linux. Обычно это занимает 15-30 секунд, в зависимости от нагрузки на сервер.

Просто сделай это, это не займет столько времени, сколько ты думаешь.

Обновление Поскольку вы используете Windows XP, вы можете получить команду сортировки в UnxUtils . Я использую его, вероятно, больше, чем версия для Linux, и он одинаково быстр.

Узкое место для огромных файлов на самом деле скорость диска .. мой сервер выше имеет быстрый набег sata. Если ваша машина - настольный компьютер (или ноутбук), то ваши IDE-диски со скоростью вращения 7200 об / мин (или 5400 об / мин) добавят к работе несколько минут.

Answer 2

Для текстовых файлов sort, по крайней мере, версия GNU Coreutils в Linux и других, работает на удивление быстро.

Посмотрите на --buffer-size и связанные с ним опции и установите --temporary-directory, если каталог /tmp слишком мал.

В качестве альтернативы, если вы действительно беспокоитесь о том, сколько времени это займет, вы можете разбить файл на более мелкие куски, отсортировать их по отдельности, а затем объединить их вместе (sort --merge). Сортировка каждого чанка может выполняться параллельно в разных системах.

Answer 3

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

Answer 4

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

Answer 5

Как насчет импорта данных в SQL Server с помощью команды «Массовая вставка»?

текст ссылки

Это позволяет довольно быстро получить данные в SQL Server и затем выполнить всевозможную эффективную сортировку SQL на основе импортированных данных.

Вы также можете настроить это как автоматизированную задачу, используя SQL Server SSIS.

Answer 6

Сортировка слиянием - ваша лучшая ставка.