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

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

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