जो तेजी से है - तत्वों की एक छोटी सरणी को सॉर्ट करना या गुणा करना?

Question

Cactus Kev's Poker Hand Evaluator के माध्यम से पढ़ना, मैं निम्नलिखित बयानों देखा:

सबसे पहले, मैंने सोचा था कि मैं हमेशा बस पहले यह मूल्यांकनकर्ता को पार करने से पहले हाथ को सॉर्ट कर सकता है; लेकिन सॉर्टिंग में समय लगता है, और मैं हाथों को सॉर्ट करने वाले किसी भी CPU चक्र को बर्बाद नहीं करना चाहता था। मुझे एक ऐसी विधि की आवश्यकता थी जिस पर ध्यान नहीं दिया गया कि पांच कार्ड किस क्रम के रूप में दिए गए थे।
...
बहुत सारे विचारों के बाद, मुझे मुख्य संख्याओं का उपयोग करने के लिए एक बुद्धिमान था। मैं तेरह कार्ड रैंकों में से प्रत्येक के लिए एक प्राइम नंबर वैल्यू असाइन करूंगा ... इस प्रणाली की सुंदरता यह है कि यदि आप अपने हाथ में प्रत्येक कार्ड के रैंक के प्राइम वैल्यू गुणा करते हैं, तो ऑर्डर के बावजूद आपको एक अद्वितीय उत्पाद मिलता है पांच कार्डों में से।
...
हमारे समय मिलीसेकंड के बाद से गुणा सबसे तेजी से गणना एक कंप्यूटर बना सकते हैं में से एक है, हम मुंडा है सैकड़ों हम मूल्यांकन से पहले प्रत्येक हाथ सॉर्ट करने के लिए मजबूर किया गया था।

मुझे इस पर विश्वास करने में कठिन समय है।

कैक्टस केवी प्रत्येक कार्ड को 4-बाइट पूर्णांक के रूप में दर्शाता है, और eval_5cards(int c1, int c2, int c3, int c4, int c5) पर कॉल करके हाथों का मूल्यांकन करता है। हम एक बाइट के रूप में कार्ड और 5-बाइट सरणी के रूप में पोकर हाथ का प्रतिनिधित्व कर सकते हैं। एक अद्वितीय हाथ पाने के लिए इस 5-बाइट सरणी को सॉर्ट करना बहुत तेज़ होना चाहिए। क्या यह उनके दृष्टिकोण से तेज़ है?

क्या होगा यदि हम उसका प्रतिनिधित्व (4-बाइट पूर्णांक के रूप में कार्ड) रखें? 5 पूर्णांक की सरणी को सॉर्ट करने से उन्हें गुणा करने से तेज़ हो सकता है? यदि नहीं, तो तत्वों की एक छोटी संख्या को क्रमबद्ध करने के लिए किस तरह के निम्न-स्तरीय अनुकूलन किए जा सकते हैं?

धन्यवाद!

सभी को अच्छा जवाब दें; मैं कुछ कठिन प्रदर्शन आंकड़े प्राप्त करने के लिए सॉर्टिंग बनाम गुणा के प्रदर्शन को बेंचमार्किंग पर काम कर रहा हूं।

Answer 1

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

हालांकि, पोकर हाथ एक एसिम्प्टोटिक समस्या नहीं है। यह सिर्फ 5 कार्ड है और वह केवल कार्ड के 13 नंबरों में से एक के बारे में परवाह करता है। भले ही गुणा सिद्धांत में जटिल है, प्रैक्टिस में इसे माइक्रोकोड में कार्यान्वित किया जाता है और यह अविश्वसनीय रूप से तेज़ है। वह क्या कर रहा है।

अब, यदि आप सैद्धांतिक प्रश्न में रुचि रखते हैं, तो गुणा के बजाय अतिरिक्त उपयोग का समाधान भी है। केवल एक ही मूल्य के 4 कार्ड हो सकते हैं, इसलिए आप मूल्यों को भी 1,5,25, ..., 5^12 असाइन कर सकते हैं और उन्हें जोड़ सकते हैं। यह अभी भी 32-बिट अंकगणित में फिट बैठता है। अन्य गणितीय गुणों के साथ अन्य अतिरिक्त-आधारित समाधान भी हैं। लेकिन यह वास्तव में कोई फर्क नहीं पड़ता, क्योंकि माइक्रोकोडेड अंकगणित कंप्यूटर कुछ भी कर रहा है उससे कहीं ज्यादा तेज़ है।

Answer 2

