Benchmarking of algorithms for set partitions
यह शोध पत्र सेट विभाजनों (set partitions) को सूचीबद्ध करने वाले एल्गोरिदम की समीक्षा करता है, उनकी गणनाओं के लिए अनुमानित सूत्र प्रदान करता है, और बेंचमार्किंग परीक्षणों के आधार पर डजोकिक एट अल. (Djokic et al.) के एल्गोरिदम की अनुशंसा करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आपके पास अलग-अलग लेगो ब्रिक्स (Lego bricks) का एक डिब्बा है। आपका काम इन ब्रिक्स को आपस में समूह बनाने के हर एक संभव तरीके को पता लगाना है। आप प्रत्येक ब्रिक को अपने छोटे से ढेर में रख सकते हैं, आप उन सभी को एक विशाल मीनार में स्टैक कर सकते हैं, या आप उन्हें विभिन्न समूहों में मिला सकते हैं। गणित की दुनिया में, इसे सेट पार्टीशन (set partition) कहा जाता है।
यह शोध पत्र मूल रूप से उन कंप्यूटर प्रोग्रामों के लिए एक "रेस रिपोर्ट" है जो इन सभी संभावित समूहों को सूचीबद्ध करने की कोशिश करते हैं। यहाँ लेखकों द्वारा दी गई जानकारी का विवरण है, जिसे सरल उपमाओं (analogies) का उपयोग करके समझाया गया है:
1. समस्या: एक तेजी से बढ़ती पहेली
लेखक बताते हैं कि जबकि कुछ वस्तुओं के लिए समूहों को सूचीबद्ध करना आसान लगता है, लेकिन संभावनाओं की संख्या अविश्वसनीय रूप से तेजी से बढ़ती है।
- उपमा: इसे 'म्यूजिकल चेयर्स' के खेल की तरह समझें, लेकिन लोगों के बजाय इसमें संख्याओं का उपयोग हो रहा है। केवल 3 वस्तुओं के साथ, उन्हें समूह बनाने के 5 तरीके हैं। लेकिन जब तक आपके पास 17 वस्तुएं होती हैं, तब तक उनके समूह बनाने के लगभग 82 अरब अलग-अलग तरीके हो जाते हैं।
- वास्तविकता: यदि आपके पास 17 या 18 से अधिक वस्तुएं हैं, तो एक उचित समय में हर एक समूह को सूचीबद्ध करना कंप्यूटर के लिए असंभव हो जाता है। हालांकि, छोटी संख्याओं के लिए, कंप्यूटर से यह करवाना बहुत उपयोगी होता है, विशेष रूप से बॉक्स पैक करने या शिफ्ट शेड्यूल करने जैसे अनुकूलन (optimization) कार्यों के लिए।
2. संभावनाओं की गणना (बेल्स नंबर्स - Bell Numbers)
एल्गोरिदम की दौड़ शुरू करने से पहले, लेखकों को यह जानने का एक तरीका चाहिए था कि उन्हें कितने समूहों की उम्मीद करनी चाहिए। इन संख्याओं को बेल्स नंबर्स (Bell Numbers) कहा जाता है।
- चुनौती: सटीक संख्या की गणना करना कठिन है, इसलिए गणितज्ञ अनुमान लगाने के लिए सूत्रों का उपयोग करते हैं।
- खोज: लेखकों ने कई जटिल गणितीय सूत्रों का परीक्षण किया। उन्होंने पाया कि एक विशिष्ट सूत्र (जिसमें "लैम्बर्ट डब्लू फंक्शन" नामक एक विशेष गणितीय फलन शामिल है) अविश्वसनीय रूप से सटीक है। यह एक ऐसे मौसम पूर्वानुमान की तरह है जो छोटी संख्याओं के लिए भी बिल्कुल सटीक होता है। उन्होंने यह भी पाया कि एक सरल सूत्र भी है जो छोटे समूहों के लिए अच्छा काम करता है, लेकिन जैसे-जैसे संख्याएँ बहुत बड़ी होती जाती हैं, वह थोड़ा ढीला पड़ जाता है।
3. दौड़: चार एल्गोरिदम की प्रतिस्पर्धा
शोध पत्र का मुख्य भाग एक "बेंचमार्क" है, जो वास्तव में एक समयबद्ध दौड़ (timed race) है। लेखकों ने इन समूहों को सूचीबद्ध करने के लिए डिज़ाइन किए गए चार अलग-अलग कंप्यूटर प्रोग्रामों (एल्गोरिदम) को लिया और उन्हें विभिन्न कंप्यूटरों (लैपटॉप, डेस्कटॉप, क्लाउड सर्वर) पर विभिन्न सॉफ्टवेयर टूल्स (कंपाइलर्स) और ऑपरेटिंग सिस्टम (विंडोज और लिनक्स) का उपयोग करके चलाया।
चार धावक ये थे:
- हचिंसन का एल्गोरिदम (Hutchinson's Algorithm): "पुराना खिलाड़ी।" यह दशकों पुराना क्लासिक तरीका है।
- सेम्बा का एल्गोरिदम (Semba's Algorithm): एक आधुनिक, तेज़ दावेदार।
- एर का एल्गोरिदम (Er's Algorithm): एक अन्य आधुनिक, तेज़ दावेदार।
- जोकिक आदि का एल्गोरिदम (Djokic et al.'s Algorithm): नया चुनौती देने वाला।
परिणाम:
- पुराना खिलाड़ी (Hutchinson): यह प्रोग्राम अन्य की तुलना में काफी धीमा था। यह भारी जूतों में मैराथन दौड़ने जैसा है। लेखकों ने स्पष्ट रूप से कहा है: इसका उपयोग न करें।
- आधुनिक धावक (Semba, Er, Djokic): ये बहुत तेज़ थे।
- विजेता: जोकिक का एल्गोरिदम (Djokic's algorithm) ने स्वर्ण पदक जीता। यह पूरे क्षेत्र में सबसे तेज़ था।
4. "इंजन" भी मायने रखता है
लेखकों ने यह भी खोजा कि कोड चलाने वाला "इंजन" कार के खुद के होने जितना ही महत्वपूर्ण है।
- ऑपरेटिंग सिस्टम: लिनक्स (Linux) पर चलने वाला कोड विंडोज (Windows) की तुलना में आम तौर पर तेज़ था।
- कंपाइलर्स (Compilers): कोड को मशीन भाषा में अनुवाद करने वाला टूल एक बड़ा अंतर पैदा करता है। उदाहरण के लिए, एक विशिष्ट एल्गोरिदम पर, इंटेल कंपाइलर मानक GNU कंपाइलर की तुलना में बहुत तेज़ था, लेकिन दूसरे एल्गोरिदम के लिए, GNU कंपाइलर बेहतर था।
- सीख: सर्वोत्तम गति प्राप्त करने के लिए, आपको सही एल्गोरिदम और सही सॉफ्टवेयर सेटिंग्स दोनों की आवश्यकता होती है।
5. अंतिम सिफारिश
हजारों परीक्षणों के बाद, लेखकों के पास किसी भी व्यक्ति के लिए जो यह काम करना चाहता है, एक स्पष्ट निर्णय है:
- जोकिक आदि (Djokic et al.) के एल्गोरिदम का उपयोग करें। यह सबसे तेज़ है, यह अपेक्षाकृत छोटा (लिखने में आसान) है, और इसे लागू करना आसान है।
- सुझाव: सुनिश्चित करें कि आपका कंप्यूटर "हाई परफॉरमेंस" मोड (कंपाइलर ऑप्टिमाइज़ेशन लेवल 2 या उससे अधिक) पर सेट है और, यदि आप लिनक्स पर हैं, तो सर्वोत्तम परिणामों के लिए इंटेल कंपाइलर का उपयोग करें।
उन्होंने क्या कवर नहीं किया
लेखक बुनियादी बातों तक ही सीमित रहने में सावधान रहे। उन्होंने उन एल्गोरिदम का परीक्षण नहीं किया जो विशिष्ट सीमाओं वाले समूहों को खोजने का प्रयास करते हैं (जैसे "समूहों में अधिकतम 3 आइटम हो सकते हैं"), और उन्होंने "ग्रे कोड्स" (Gray codes) नामक एक अलग प्रकार की व्यवस्था प्रणाली को भी नहीं देखा। ये भविष्य के शोध के लिए छोड़े गए हैं।
संक्षेप में: यदि आपको वस्तुओं के एक छोटे सेट को समूहबद्ध करने के हर तरीके को सूचीबद्ध करने के लिए एक कंप्यूटर की आवश्यकता है, तो पुराने तरीकों का उपयोग न करें। जोकिक एल्गोरिदम का उपयोग करें, लिनक्स पर चलाएं और इंटेल कंपाइलर का उपयोग करें, और आप पलक झपकते ही अपना काम पूरा कर लेंगे।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।