🎲 🐂 👨‍👩‍👧 यह आपका हास्केल फैक्टरियल (केवल) और के लिए अच्छा है 🚜 ☪️ 👇🏼

जब पसंदीदा भाषाओं की बात आती है, तो मैं आमतौर पर कहता हूं कि, अन्य सभी चीजें समान हैं, मैं हर चीज के लिए क्रशर और हास्केल के लिए C ++ पसंद करता हूं। यह समय-समय पर जांचना उपयोगी है कि क्या यह विभाजन न्यायसंगत है, और केवल हाल ही में एक निष्क्रिय और बहुत सरल प्रश्न उत्पन्न हुआ है: एक संख्या के सभी विभाजकों का योग इस बिल की संख्या के विकास के साथ कैसे व्यवहार करेगा, कहते हैं, पहले अरब संख्याओं के लिए। इस कार्य को डराना आसान है (इसे परिणामी संख्या की चक्की कहना शर्म की बात है), इसलिए यह इस तरह के चेक के लिए एक बढ़िया विकल्प की तरह लगता है।

इसके अलावा, मेरे पास अभी भी हास्केल कोड के प्रदर्शन की सटीक भविष्यवाणी करने की क्षमता नहीं है, इसलिए यह देखने के लिए जानबूझकर खराब दृष्टिकोणों की कोशिश करना उपयोगी है कि प्रदर्शन कैसे कम हो जाएगा।

ठीक है, इसके अलावा, आप आसानी से प्रत्येक संख्या के लिए भाजक के लिए ललाट खोज की तुलना में अधिक कुशल एल्गोरिदम दिखा सकते हैं $1$ को $एन$ ।

एल्गोरिथ्म

तो, चलो एल्गोरिथ्म के साथ शुरू करते हैं।

किसी संख्या के सभी विभाजकों का योग कैसे ज्ञात करें $एन$ ? आप सभी के माध्यम से जा सकते हैं $k_1 \ in \ {1 \ dots \ lfloor \ sqrt n \ rfloor \}$ और इस तरह के हर के लिए $k_1$ शेष भाग की जाँच करें $एन$ पर $k_1$ । यदि शेष है $0$ , फिर बैटरी में जोड़ें $k_1 + k_2$ जहाँ $k_2 = \ frac {n} {k_1}$ अगर $k_1 \ neq k_2$ , और बस $k_1$ अन्यथा।

क्या यह एल्गोरिथम लागू किया जा सकता है $एन$ समय, प्रत्येक संख्या से $1$ को $एन$ ? आप निश्चित रूप से कर सकते हैं। कठिनाई क्या होगी? उस आदेश को देखना आसान है $O (n ^ \ frac {3} {2})$ विभाजन - प्रत्येक संख्या के लिए हम विभाजन की जड़ बनाते हैं, और हमारे पास संख्याएँ होती हैं $एन$ । क्या हम बेहतर कर सकते हैं? यह पता चला है कि हाँ।

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

तो, अब हमें एक से प्रत्येक संख्या के लिए झपट्टा मारने की आवश्यकता है $1$ को $एन$ इसके सभी भाजक के योग की गणना करें। ऐसा करने के लिए, सभी के माध्यम से जाना $k_1 \ in \ {1 \ dots \ lfloor \ sqrt n \ rfloor \}$ , और प्रत्येक ऐसे के लिए $k_1$ चलो सब के माध्यम से चलते हैं $k_2 \ in \ {k_1 \ dots \ lfloor \ frac {n} {k} \ rflot \}$ । प्रत्येक जोड़ी के लिए $(k_1, k_2)$ सूचकांक के साथ सेल में जोड़ें $k_1 \ cdot k_2$ अर्थ $k_1 + k_2$ अगर $k_1 \ neq k_2$ , और $k_1$ अन्यथा।

यह एल्गोरिदम बिल्कुल करता है $n ^ \ frac {1} {2}$ विभाजन, और प्रत्येक गुणा (जो विभाजन से सस्ता है) हमें सफलता की ओर ले जाता है: प्रत्येक पुनरावृत्ति पर हम कुछ बढ़ाते हैं। यह ललाट दृष्टिकोण की तुलना में बहुत अधिक प्रभावी है।

इसके अलावा, यह एक ही ललाट दृष्टिकोण होने पर, आप दोनों कार्यान्वयन की तुलना कर सकते हैं और सुनिश्चित कर सकते हैं कि वे काफी कम संख्या के लिए समान परिणाम देते हैं, जो थोड़ा आत्मविश्वास जोड़ना चाहिए।

