Сортировка содержимого очень большого (800 ГБ) текстового файла в Windows

25

У меня есть текстовый файл со словом в каждой строке, размер файла 800 ГБ. Мне нужно отсортировать слова в алфавитном порядке.

Я попытался с помощью программы сортировки Windows, используя:

sort.exe input.txt /o output.txt

что выдает ошибку: Недостаточно основной памяти для завершения сортировки.

У меня 32 ГБ оперативной памяти, поэтому, когда я пытаюсь указать 10 ГБ памяти для сортировки, используя:

sort.exe input.txt /o output.txt /M 10000000

Я получил:

Предупреждение: указанный объем памяти уменьшается до доступной памяти подкачки.

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

Какие у меня варианты?

windows sorting Майя
источник
2
Пожалуйста, не кросспост См. Допускается ли перекрестная публикация вопроса на нескольких сайтах Stack Exchange, если вопрос по теме для каждого сайта?
ДэвидПостилл
10
Это не кросс-пост, я не машина, поэтому публикация и удаление другого занимает несколько минут!
MaYaN
3
В будущем разрешите сообществу перенести ваш вопрос
Ramhound
4
В Linux вы можете применить этот метод . С файлами размером 100 Мб это не должно быть большой проблемой.
Эрик Думинил
3
Какую версию Windows вы используете? Файл sort.exe с довольно старой версией Windows Server 2012 R2 утверждает, что он может выполнять внешнюю сортировку слиянием с использованием временного файла на диске (без документирования ограничения размера). Попробуйте использовать / T, чтобы указать диск с 800 Гб свободного места для временного файла. А сообщение о том, что «входная запись превышает максимальную длину», похоже, не имеет отношения к пробелу - посмотрите на параметр / REC и подумайте, какой у вас терминатор строки.
Давидбак

Ответы:

16

Какие у меня варианты?

Попробуйте бесплатную утилиту сортировки командной строки CMSort .

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

CMsort читает записи входного файла, пока не будет достигнута установленная память. Затем записи сортируются и записываются во временный файл. Это будет повторяться до тех пор, пока все записи не будут обработаны. Наконец, все временные файлы объединяются в выходной файл. Если доступной памяти достаточно, временные файлы не записываются и объединение не требуется.

Один пользователь сообщает, что отсортировал файл размером 130 000 000 байт.

Если вы хотите настроить некоторый код самостоятельно, есть также Сортировка огромных текстовых файлов - CodeProject - «Алгоритм сортировки строк в текстовых файлах, размер которых превышает доступную память»

ДэвидПостилл
источник
26
Ух, 130 мегабайт !!! +1
Дэвид Фёрстер
3
@DavidPostill Вы уверены, что сортировка по coreutils для Windows не более эффективна ( --parallelвариант, если у вас более одного ядра ...)?
Хастур
23

Еще один вариант - загрузить файл в базу данных. Например, MySQL и MySQL Workbench.
Базы данных являются идеальными кандидатами для работы с большими файлами

Если ваш входной файл содержит только слова, разделенные новой строкой, это не должно быть сложно.

После того, как вы установили базу данных и MySQL Workbench, это то, что вам нужно сделать.
Сначала создайте схему (предполагается, что слова не будут длиннее 255 символов, хотя вы можете изменить это, увеличив значение аргумента). Первый столбец «idwords» является первичным ключом.

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

Во-вторых, импортируйте данные: EG Это импортирует все слова в таблицу (этот шаг может занять некоторое время. Мой совет - сначала запустить тест с небольшим файлом слов, и как только вы убедитесь, что формат такой же, как больший (обрежьте таблицу. IE очистите ее и загрузите полный набор данных).

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);


Эта ссылка может помочь получить правильный формат для загрузки. https://dev.mysql.com/doc/refman/5.7/en/load-data.html
EG. Если вам нужно пропустить первую строку, вы должны сделать следующее.

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

Наконец сохраните отсортированный файл. Это может занять некоторое время, в зависимости от вашего компьютера.

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

Вы также можете искать данные по своему усмотрению. EG Это даст вам первые 50 слов в порядке возрастания (начиная с 0-го или первого слова).

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;

Удачи
Пит

