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

Question

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

sort large_file 

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

메모리를 과도하게 소비하지 않는 이유는 무엇입니까?

Answer 1

Algorithmic details of UNIX Sort command은 Unix Sort가 외부 R-Way 병합 정렬 알고리즘을 사용한다고 말합니다. 링크는 더 자세한 내용으로 들어가지만 본질적으로 입력을 더 작은 부분 (메모리에 맞춰 짐)으로 나누고 마지막 부분에서 각 부분을 병합합니다.

Answer 2

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

Answer 3

나는이 프로그램에 익숙하지 않지만 외부 정렬을 통해 이루어 졌다고 생각한다. (문제의 대부분은 임시 파일에 저장되는 반면, 문제의 비교적 작은 부분은 한 번에 메모리에 저장된다.) Donald Knuth의 The Art of Computer Programming, Vol. 3 Sorting and Searching, Section 5.4에서 주제에 대한 자세한 설명을 볼 수 있습니다.

Answer 4

경고 :이 스크립트는 청크 당 하나의 셸을 시작하며, 실제로는 대용량 파일의 경우 수백 개가 될 수 있습니다.

---

다음은이 목적으로 작성한 스크립트입니다. 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 

은 참조 : "Sorting large files faster with a shell script"

Answer 5

메모리는 문제가되지 않습니다 - 종류 이미 처리한다. 멀티 코어 CPU를 최적의 상태로 사용하고 싶다면 작은 스크립트 (넷에서 찾을 수있는 것과 비슷하지만 대부분의 경우보다 간단하고 깔끔한)와 같이 구현해야합니다. 조심스럽게 종류의 옵션에서

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

Answer 6

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

봐 성능을 가속화하고 컴퓨터와 문제에 미치는 영향의 이해합니다. 우분투에 주요 매개 변수는 임시 파일의

• 위치, 더 나은하지만 원인 가입을 통해 않도록 사용하는 모든 메모리의 -sn % (N의 %를 사용하는 메모리의 디렉토리 이름
• 금액 -t 있습니다 디스크로 교환. 당신은 "-S 80 %"처럼 사용할 수있는 결과 2 기가 바이트 RAM을 사용할 RAM의 80 %, 또는 "-S 세대"를 사용합니다.)
가

질문자가 "왜 메모리 사용을 요구하지 않습니다 ? " 그 대답은 역사에서 나왔고 오래된 Unix 시스템은 작았고 기본 메모리 크기는 작게 설정되었습니다. 워크로드가 가능한 한 크게 조정하여 정렬 성능을 크게 향상시킵니다. 작업 디렉토리를 정렬하는 파일의 크기를 최소한 1.25 * 보유 할 수있는 충분한 공간이있는 가장 빠른 장치의 위치로 설정하십시오.