पहला कार्यान्वयन

और वैसे, यह सीधे हास्केल में प्रारंभिक कार्यान्वयन का एक छद्म कोड है:

module Divisors.Multi(divisorSums) where import Data.IntMap.Strict as IM divisorSums :: Int -> Int divisorSums n = IM.fromListWith (+) premap IM.! n where premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1) | k1 <- [ 1 .. floor $ sqrt $ fromIntegral n ] , k2 <- [ k1 .. n `quot` k1 ] ]

Main मॉड्यूल सरल है, और मैं इसे नहीं लाता।

इसके अलावा, यहां हम केवल सबसे अधिक राशि दिखाते हैं $एन$ अन्य कार्यान्वयन के साथ तुलना में आसानी के लिए। इस तथ्य के बावजूद कि हास्केल एक आलसी भाषा है, इस मामले में सभी राशियों की गणना की जाएगी (हालांकि इसके लिए पूर्ण औचित्य इस लेख के दायरे से परे है), इसलिए यह काम नहीं करता है कि हमने अनजाने में कुछ भी नहीं गिना।

यह कितनी तेजी से काम करता है? मेरे i7 3930k पर, एक धारा में, 100,000 तत्व 0.4 s में काम करते हैं। इस मामले में, गणना पर 0.15 सेकेंड और जीसी पर 0.25 एस खर्च किया जाता है। और हम लगभग 8 मेगाबाइट मेमोरी पर कब्जा कर लेते हैं, हालांकि, जब से इंट का आकार 8 बाइट्स है, आदर्श रूप से हमारे पास 800 किलोबाइट्स होना चाहिए।

अच्छा (वास्तव में नहीं)। बढ़ती, उम, संख्याओं के साथ ये संख्या कैसे बढ़ेगी? 1'000'000 तत्वों के लिए, यह लगभग 7.5 सेकंड के लिए काम कर रहा है, कंप्यूटिंग पर तीन सेकंड और जीसी पर 4.5 सेकंड खर्च कर रहा है, साथ ही 80 मेगाबाइट (आवश्यक से 10 गुना अधिक) पर कब्जा कर रहा है। और यहां तक कि अगर हम एक दूसरे के लिए वरिष्ठ जावा सॉफ्टवेयर डेवलपर्स होने का दिखावा करते हैं और जीसी ट्यूनिंग शुरू करते हैं, तो हम तस्वीर को महत्वपूर्ण रूप से नहीं बदलेंगे। बहुत बुरा। ऐसा लगता है कि हम कभी भी एक अरब संख्याओं की प्रतीक्षा नहीं करेंगे, और हम या तो स्मृति में नहीं आते हैं: मेरी मशीन पर केवल 64 गीगाबाइट रैम है, और यदि रुझान जारी रहता है, तो इसमें लगभग 80 का समय लगेगा।

ऐसा करने में समय लगता है

C ++ विकल्प

आइए इस बारे में कुछ विचार करने की कोशिश करें कि इसके लिए प्रयास करने का क्या अर्थ है, और इसके लिए हम प्लसस पर कोड लिखेंगे।

खैर, चूंकि हमारे पास पहले से ही डीबग्ड एल्गोरिथम है, तो सब कुछ सरल है:

 #include <vector> #include <string> #include <cmath> #include <iostream> int main(int argc, char **argv) { if (argc != 2) { std::cerr << "Usage: " << argv[0] << " maxN" << std::endl; return 1; } int64_t n = std::stoi(argv[1]); std::vector<int64_t> arr; arr.resize(n + 1); for (int64_t k1 = 1; k1 <= static_cast<int64_t>(std::sqrt(n)); ++k1) { for (int64_t k2 = k1; k2 <= n / k1; ++k2) { auto val = k1 != k2 ? k1 + k2 : k1; arr[k1 * k2] += val; } } std::cout << arr.back() << std::endl; }

यदि आप अचानक इस कोड के बारे में कुछ लिखना चाहते हैं

कंपाइलर इस मामले में एक महान लूप-इनवेरिएंट कोड मोशन करता है, जो प्रोग्राम के जीवन में एक बार रूट की गणना करता है, और बाहरी लूप के पुनरावृत्ति के अनुसार n / k1 गणना करता है।

और सादगी के बारे में एक बिगाड़ने वाला

