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

Question

Команда UNIX sort может сортировать очень большой файл, как это:

sort large_file 

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

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

Answer 1

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

Answer 2

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

Answer 3

Я не знаком с программой, но, я думаю, это делается с помощью внешней сортировки (большая часть проблемы хранится во временных файлах, а относительно небольшая часть проблемы хранится в памяти за раз). См. The Art of Computer Programming, Vol. 3 Sorting and Searching, Section 5.4 Дональда Кнута для очень подробного обсуждения темы.

Answer 4

ВНИМАНИЕ: Этот скрипт запускает одну оболочку за кусок, для действительно больших файлов это могут быть сотни.

---

Вот сценарий, который я написал для этой цели. На 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 

Смотрите также: "Sorting large files faster with a shell script"

Answer 5

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

#!/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* 

Answer 6

#!/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 

Answer 7

Посмотрите внимательно на опциях вида, чтобы ускорить работу и понять, что это влияние на вашу машину и проблемы. Основные параметры на Ubuntu являются

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

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