यूनिक्स सॉर्ट कमांड कैसे एक बहुत बड़ी फाइल को सॉर्ट कर सकता है?

Question

यूनिक्स sort कमांड इस तरह की एक बहुत बड़ी फ़ाइल को सॉर्ट कर सकता है:

sort large_file 

सॉर्ट एल्गोरिदम कैसे कार्यान्वित किया जाता है?

यह कैसे स्मृति की अत्यधिक खपत का कारण नहीं बनता है?

Answer 1

Algorithmic details of UNIX Sort command का कहना है कि यूनिक्स सॉर्ट एक बाहरी आर-वे विलय सॉर्टिंग एल्गोरिदम का उपयोग करता है। लिंक अधिक जानकारी में जाता है, लेकिन संक्षेप में यह इनपुट को छोटे हिस्सों में विभाजित करता है (जो स्मृति में फिट होता है) और फिर अंत में प्रत्येक भाग को विलय करता है।

Answer 2

sort कमांड अस्थायी डिस्क फ़ाइलों में काम करने वाले डेटा स्टोर करता है (आमतौर पर /tmp में)।

Answer 3

मैं प्रोग्राम से परिचित नहीं हूं लेकिन मुझे लगता है कि यह बाहरी सॉर्टिंग के माध्यम से किया जाता है (अधिकांश समस्या अस्थायी फ़ाइलों में होती है जबकि समस्या का अपेक्षाकृत छोटा हिस्सा एक समय में स्मृति में आयोजित होता है)। विषय की बहुत गहन चर्चा के लिए डोनाल्ड 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

मेमोरी एक समस्या नहीं होना चाहिए - तरह पहले से ही इस बात का ख्याल रखता है। यदि आप अपने बहु-कोर सीपीयू का इष्टतम उपयोग करना चाहते हैं तो मैंने इसे एक छोटी सी स्क्रिप्ट में कार्यान्वित किया है (कुछ लोगों के जैसा आप नेट पर पा सकते हैं, लेकिन उनमें से अधिकतर से सरल/क्लीनर;))। ध्यान से एक तरह से विकल्पों पर

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

देखो प्रदर्शन में तेजी लाने और इसे अपने मशीन और समस्या पर प्रभाव है समझने के लिए। Ubuntu पर कुंजी पैरामीटर

• अस्थायी फ़ाइलों का स्थान स्मृति के DIRECTORY_NAME
• राशि आयकर उपयोग करने के लिए सभी स्मृति की -SN% (एन% का उपयोग करने के, और अधिक बेहतर लेकिन सदस्यता का कारण बनता है के ऊपर से बचने कर रहे हैं डिस्क पर गमागमन। आप इसे 'एस 80% "की तरह उपयोग कर सकते हैं के लिए 2 जीबी रैम उपलब्ध रैम का 80%, या" एस 2 जी "का उपयोग करें।)

प्रश्नकर्ता पूछते हैं," क्यों कोई उच्च स्मृति उपयोग ? " इसका उत्तर इतिहास से आता है, पुरानी यूनिक्स मशीनें छोटी थीं और डिफ़ॉल्ट मेमोरी आकार छोटा सेट होता है। सॉर्ट प्रदर्शन में काफी सुधार करने के लिए अपने वर्कलोड के लिए जितना संभव हो उतना बड़ा समायोजित करें। कार्यस्थल निर्देशिका को अपने सबसे तेज़ डिवाइस पर किसी स्थान पर सेट करें जिसमें कम से कम 1.25 * सॉर्ट किए जाने वाले फ़ाइल का आकार रखने के लिए पर्याप्त स्थान हो।