इस कोड ने मेरे लिए पहली बार काम नहीं किया, इस तथ्य के बावजूद कि मैंने एक मौजूदा एल्गोरिथ्म की नकल की। मैंने बहुत ही मूर्खतापूर्ण गलतियाँ की हैं, ऐसा लगता है कि सीधे तौर पर प्रकारों से संबंधित नहीं हैं, लेकिन फिर भी वे बने हुए थे। लेकिन यह है, विचार जोर से।

-O3 -march=native , -O3 -march=native 8, एक लाख तत्वों को 0.024 एस में संसाधित किया जाता है, जो आवंटित 8 मेगाबाइट मेमोरी पर कब्जा कर -O3 -march=native । बिलियन - 155 सेकंड, 8 गीगाबाइट मेमोरी, जैसा कि अपेक्षित था। ओह। हास्केल अच्छा नहीं है। हास्केल को बाहर फेंकने की आवश्यकता है। इस पर केवल factorials और prepromorphisms और लिखते हैं! या नहीं?

दूसरा विकल्प

जाहिर है, IntMap माध्यम से सभी उत्पन्न आंकड़ों को चलाने के लिए, IntMap , वास्तव में, एक अपेक्षाकृत साधारण नक्शा - इसे हल्के ढंग से रखने के लिए, सबसे बुद्धिमान निर्णय नहीं है (हाँ, यह वही स्पष्ट रूप से घटिया विकल्प है जो शुरुआत में उल्लेख किया गया था)। हम C ++ कोड की तरह एक सरणी का उपयोग क्यों नहीं करते हैं?

आइए कोशिश करते हैं:

 module Divisors.Multi(divisorSums) where import qualified Data.Array.IArray as A import qualified Data.Array.Unboxed as A divisorSums :: Int -> Int divisorSums n = arr A.! n where arr = A.accumArray (+) 0 (1, n) premap :: A.UArray Int Int premap = [ (k1 * k2, if k1 /= k2 then k1 + k2 else k1) | k1 <- [ 1 .. floor bound ] , k2 <- [ k1 .. n `quot` k1 ] ] bound = sqrt $ fromIntegral n :: Double

यहां हम तुरंत सरणी के अनबॉक्स संस्करण का उपयोग करते हैं, चूंकि Int काफी सरल है, और हमें इसमें आलस्य की आवश्यकता नहीं है। बॉक्सिंग संस्करण केवल arr प्रकार में भिन्न होगा, इसलिए हम मुहावरे में भी नहीं खोते हैं। इसके अलावा, बाध्य के लिए बंधन यहां अलग से बनाया गया है, लेकिन इसलिए नहीं कि कंपाइलर बेवकूफ है और एलआईसीएम नहीं करता है, लेकिन क्योंकि तब आप स्पष्ट रूप से इसके प्रकार को निर्दिष्ट कर सकते हैं और floor तर्क के डिफ़ॉल्ट के बारे में संकलक से चेतावनी से बच सकते हैं।

एक लाख तत्वों के लिए ०.०४५ एस (केवल प्लसस से दो गुना बदतर!)। मेमोरी के 8 मेगाबाइट, जीसी (!) में शून्य मिलीसेकंड। बड़े आकार में, प्रवृत्ति बनी रहती है - C ++ की तुलना में लगभग दो गुना धीमी, और समान मात्रा में मेमोरी। महान परिणाम! लेकिन क्या हम बेहतर कर सकते हैं?

यह पता चला है कि हाँ। accumArray सूचकांकों की जाँच करता है, जो हमें इस मामले में करने की आवश्यकता नहीं है - निर्माण में सूचकांक सही हैं। चलो कॉल को बदलने का प्रयास करें।

 module Divisors.Multi(divisorSums) where import qualified Data.Array.Base as A import qualified Data.Array.IArray as A import qualified Data.Array.Unboxed as A divisorSums :: Int -> Int divisorSums n = arr A.! (n - 1) where arr = A.unsafeAccumArray (+) 0 (0, n - 1) premap :: A.UArray Int Int premap = [ (k1 * k2 - 1, if k1 /= k2 then k1 + k2 else k1) | k1 <- [ 1 .. floor bound ] , k2 <- [ k1 .. n `quot` k1 ] ] bound = sqrt $ fromIntegral n :: Double

जैसा कि आप देख सकते हैं, खरोंच से अनुक्रमित होने की आवश्यकता को छोड़कर, परिवर्तन न्यूनतम हैं (जो, मेरी राय में, पुस्तकालय एपीआई में एक बग है, लेकिन यह एक और सवाल है)। प्रदर्शन क्या है?

