Как команда UNIX sort могла отсортировать очень большой файл?

Команда UNIX sortможет отсортировать очень большой файл следующим образом:

sort large_file

Как реализован алгоритм сортировки?

Почему это не вызывает чрезмерного потребления памяти?

В алгоритмические детали команды UNIX Сортировка говорит Unix Сортировка использует алгоритм в слияние внешнего R-Way сортировки. Ссылка дает более подробную информацию, но по сути она делит ввод на более мелкие части (которые помещаются в память), а затем объединяет каждую часть вместе в конце.

Команда sortсохраняет рабочие данные во временных файлах на диске (обычно в формате /tmp).

ПРЕДУПРЕЖДЕНИЕ. Этот сценарий запускает одну оболочку для каждого фрагмента, для действительно больших файлов их может быть сотни.

Вот сценарий, который я написал для этой цели. На машине с 4 процессорами производительность сортировки улучшилась на 100%!

#! /bin/ksh

MAX_LINES_PER_CHUNK=1000000
ORIGINAL_FILE=$1
SORTED_FILE=$2
CHUNK_FILE_PREFIX=$ORIGINAL_FILE.split.
SORTED_CHUNK_FILES=$CHUNK_FILE_PREFIX*.sorted

usage ()
{
     echo Parallel sort
     echo usage: psort file1 file2
     echo Sorts text file file1 and stores the output in file2
     echo Note: file1 will be split in chunks up to $MAX_LINES_PER_CHUNK lines
     echo  and each chunk will be sorted in parallel
}

# test if we have two arguments on the command line
if [ $# != 2 ]
then
    usage
    exit
fi

#Cleanup any lefover files
rm -f $SORTED_CHUNK_FILES > /dev/null
rm -f $CHUNK_FILE_PREFIX* > /dev/null
rm -f $SORTED_FILE

#Splitting $ORIGINAL_FILE into chunks ...
split -l $MAX_LINES_PER_CHUNK $ORIGINAL_FILE $CHUNK_FILE_PREFIX

for file in $CHUNK_FILE_PREFIX*
do
    sort $file > $file.sorted &
done
wait

#Merging chunks to $SORTED_FILE ...
sort -m $SORTED_CHUNK_FILES > $SORTED_FILE

#Cleanup any lefover files
rm -f $SORTED_CHUNK_FILES > /dev/null
rm -f $CHUNK_FILE_PREFIX* > /dev/null

См. Также: « Ускорение сортировки больших файлов с помощью сценария оболочки »

Я не знаком с программой, но полагаю, что это делается с помощью внешней сортировки (большая часть проблемы хранится во временных файлах, в то время как относительно небольшая часть проблемы сохраняется в памяти одновременно). См. Книгу Дональда Кнута « Искусство программирования», том. 3 Сортировка и поиск, раздел 5.4 для очень глубокого обсуждения предмета.

#!/bin/bash

usage ()
{
    echo Parallel sort
    echo usage: psort file1 file2
    echo Sorts text file file1 and stores the output in file2
}

# test if we have two arguments on the command line
if [ $# != 2 ]
then
    usage
    exit
fi

pv $1 | parallel --pipe --files sort -S512M | parallel -Xj1 sort -S1024M -m {} ';' rm {} > $2

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

• Расположение временных файлов -T имя_каталога
• Объем используемой памяти -SN% (N% всей используемой памяти, чем больше, тем лучше, но избегайте излишней подписки, которая вызывает подкачку на диск. Вы можете использовать это как «-S 80%», чтобы использовать 80% доступной оперативной памяти, или «-S 2G» для 2 ГБ ОЗУ.)

Спрашивающий спрашивает: "Почему не используется много памяти?" Ответ на этот вопрос исходит из истории: старые unix-машины были небольшими, а размер памяти по умолчанию установлен маленьким. Настройте его как можно больше для вашей рабочей нагрузки, чтобы значительно улучшить производительность сортировки. Установите рабочий каталог в такое место на самом быстром устройстве, на котором достаточно места для хранения не менее 1,25 * размера сортируемого файла.

Память не должна быть проблемой - sort уже позаботится об этом. Если вы хотите оптимально использовать свой многоядерный процессор, я реализовал это в небольшом скрипте (похожем на те, которые вы можете найти в сети, но проще / чище, чем большинство из них;)).

#!/bin/bash
# Usage: psort filename <chunksize> <threads>
# In this example a the file largefile is split into chunks of 20 MB.
# The part are sorted in 4 simultaneous threads before getting merged.
# 
# psort largefile.txt 20m 4    
#
# by h.p.
split -b $2 $1 $1.part
suffix=sorttemp.`date +%s`
nthreads=$3
i=0
for fname in `ls *$1.part*`
do
    let i++
    sort $fname > $fname.$suffix &
    mres=$(($i % $nthreads))
    test "$mres" -eq 0 && wait
done
wait
sort -m *.$suffix 
rm $1.part*