☰

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

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

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

Я пробовал использоватьОкна Сортироватьпрограмма с использованием:

sort.exe input.txt /o output.txt

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

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

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

Я получил:

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

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

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

решение1

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

ПытатьсяБесплатная утилита командной строки для сортировки CMSort.

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

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

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

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

решение2

Другой вариант — загрузить файл в базу данных. Например, 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`));

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

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

Например, если вам нужно пропустить первую строку, вы можете сделать следующее.

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';

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

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

решение3

sort

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

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

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

Примечания:

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

решение4

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

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

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

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

Связанный контент