UNIX sort 명령은 어떻게 매우 큰 파일을 정렬 할 수 있습니까?

UNIX sort 명령은 어떻게 매우 큰 파일을 정렬 할 수 있습니까?

---

UNIX sort명령은 다음과 같이 매우 큰 파일을 정렬 할 수 있습니다.

sort large_file

정렬 알고리즘은 어떻게 구현됩니까?

과도한 메모리 소비를 일으키지 않는 이유는 무엇입니까?

---

UNIX Sort 명령 의 알고리즘 세부 정보에 따르면 Unix Sort는 외부 R-Way 병합 정렬 알고리즘을 사용합니다. 링크는 더 자세히 설명하지만 본질적으로 입력을 더 작은 부분 (메모리에 맞는)으로 나누고 마지막에 각 부분을 병합합니다.

---

이 sort명령은 작업 데이터를 임시 디스크 파일 (일반적으로 /tmp)에 저장합니다.

---

경고 : 이 스크립트는 청크 당 하나의 셸을 시작합니다. 정말 큰 파일의 경우 수백 개가 될 수 있습니다.

---

여기에 제가이 목적으로 작성한 스크립트가 있습니다. 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

참조 : " 쉘 스크립트를 사용하여 대용량 파일을 더 빠르게 정렬 "

---

나는 프로그램에 익숙하지 않지만 외부 정렬을 통해 수행되는 것 같습니다 (대부분의 문제는 임시 파일에 보관되고 문제의 비교적 작은 부분은 한 번에 메모리에 보관 됨). Donald Knuth의 The Art of Computer Programming, Vol. 3 분류 및 검색, 섹션 5.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

---

성능을 높이기 위해 정렬 옵션을주의 깊게 살펴보고 이것이 기계 및 문제에 미치는 영향을 이해하십시오. Ubuntu의 주요 매개 변수는 다음과 같습니다.

• 임시 파일의 위치 -T directory_name
• Amount of memory to use -S N% ( N% of all memory to use, the more the better but avoid over subscription that causes swapping to disk. You can use it like "-S 80%" to use 80% of available RAM, or "-S 2G" for 2 GB RAM.)

The questioner asks "Why no high memory usage?" The answer to that comes from history, older unix machines were small and the default memory size is set small. Adjust this as big as possible for your workload to vastly improve sort performance. Set the working directory to a place on your fastest device that has enough space to hold at least 1.25 * the size of the file being sorted.

---

Memory should not be a problem - sort already takes care of that. If you want make optimal usage of your multi-core CPU I have implementend this in a small script (similar to some you might find on the net, but simpler/cleaner than most of those ;)).

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

참고URL : https://stackoverflow.com/questions/930044/how-could-the-unix-sort-command-sort-a-very-large-file