रुबी में एक सेट में छोटे तार जोड़ना धीमा है

Question

मैं इस रूबी कोड का उपयोग कर अपने यूटीएफ -8 फ्रेंच शब्दकोश फ़ाइल के सभी अद्वितीय पात्रों को निकालने का प्रयास कर रहा हूं। शब्दकोश 3.7 एमबी है। कुछ कारणों से यह निष्पादित करने के लिए मेरे सभ्य कंप्यूटर को आधे घंटे लगते हैं। कोई विचार?

c = Set.new 
f = open "dict" 
s = f.read 
f.close 

for i in 0..s.length-1 
    c << s[i] 
end 

Answer 1

इस पर किसी भी गणना करने से पहले पूरी फ़ाइल में पढ़ना आईओ को गणना के साथ अंतःस्थापित होने से रोकता है। इसके अलावा, यह मेमोरी प्रेशर बढ़ाता है (संभावित रूप से महत्वपूर्ण यदि आप अपनी मेमोरी की सीमा के करीब चल रहे हैं) और cache coherency को काफी हद तक कम कर देता है।

मैं निम्नलिखित छोटे से स्क्रिप्ट जो मेरे /usr/share/dict/words फ़ाइल पर .3 सेकंड में कार्यान्वित लिखा था - एक मेगाबाइट से भी कम समय है, लेकिन अभी काफी बड़ी थोड़ा दिलचस्प हो रहे हैं:

$ cat /tmp/set.rb 
#!/usr/bin/ruby 

require 'set' 

c = Set.new 
f = open "/usr/share/dict/words" 

f.each_char do |char| 
    c << char 
end 

p c 
$ time /tmp/set.rb 
#<Set: {"A", "\n", "'", "s", "B", "M", "C", "T", "H", "I", "D", "S", "O", "L", "P", "W", "Z", "a", "c", "h", "e", "n", "l", "i", "y", "r", "o", "b", "d", "t", "u", "j", "g", "m", "p", "v", "x", "f", "k", "z", "w", "q", "ó", "ü", "á", "ö", "ñ", "E", "F", "R", "U", "N", "G", "K", "é", "ä", "Q", "è", "V", "J", "X", "ç", "ô", "í", "Y", "â", "û", "ê", "å", "Å"}> 

real 0m0.341s 
user 0m0.340s 
sys 0m0.000s 

आपका कार्यक्रम अभी भी एक मिनट को क्रियान्वित किया गया था बाद में, और मैंने छोड़ दिया।

मुख्य अंतर यह है कि मेरा एक बफर में फ़ाइल (शायद 4k-16k) को पढ़ने के लिए अंतर्निहित इटरेटर्स का उपयोग करता है और मुझे प्रत्येक पुनरावृत्ति के माध्यम से एक विशिष्ट चरित्र सौंपता है। यह बार-बार स्मृति की एक ही छोटी मात्रा का पुन: उपयोग करेगा और सीपीयू की अपेक्षाकृत छोटी कैश लाइनों को डेटा की संपूर्णता को स्टोर करने की अनुमति देगा।

संपादित

एक छोटे से परीक्षण मामले मैं बनाम स्ट्रिंग उप पटकथा each_char ज्यादातर गति अंतर को अलग करने में सक्षम था के साथ। Jörg points out that string subscripting is an O(N) operation - क्योंकि यूटीएफ -8 तारों को गुणा द्वारा अनुक्रमित नहीं किया जा सकता है क्योंकि कोई उम्मीद कर सकता है, एनएच चरित्र ढूंढना शुरू से ही शुरू होता है। इस प्रकार, आपका दृष्टिकोण ओ (एन^2) है और मेरा सिर्फ ओ (एन) था, और कि प्रदर्शन अंतर को समझाने के लिए बहुत कुछ आगे जाता है। मैं अंत में सामग्री हूं कि हमने मूल कारण निकाला है।