W jaki sposób polecenie sortowania systemu UNIX może posortować bardzo duży plik?

Polecenie UNIX sortmoże sortować bardzo duży plik w następujący sposób:

sort large_file

Jak jest zaimplementowany algorytm sortowania?

Dlaczego nie powoduje nadmiernego zużycia pamięci?

Te dane algorytmiczne sort polecenia UNIX mówi Unix Sortuj wykorzystuje algorytm scalania sortowania zewnętrzny R-Way. Łącze zawiera więcej szczegółów, ale zasadniczo dzieli dane wejściowe na mniejsze części (które mieszczą się w pamięci), a następnie łączy każdą część razem na końcu.

W sortsklepach polecenie dane tymczasowe pliki dysków roboczych (zazwyczaj /tmp).

OSTRZEŻENIE: Ten skrypt uruchamia jedną powłokę na porcję, w przypadku naprawdę dużych plików może to być setki.

Oto skrypt, który napisałem w tym celu. Na komputerze z 4 procesorami poprawiło to wydajność sortowania o 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

Zobacz też: „ Szybsze sortowanie dużych plików za pomocą skryptu powłoki ”

Nie znam tego programu, ale wydaje mi się, że odbywa się to za pomocą sortowania zewnętrznego (większość problemu jest przechowywana w plikach tymczasowych, podczas gdy stosunkowo niewielka część problemu jest przechowywana w pamięci). Zobacz Donald Knuth's The Art of Computer Programming, tom. 3 Sortowanie i wyszukiwanie, sekcja 5.4 dla bardzo dogłębnej dyskusji na ten temat.

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

Przyjrzyj się uważnie opcjom sortowania, aby przyspieszyć działanie i zrozum, jak wpływa to na Twój komputer i problem. Kluczowe parametry w systemie Ubuntu to

• Lokalizacja plików tymczasowych -T nazwa_katalogu
• Ilość pamięci do wykorzystania -SN% (N% całej pamięci do wykorzystania, im więcej, tym lepiej, ale unikaj subskrypcji powodującej zamianę na dysk. Możesz użyć tego jak „-S 80%”, aby użyć 80% dostępnej pamięci RAM, lub „-S 2G” dla 2 GB pamięci RAM).

Pytający pyta „Dlaczego nie ma dużego użycia pamięci?” Odpowiedź na to pochodzi z historii, starsze komputery z systemem UNIX były małe, a domyślny rozmiar pamięci jest ustawiony na mały. Dostosuj to tak duże, jak to możliwe, aby znacznie poprawić wydajność sortowania. Ustaw katalog roboczy na miejsce na najszybszym urządzeniu, w którym jest wystarczająco dużo miejsca, aby pomieścić co najmniej 1,25 * rozmiaru sortowanego pliku.

Pamięć nie powinna być problemem - sort już się tym zajmuje. Jeśli chcesz optymalnie wykorzystać swój wielordzeniowy procesor, zaimplementowałem to w małym skrypcie (podobnym do niektórych, które możesz znaleźć w sieci, ale prostszym / czystszym niż większość z nich;)).

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