Bagaimana perintah sortir UNIX dapat mengurutkan file yang sangat besar?

sortPerintah UNIX dapat mengurutkan file yang sangat besar seperti ini:

sort large_file

Bagaimana algoritma sortir diimplementasikan?

Kenapa tidak menyebabkan konsumsi memory yang berlebihan?

The rincian algorithmic dari UNIX perintah Sortir mengatakan Unix Urutkan menggunakan eksternal R-Way merge algoritma sorting. Tautan menjelaskan lebih detail, tetapi pada dasarnya itu membagi input menjadi bagian-bagian yang lebih kecil (yang sesuai dengan memori) dan kemudian menggabungkan setiap bagian bersama-sama di akhir.

The sorttoko perintah data dalam file disk sementara bekerja (biasanya dalam /tmp).

PERINGATAN: Skrip ini memulai satu shell per bagian, untuk file yang sangat besar, ini bisa ratusan.

Berikut ini skrip yang saya tulis untuk tujuan ini. Pada mesin 4 prosesor, ini meningkatkan kinerja pengurutan sebesar 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

Lihat juga: " Mengurutkan file besar lebih cepat dengan skrip shell "

Saya tidak terbiasa dengan program ini tetapi saya rasa ini dilakukan dengan cara penyortiran eksternal (sebagian besar masalah disimpan dalam file sementara sementara sebagian kecil masalah disimpan di memori pada satu waktu). Lihat The Art of Computer Programming karya Donald Knuth , Vol. 3 Penyortiran dan Pencarian, Bagian 5.4 untuk diskusi yang sangat mendalam tentang subjek tersebut.

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

Perhatikan baik-baik opsi semacam untuk mempercepat kinerja dan pahami pengaruhnya pada mesin dan masalah Anda. Parameter kunci di Ubuntu adalah

• Lokasi file sementara -T nama_direktori
• Jumlah memori yang akan digunakan -SN% (N% dari semua memori yang digunakan, lebih banyak lebih baik tetapi hindari berlangganan berlebihan yang menyebabkan pertukaran ke disk. Anda dapat menggunakannya seperti "-S 80%" untuk menggunakan 80% RAM yang tersedia, atau "-S 2G" untuk RAM 2 GB.)

Penanya bertanya "Mengapa tidak ada penggunaan memori yang tinggi?" Jawabannya berasal dari sejarah, mesin unix yang lebih lama berukuran kecil dan ukuran memori default disetel kecil. Sesuaikan ini sebesar mungkin untuk beban kerja Anda untuk sangat meningkatkan kinerja pengurutan. Setel direktori kerja ke tempat di perangkat tercepat Anda yang memiliki cukup ruang untuk menampung setidaknya 1,25 * ukuran file yang sedang diurutkan.

Memori seharusnya tidak menjadi masalah - semacam sudah mengurusnya. Jika Anda ingin memanfaatkan CPU multi-core secara optimal, saya telah mengimplementasikannya dalam skrip kecil (mirip dengan beberapa yang mungkin Anda temukan di internet, tetapi lebih sederhana / lebih bersih daripada kebanyakan;)).

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