Самый быстрый способ перетасовать строки в файле в Linux

Ответ 1

Используйте shuf вместо sort -R (справочная страница).

Медленность sort -R возможно из-за хэширования каждой строки. shuf просто выполняет произвольную перестановку, поэтому у нее нет этой проблемы.

(Это было предложено в комментарии, но почему-то не написано ничем как ответ)

Ответ 2

50 минут не вызваны фактической механикой сортировки, основанной на вашем описании. Время, скорее всего, потрачено на ожидание /dev/random, чтобы генерировать достаточную энтропию.

Один из подходов заключается в использовании внешнего источника случайных данных (http://random.org, например), а также вариации на Шварццианское преобразование. Шварцское преобразование превращает данные, которые будут отсортированы в "обогащенные" данные с встроенным ключом сортировки. Данные сортируются с использованием ключа, а затем ключ отбрасывается.

Чтобы применить это к вашей проблеме:

• сгенерируйте текстовый файл со случайными числами, по 1 на строку, с тем же количеством строк, что и файл для сортировки. Это можно сделать в любое время, запустить в фоновом режиме, запустить на другом сервере, загрузить с random.org и т.д. Дело в том, что эта случайность не создается во время сортировки.

• создайте обогащенную версию файла с помощью paste:

  paste random_number_file.txt string_data.txt > tmp_string_data.txt

• сортировать этот файл:

  sort tmp_string_data.txt > sorted_tmp_string_data.txt

• удалить случайные данные:

  cut -f2- sorted_tmp_string_data.txt > random_string_data.txt

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

Ответ 3

Вы можете попробовать мой инструмент: HugeFileProcessor. Он способен перетасовывать файлы сотен ГБ в разумные сроки.

Ниже приведены сведения о реализации перетасовки. Для этого требуется указать batchSize - количество строк для хранения в ОЗУ при записи на вывод. Чем больше, тем лучше (если вы не из ОЗУ), потому что общее время перетасовки будет (количество строк в исходном файле)/batchSize * (время для полного чтения sourceFile). Обратите внимание, что программа перетасовывает весь файл, а не на основе пакета.

Алгоритм выглядит следующим образом.

• Подсчитайте строки в исходном файле. Это делается простым чтением всего файла по очереди. (См. Некоторые сравнения здесь.) Это также дает измерение того, сколько времени потребуется, чтобы прочитать весь файл один раз. Таким образом, мы могли бы оценить, сколько раз потребовалось бы сделать полную перетасовку, потому что для этого потребовалось бы полное чтение файлов Ceil (linesCount/batchSize).

• Теперь, когда мы знаем общий набор строк, мы можем создать индексный массив с размером строки и перетасовать его с помощью Fisher-Yates ( так называемый orderArray в коде). Это даст нам порядок, в котором мы хотим иметь строки в перетасованном файле. Обратите внимание, что это глобальный порядок по всему файлу, а не пакету или фрагменту или чем-то.

• Теперь реальный код. Нам нужно получить все строки from sourceFile в порядке, который мы только что вычислили, но мы не можем прочитать весь файл в памяти. Поэтому мы просто разделили задачу.

  • Мы переходим через sourceFile, читаем все строки и сохраняем в памяти только те строки, которые были бы в первом пакете-массиве orderArray. Когда мы получим все эти строки, мы можем записать их в outFile в требуемом порядке, и это будет выполняться с помощью batchSize/linesCount.
  • Затем мы повторяем весь процесс снова и снова, принимая следующие части orderArray и читаем sourceFile от начала до конца для каждой части. В конце концов весь orderArray обрабатывается, и мы закончили.

Почему это работает?

Потому что все, что мы делаем, это просто чтение исходного файла от начала до конца. Нет поиска вперед/назад, а также то, что на HDD. Файл считывается в кусках в соответствии с внутренними буферами HDD, блоками FS, CPU cahce и т.д., И все считывается последовательно.

Некоторые числа

На моей машине (Core i5, 16 ГБ оперативной памяти, Win8.1, HDD Toshiba DT01ACA200 2TB, NTFS) Я смог перетасовать файл размером 132 ГБ (84 000 000 строк) примерно за 5 часов, используя пакетный размер 3 500 000 При пакетной загрузке 2 000 000 это заняло около 8 часов. Скорость чтения составляла около 118000 строк в секунду.