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

Question

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

sort large_file

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

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

Answer 1

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

Answer 2

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

Answer 3

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

---

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

Смотрите также: " Сортировка больших файлов быстрее с помощью сценария оболочки "

Answer 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

Answer 5

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

Answer 6

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

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

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

Answer 7

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

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