एक लाख तत्व - 0.021 एस (वाह, त्रुटि के मार्जिन के भीतर, लेकिन पेशेवरों की तुलना में तेज!)। स्वाभाविक रूप से, मेमोरी के समान 8 मेगाबाइट, जीसी में वही 0 एमएस।

अरब तत्व - 152 एस (ऐसा लगता है कि यह वास्तव में प्लसस की तुलना में तेज है!)। 8 गीगाबाइट से थोड़ा कम। जीसी में 0 एमएस। कोड अभी भी मुहावरेदार है। मुझे लगता है कि हम कह सकते हैं कि यह एक जीत है।

निष्कर्ष में

सबसे पहले, मुझे आश्चर्य था कि एक unsafe संस्करण के साथ accumArray को बदलने से इस तरह की वृद्धि होगी। 10-20 प्रतिशत की उम्मीद करना अधिक उचित होगा (आखिरकार, प्लसस में, operator[] जगह operator[] साथ at() प्रदर्शन में उल्लेखनीय कमी नहीं देता है), लेकिन आधे से नहीं!

दूसरी बात, मेरी राय में, यह वास्तव में अच्छा है कि एक परस्पर चिपके हुए बिना एक बहुत ही अच्छा स्वच्छ कोड प्रदर्शन के इस स्तर तक पहुँचता है।

तीसरा, निश्चित रूप से, आगे के अनुकूलन संभव हैं, और सभी स्तरों पर। मुझे यकीन है, उदाहरण के लिए, आप प्लसस पर कोड से थोड़ा अधिक निचोड़ सकते हैं। हालांकि, मेरी राय में, ऐसे सभी बेंचमार्क में, प्रयास के बीच संतुलन (और कोड की मात्रा) और परिणामस्वरूप निकास महत्वपूर्ण है। अन्यथा, सब कुछ अंततः एलएलवीएम जेआईटी की चुनौती या कुछ इसी तरह से परिवर्तित होता है। इसके अलावा, इस समस्या को हल करने के लिए निश्चित रूप से अधिक कुशल एल्गोरिदम हैं, लेकिन यहां प्रस्तुत एक छोटी सोच का परिणाम इस छोटे से रविवार के साहसिक कार्य के लिए भी काम करेगा।

चौथा, मेरा पसंदीदा: प्रकार प्रणाली विकसित करने की आवश्यकता है। unsafe की जरूरत नहीं है, एक प्रोग्रामर के रूप में मैं साबित कर सकता हूँ कि k_1 * k_2 <= n सभी k_1, k_2 लूप में है। भरोसेमंद रूप से टाइप की गई भाषाओं की एक आदर्श दुनिया में, मैं इस प्रमाण का निर्माण सांख्यिकीय रूप से करूंगा और इसे संबंधित फ़ंक्शन में पास करूंगा, जो रनटाइम में चेक की आवश्यकता को हटा देगा। लेकिन, अफसोस, हास्केल में पूर्ण-जावितिपोव नहीं हैं, और उन भाषाओं में जहां जावितिपि हैं (और जो मुझे पता है), कोई array और एनालॉग नहीं हैं।

पांचवीं, मैं अन्य प्रोग्रामिंग भाषाओं को इन भाषाओं में पास-बेंचमार्क के लिए अर्हता प्राप्त करने के लिए पर्याप्त नहीं जानता, लेकिन मेरे एक मित्र ने अजगर में एक एनालॉग लिखा था। लगभग ठीक सौ बार धीमा, और स्मृति से भी बदतर। और एल्गोरिथ्म अपने आप में बेहद सरल है, इसलिए यदि कोई जानकार गो, रस्ट, जूलिया, डी, जावा, टिप्पणियों में एक एनालॉग या कुछ और लिखता है और एक तुलना साझा करता है, उदाहरण के लिए, सी ++ के साथ - उनके मशीन पर कोड - यह शायद बहुत अच्छा होगा ।

पुनश्च: थोड़ा clickbait हेडर के लिए क्षमा करें। मैं कुछ भी बेहतर नहीं कर सकता था।

यह आपका हास्केल फैक्टरियल (केवल) और के लिए अच्छा है

एल्गोरिथ्म

पहला कार्यान्वयन

C ++ विकल्प

दूसरा विकल्प

निष्कर्ष में

More articles: