देखकर मैं अभी तक टिप्पणी नहीं जोड़ सकता, मैं थोड़ा और काम करूंगा और बस उन सभी का विश्लेषण करूंगा। मैं विश्लेषण को शीर्ष पर डाल रहा हूं; हालांकि, प्रासंगिक डेटा नीचे है। (नोट: यह सब 6.12.3 में भी किया जाता है - अभी तक कोई जीएचसी 7 जादू नहीं है।)
विश्लेषण:
संस्करण 1: शो ints के लिए बहुत अच्छा है, विशेष रूप से उन लोगों के रूप कम हमारे पास के रूप में है। स्ट्रिंग वास्तव में जीएचसी में सभ्य हो जाता है; हालांकि तारों को पढ़ने और फ़ाइलों को बड़े तार लिखना (या stdout, हालांकि आप ऐसा नहीं करना चाहते हैं) वे हैं जहां आपका कोड पूरी तरह से क्रॉल कर सकता है। मुझे संदेह होगा कि इट्स के लिए शो के भीतर चालाक अनुकूलन के कारण यह बहुत तेज क्यों है।
संस्करण 2: यह संकलित होने पर गुच्छा का सबसे धीमा था। कुछ समस्याएं: इसके तर्क में उलटा सख्त है। इसका अर्थ यह है कि आप अगले तत्वों की गणना करते समय सूची के पहले भाग पर गणना करने में सक्षम होने से लाभ नहीं उठाते हैं; आपको उन सभी की गणना करना है, उन्हें फ़्लिप करना है, और फिर सूची के तत्वों पर अपनी गणना (अर्थात् ('mod` 10)) करें। हालांकि यह छोटा प्रतीत हो सकता है, इससे अधिक स्मृति उपयोग हो सकता है (यहां आवंटित 5 जीबी ढेर मेमोरी को भी ध्यान दें) और धीमी गणनाएं। (लंबी कहानी कम: रिवर्स उपयोग नहीं करते।)
संस्करण 3: याद रखें कैसे मैं सिर्फ इतना कहा रिवर्स का उपयोग नहीं करते? बाहर निकलता है, अगर आप इसे बाहर ले जाते हैं, तो यह कुल निष्पादन समय 1.7 9 तक गिर जाता है - बेसलाइन की तुलना में मुश्किल से धीमा। यहां एकमात्र समस्या यह है कि जब आप संख्या में गहराई से जाते हैं, तो आप गलत दिशा में सूची की रीढ़ की हड्डी बना रहे हैं (अनिवार्य रूप से, आप रिकर्सन के साथ "इन" सूची में शामिल हो रहे हैं, क्योंकि "पर" सूचि)।
संस्करण 4: यह एक बहुत चालाक कार्यान्वयन है। आपको कई अच्छी चीजों से लाभ होता है: एक के लिए, quotRem को यूक्लिडियन एल्गोरिदम का उपयोग करना चाहिए, जो इसके बड़े तर्क में लॉगरिदमिक है। (हो सकता है कि यह तेज़ हो, लेकिन मुझे विश्वास नहीं है कि यूक्लिड की तुलना में स्थिर कारक से अधिक कुछ भी है।) इसके अलावा, आप पिछली बार चर्चा की गई सूची में शामिल हैं, ताकि आपको किसी भी सूची के भाग को हल करने की आवश्यकता न हो जाओ - सूची पूरी तरह से पूरी तरह से बनाई गई है जब आप इसे पार्स करने के लिए वापस आते हैं। जैसा कि आप देख सकते हैं, इस से प्रदर्शन लाभ।
यह कोड शायद जीएचसीआई में सबसे धीमा था क्योंकि जीएचसी सौदे में -ओ 3 ध्वज के साथ कई अनुकूलन किए गए थे, जिससे सूची तेजी से बढ़ रही थी, जबकि जीएचसीआई इनमें से कोई भी नहीं करेगा।
सबक: विपक्ष एक सूची पर सही तरीके से, मध्यवर्ती कठोरता कि नीचे संगणना धीमा कर सकते हैं के लिए देख सकते हैं, और अपने कोड के प्रदर्शन के सुक्ष्म आंकड़े देखते समय में कुछ शेष काम करते हैं। -ओ 3 झंडे के साथ भी संकलित करें: जब भी आप नहीं करते हैं, वे सभी लोग जो जीएचसी सुपर-फास्ट बनाने में बहुत घंटे लगाते हैं, आप पर बड़ी ओल 'पिल्ला आंखें मिलती हैं।
डाटा:
मैं बस, सभी चार कार्यों ली, उन्हें एक .hs फ़ाइल में फंस, और फिर उपयोग में समारोह को प्रतिबिंबित करने के लिए बदल के रूप में आवश्यक। इसके अलावा, मैंने आपकी सीमा 5e6 तक बढ़ा दी, क्योंकि कुछ मामलों में संकलित कोड 1e6 पर आधा सेकेंड से भी कम समय में चलाया जाएगा, और यह हमारे द्वारा किए जा रहे मापों के साथ ग्रैन्युलरिटी समस्याओं का कारण बन सकता है।
कंपाइलर विकल्प: ghc --make -O3 [filename] .hs जीएचसी कुछ अनुकूलन करने के लिए उपयोग करें। हम अंकों + आरटीएस-स्टेडर का उपयोग कर मानक त्रुटि में आंकड़े डंप करेंगे।
- उपयोग में कुल स्मृति: केवल 1 एमबी साधन
digits1 +RTS -sstderr
12000000
2,885,827,628 bytes allocated in the heap
446,080 bytes copied during GC
3,224 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 5504 collections, 0 parallel, 0.06s, 0.03s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.61s ( 1.66s elapsed)
GC time 0.06s ( 0.03s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.67s ( 1.69s elapsed)
%GC time 3.7% (1.5% elapsed)
Alloc rate 1,795,998,050 bytes per MUT second
Productivity 96.3% of total user, 95.2% of total elapsed
यहाँ तीन प्रमुख आंकड़े हैं:
-sstderr को डम्पिंग हमें उत्पादन है कि इस तरह दिखता है, digits1 के मामले में देता है यह संस्करण बहुत ही अंतरिक्ष-कुशल है।
- कुल समय: 1.61 का मतलब अब कुछ भी नहीं है, लेकिन हम देखेंगे कि यह अन्य कार्यान्वयन के खिलाफ कैसा दिखता है।
- उत्पादकता: यह सिर्फ 100% कम कचरा संग्रहण है; क्योंकि हम 96.3% पर कर रहे हैं इसका मतलब है कि हम वस्तुओं है कि हम स्मृति में चारों ओर झूठ बोल छोड़ के एक बहुत .. नहीं बना रहे
ठीक है, के संस्करण 2.
digits2 +RTS -sstderr
12000000
5,512,869,824 bytes allocated in the heap
1,312,416 bytes copied during GC
3,336 bytes maximum residency (1 sample(s))
13,048 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 10515 collections, 0 parallel, 0.06s, 0.04s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 3.20s ( 3.25s elapsed)
GC time 0.06s ( 0.04s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 3.26s ( 3.29s elapsed)
%GC time 1.9% (1.2% elapsed)
Alloc rate 1,723,838,984 bytes per MUT second
Productivity 98.1% of total user, 97.1% of total elapsed
पर चलते चलो ठीक है, तो हम एक दिलचस्प पैटर्न देख रहे हैं।
- स्मृति की समान मात्रा का उपयोग किया जाता है। इसका मतलब है कि यह एक बहुत अच्छा कार्यान्वयन है, हालांकि इसका मतलब यह हो सकता है कि हमें यह देखने के लिए उच्च नमूना इनपुट पर परीक्षण करने की आवश्यकता है कि क्या हम एक अंतर पा सकते हैं।
- इसमें दो बार लगते हैं। हम कुछ अटकलों पर वापस आ जाएंगे कि यह बाद में क्यों है।
- यह वास्तव में थोड़ा अधिक उत्पादक है, लेकिन यह देखते हुए कि जीसी किसी भी कार्यक्रम का एक बड़ा हिस्सा नहीं है, इससे हमें कुछ भी महत्वपूर्ण नहीं मदद मिलती है।
संस्करण 3:
digits3 +RTS -sstderr
12000000
3,231,154,752 bytes allocated in the heap
832,724 bytes copied during GC
3,292 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 6163 collections, 0 parallel, 0.02s, 0.02s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 2.09s ( 2.08s elapsed)
GC time 0.02s ( 0.02s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 2.11s ( 2.10s elapsed)
%GC time 0.7% (1.0% elapsed)
Alloc rate 1,545,701,615 bytes per MUT second
Productivity 99.3% of total user, 99.3% of total elapsed
ठीक है, तो हम कुछ अजीब पैटर्न देख रहे हैं।
- हम अभी भी उपयोग में 1 एमबी कुल मेमोरी पर हैं। इसलिए हमने कुछ भी स्मृति-अक्षम नहीं किया है, जो अच्छा है।
- हम अंक 1 पर काफी नहीं हैं, लेकिन हमें अंक 2 बहुत आसानी से हरा है।
- बहुत कम जीसी। (ध्यान रखें कि 95 भी बात को लेकर% उत्पादकता बहुत अच्छा है, इसलिए हम वास्तव में यहाँ कुछ भी बहुत महत्वपूर्ण के साथ काम नहीं कर रहे हैं।)
और अंत में, संस्करण 4:
digits4 +RTS -sstderr
12000000
1,347,856,636 bytes allocated in the heap
270,692 bytes copied during GC
3,180 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 2570 collections, 0 parallel, 0.00s, 0.01s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.09s ( 1.08s elapsed)
GC time 0.00s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.09s ( 1.09s elapsed)
%GC time 0.0% (0.8% elapsed)
Alloc rate 1,234,293,036 bytes per MUT second
Productivity 100.0% of total user, 100.5% of total elapsed
Wowza! आइए इसे तोड़ दें:
- हम अभी भी 1 एमबी कुल पर हैं। यह लगभग निश्चित रूप से इन कार्यान्वयन की एक विशेषता है, क्योंकि वे 5e5 और 5e7 के इनपुट पर 1 एमबी पर रहते हैं। आलस्य के लिए एक नियम, यदि आप करेंगे।
- हमने अपने मूल समय का लगभग 32% काट दिया, जो कि बहुत प्रभावशाली है।
- मुझे संदेह है कि यहां पर प्रतिशत सुपरल्यूमिनल कणों पर किसी भी गणना के बजाए -स्टेडर की निगरानी में ग्रैन्युलरिटी को दर्शाते हैं।
कोड संकलन के बजाय ऊपर GHCi में यह चल रहा है बहुत अलग परिणाम देता है। w/-O3 संकलित करते समय 'अंक 4'' अंकों 'से 1.8 गुना तेज है। – gawi
कारण शायद यह है कि 'showInt' को संकलक द्वारा अनुकूलित किया जा सकता है, जबकि ghci कोई अनुकूलन नहीं करेगा। – fuz
कम से कम -O2 (जैसा गावी कहा गया है) के साथ कोड संकलित करें, फिर मानदंड का उपयोग करके बेंचमार्क, और जो भी अच्छा है, उसके प्यार के लिए 'mod' का उपयोग न करें,' rem' का उपयोग करें !!! –