Питер Х
источник
2
Это IS правильный ответ со значительным отрывом.
MonkeyZeus
1
Этот подход, безусловно, будет более гибким, особенно если вы обнаружите, что вам нужно, например, перезапустить сортировку с другим порядком.
барбекю
Мне все равно, насколько быстро работает ваш экземпляр MySQL , MariaDB или любой другой СУБД , он не приблизится к производительности вставки SQLite на той же машине. Даже с таким быстрым, как SQLite, этот объем данных слишком (и медленный) обрабатывать (поверьте мне, я сначала попробовал!), Поэтому лучшее решение - сначала отсортировать и удалить дубликаты, а затем вставить их в БД, такую ​​как SQLite . Так что, хотя это решение может быть действительно для некоторых случаев, оно определенно не для того, что я пытаюсь сделать. Спасибо, что нашли время, чтобы опубликовать это в любом случае.
MaYaN
Заказ mywordsбудет длиться вечно. Даже с этим LIMIT, это займет столько же времени, сколько и все, потому что MySQL должен будет пройти через все значения mywordsи упорядочить их. Чтобы это исправить, вы должны сделать следующее после того, как вы это сделали LOAD DATA. Добавить индекс в mywords. Теперь вы можете заказать по этой колонке, а не сделать это через тысячелетия. И это лучше , чтобы добавить индекс после загрузки данных , а не в то время , вы создали таблицу (намного быстрее загрузки данных).
Buttle Butkus
7

sort

Существует много алгоритмов, используемых для сортировки упорядоченных и не упорядоченных файлов [ 1 ] .
Поскольку все эти алгоритмы уже реализованы, выберите программу, уже протестированную.

В coreutils (из Linux, но доступно и для Windows [ 2 ] ) существует sortкоманда, способная работать параллельно под многоядерными процессорами: обычно этого достаточно.

Если ваш файл настолько велик, вы можете помочь в обработке splitting ( split -l), файла в некоторых чанках, возможно, с помощью опции Parallel ( --parallel) и сортировке полученных упорядоченных чанков с помощью -mопции ( сортировка слиянием ).
Один из многих способов сделать это объясняются здесь (разделение файлов, одиночные чушки порядка, слияние упорядоченных ломтей, удалять временные файлы).

Заметки:

  • В Windows 10 существует так называемая подсистема Windows для Linux, в которой все примеры Linux будут казаться более естественными.
  • Сортировка с использованием разных алгоритмов имеет разное время выполнения, которое масштабируется в зависимости от количества сортируемых записей данных (O (n m ), O (nlogn) ...).
  • Эффективность алгоритма зависит от порядка, который уже присутствует в исходном файле.
    (Например, пузырьковая сортировка - это самый быстрый алгоритм для уже упорядоченного файла - ровно N, но в других случаях он неэффективен).
Hastur
источник
2

Чтобы предложить альтернативное решение для Peter H, существует программа q, которая позволяет использовать команды в стиле SQL для текстовых файлов. Команда ниже будет делать то же самое (запускаться из командной строки в том же каталоге, что и файл), без необходимости устанавливать SQL Workbench или создавать таблицы.

q "select * from words.txt order by c1"

c1 является сокращением для столбца 1.

Вы можете исключить повторяющиеся слова с

q "select distinct c1 from words.txt order by c1"

и отправить вывод в другой файл

q "select distinct c1 from words.txt order by c1" > sorted.txt
Брайан
источник
Есть идеи, справится ли это с файлом на 800 гигов?
Роулинг
1
Я не уверен на 100% - я проверял вышеупомянутое с файлом 1200 строк (9 КБ). На странице разработчиков есть страница с ограничениями, в которой ничего не говорится о максимальном размере файла. Большой файл все еще может столкнуться с проблемой памяти.
Брайан
3
q не может обработать этот объем данных, помните, что q использует SQLite за кулисами, если я не могу загрузить данные напрямую в SQLite, что заставляет вас думать, что q может?
MaYaN
2

Если слова в каждой строке взяты из ограниченного словаря (например, английского), вы можете отсортировать список за O (n + m log m), используя TreeMap и количество записей (где m - количество уникальных значений).

В противном случае вы можете использовать java-библиотеку big-sorter . Он разбивает входные данные на отсортированные промежуточные файлы и эффективно объединяет их (в целом O (nlogn)). Сортировка вашего файла выглядит следующим образом:

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

Я создал файл объемом 1,7 ГБ (100 м строк) со случайно сгенерированными 16-символьными словами и отсортировал его, как указано выше, в 142-х годах и основываясь на вычислительной сложности O (n log n) метода, который я использую, я оцениваю, что 800 ГБ из 16-ти символов символов займет около 24 часов, чтобы отсортировать однопоточные на моем ноутбуке i5 2.3 ГГц с SSD.

Дейв Мотен
источник