परीक्षण के बिना, मैं उनके तर्क से सहानुभूति व्यक्त करता हूं। सॉर्टिंग की तुलना में आप इसे 4 गुणाओं में कर सकते हैं, जो n log n है। विशेष रूप से, इष्टतम sorting network 9 तुलना की आवश्यकता है। मूल्यांकनकर्ता को कम से कम क्रमबद्ध सरणी के प्रत्येक तत्व को देखना होगा, जो कि एक और 5 संचालन है।

Answer 3

यह वास्तव में प्रासंगिक नहीं होना चाहिए, लेकिन वह सही है। सॉर्टिंग गुणा करने से ज्यादा लंबा लगता है।

असली सवाल क्या वह जिसके परिणामस्वरूप अभाज्य संख्या के साथ किया था, और कहा कि कैसे मददगार था है (यह बाँटे के बाद से मैं छँटाई से अधिक समय लग की उम्मीद करेंगे।

Answer 4

यह किसी भी छँटाई आपरेशन कि हो सकता है के बारे में सोचना मुश्किल है संख्याओं के समान सेट को गुणा करने से तेज़। प्रोसेसर स्तर पर, गुणा केवल load, load, multiply, load, multiply, ... है, शायद इसमें जमा किए गए संचयक के कुछ हेरफेर के साथ। यह रैखिक, आसानी से पाइपलाइन है, संबंधित शाखा गलत भविष्यवाणी लागतों के साथ कोई तुलना नहीं है। गुणा करने के लिए प्रति मान के बारे में 2 निर्देश। जब तक गुणा निर्देश दर्दनाक रूप से धीमा नहीं होता है, तब तक तेजी से कल्पना करना मुश्किल होता है।

Answer 5

बेशक यह आपके कंप्यूटर के सीपीयू पर बहुत निर्भर करता है, लेकिन एक विशिष्ट इंटेल सीपीयू (उदा। कोर 2 डुओ) 3 सीपीयू घड़ी चक्रों के भीतर दो 32 बिट संख्याओं को गुणा कर सकता है। एक प्रकार के एल्गोरिदम के लिए इसे हरा करने के लिए, एल्गोरिदम को 3 * 4 = 12 CPU चक्रों से तेज़ होना चाहिए, जो एक बहुत तंग बाधा है। मानक सॉर्टिंग एल्गोरिदम में से कोई भी इसे सुनिश्चित करने के लिए 12 चक्र से कम में नहीं कर सकता है।अकेले दो नंबरों की तुलना में एक सीपीयू चक्र लगेगा, नतीजे पर सशर्त शाखा एक सीपीयू चक्र भी लेगी और जो कुछ भी आप करेंगे, कम से कम एक सीपीयू चक्र लेंगे (दो कार्ड्स को स्वैप करना वास्तव में कम से कम 4 सीपीयू चक्र लेगा)। तो जीत गुणा।

बेशक यह कार्ड या तो पहले या दूसरे स्तर के कैश या यहां तक ​​कि स्मृति से कार्ड मूल्य लाने के लिए विलंबता नहीं ले रहा है; हालांकि, यह विलंबता किसी भी मामले, गुणा और सॉर्टिंग पर लागू होती है।

Answer 6

5 तत्वों को एक अनुकूलित निर्णय पेड़ का उपयोग करके सॉर्ट किया जा सकता है, जो एक सामान्य उद्देश्य सॉर्टिंग एल्गोरिदम का उपयोग करने से बहुत तेज है।

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

लेकिन अगर आप सॉर्टिंग करने के लिए कस्टम हार्डवेयर बना सकते हैं, तो तेज हो सकता है।

Answer 7

उल्लेख करने योग्य एक बात यह है कि भले ही आपके सीपीयू के गुणा निर्देश धीमे हो जाएं (या nonexistent ...) आप चीजों को और भी गति देने के लिए एक लुकअप टेबल का उपयोग कर सकते हैं।

Answer 8

बहुत सारे विचारों के बाद, मुझे मुख्य संख्याओं का उपयोग करने के लिए एक बुद्धिमानी थी। मैं तेरह कार्ड रैंकों में से प्रत्येक के लिए एक प्राइम नंबर वैल्यू असाइन करूंगा ... इस प्रणाली की सुंदरता यह है कि यदि आप अपने हाथ में प्रत्येक कार्ड के रैंक के प्राइम वैल्यू गुणा करते हैं, तो ऑर्डर के बावजूद आपको एक अद्वितीय उत्पाद मिलता है पांच कार्डों में से।

यह एक गैर-स्थितित्मक संख्या प्रणाली का एक उदाहरण है।

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

क्या होगा यदि हम उसका प्रतिनिधित्व (4-बाइट पूर्णांक के रूप में कार्ड) रखें? 5 पूर्णांक की सरणी को सॉर्ट करने से उन्हें गुणा करने से तेज़ हो सकता है?

रैम एक बाहरी संसाधन है और आमतौर पर सीपीयू की तुलना में धीमी है। स्वैप परिचालनों के कारण 5 इंच की छंटनी को हमेशा रैम पर जाना होगा। यहां फ़ंक्शन को सॉर्ट करने का ओवरहेड जोड़ें, और गुणा सभी खराब दिखने से रोकता है।

मुझे लगता है कि आधुनिक सीपीयू पूर्णांक गुणा पर सॉर्टिंग की तुलना में काफी तेज़ होगा, क्योंकि कई गुणाओं को अलग-अलग एएलयू पर एक ही समय में निष्पादित किया जा सकता है, जबकि सीपीयू को रैम से कनेक्ट करने वाली केवल एक बस है।

यदि नहीं, तो तत्वों की एक छोटी संख्या को क्रमबद्ध करने के लिए किस तरह के निम्न-स्तर अनुकूलन किए जा सकते हैं?

5 पूर्णांकों बहुत जल्दी हल हो सकता है का उपयोग कर bubble sort: qsort अधिक स्मृति (प्रत्यावर्तन के लिए) का प्रयोग करेंगे, जबकि अच्छी तरह से अनुकूलित बुलबुला तरह डी-कैश से पूरी तरह से काम करेगा।

Answer 9

जैसा कि अन्य ने इंगित किया है, अकेले सॉर्ट करना 5 मानों के लिए गुणा करने से तेज़ नहीं है। यह, उसके बाकी समाधान, हालांकि, अनदेखा करता है। 5-तत्व प्रकार को रद्द करने के बाद, वह 4888 मूल्यों की एक सरणी पर एक द्विआधारी खोज करने के लिए आगे बढ़ता है - कम से कम 12 तुलना, कभी भी आवश्यकतानुसार अधिक!

ध्यान दें कि मैं यह नहीं कह रहा हूं कि एक बेहतर समाधान है जिसमें सॉर्टिंग शामिल है - मैंने इसे पर्याप्त विचार नहीं दिया है, व्यक्तिगत रूप से - केवल यह कि अकेला सॉर्टिंग केवल समस्या का हिस्सा है।

उन्हें भी प्राइम का उपयोग करने की आवश्यकता नहीं थी। अगर उसने 4 बिट्स में प्रत्येक कार्ड के मूल्य को एन्कोड किया है, तो उसे हाथों का प्रतिनिधित्व करने के लिए 20 बिट्स की आवश्यकता होगी, जिसमें 0 से 2^20 = 1048576 की रेंज दी जाएगी, प्राइम्स का उपयोग करके उत्पादित रेंज के लगभग 1/100 वें, और पर्याप्त छोटा (हालांकि अभी भी कैश कोहेरेंसी मुद्दों का सामना करना पड़ रहा है) एक लुकअप टेबल तैयार करने के लिए।

बेशक, टेक्सास होल्डम जैसे गेम में पाए जाने वाले 7 कार्ड लेने के लिए और भी दिलचस्प संस्करण है, और उनसे 5 सर्वश्रेष्ठ कार्ड कार्ड मिल सकते हैं।

Answer 10

गुणा तेजी से है।

किसी दिए गए सरणी का गुणा हमेशा सरणी को सॉर्ट करने से तेज होगा, गुणात्मक परिणाम को सार्थक परिणाम में मानते हुए, और लुकअप तालिका अप्रासंगिक है क्योंकि कोड को पोकर हाथ का मूल्यांकन करने के लिए डिज़ाइन किया गया है, इसलिए आपको करना होगा वैसे भी क्रमबद्ध सेट पर एक लुकअप।

Answer 11

तैयार किए गए टेक्सास होल्डम 7- और 5-कार्ड मूल्यांकनकर्ता का एक उदाहरण here दस्तावेज़ीकरण के साथ पाया जा सकता है और here समझाया जा सकता है। सभी फीडबैक उसमें मिले ई-मेल पते पर आपका स्वागत है।

आपको 7-कार्ड हाथों का मूल्यांकन करते समय क्रमबद्ध करने की आवश्यकता नहीं है, और आमतौर पर (~ 9 7% समय) केवल 6 जोड़ों और कुछ बिट बदलावों से दूर हो सकता है। अलगो एक जेनरेट लुकअप टेबल का उपयोग करता है जो 9 एमबी रैम पर रहता है और निकट-तत्काल में उत्पन्न होता है। सस्ते। यह सब 32-बिट्स के अंदर किया जाता है, और 7-कार्ड मूल्यांकनकर्ता "इनलाइनिंग" मेरे लैपटॉप पर लगभग 50 मीटर यादृच्छिक रूप से जेनरेट किए गए हाथों का मूल्यांकन करने के लिए अच्छा है।

ओह, और गुणा सॉर्टिंग से तेज़ है।