क्या रिचर्ड हेंड्रिक बेवकूफ थे, या रैखिक खोज बनाम द्विआधारी

मुझे लगता है, हेबे पर सिलिकॉन वैली श्रृंखला के प्रशंसक हैं। इस हफ्ते, सभी छह सत्रों में पहली बार, उन्होंने एक बड़ा कोड दिखाया - ज़ाहिर है, मैं तुरंत यहां चर्चा करना चाहता हूं।

मुख्य चरित्र रिचर्ड हेंड्रिक्स को अपमानित करना चाहते हैं, उनके पूर्व मालिक एक बैठक में अपने पुराने कोड के टुकड़े को दिखाते हैं। वहां, पहले से ही सॉर्ट किए गए डेटा पर एक रेखीय खोज लागू होती है - इसलिए कार्य पूरा हो जाएगा, लेकिन यह बहुत अक्षम दिखता है।

रिचर्ड खुद यह तर्क नहीं देते कि कोड खराब है। हालांकि, श्रृंखला के दर्शकों के बीच, उनके फैसले में अचानक डिफेंडर्स मिले, और अब मुझे आश्चर्य है कि हबर अपनी स्थिति के बारे में क्या सोचते हैं।

रिचर्ड का ज्ञात कोड स्निपेट इस तरह दिखता है:

int index = 0; while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index); return index < sortedList.size() ? index : -1; 

यहां, एक रेखीय खोज किसी क्रमबद्ध सूची के प्रत्येक तत्व के बदले में मुड़ जाती है, जब तक कि वह दाईं ओर न हो जाए। एक नियम के रूप में, वे सॉर्ट किए गए डेटा पर द्विआधारी खोज पसंद करते हैं, जो कि हर बार आधे में सेट को विभाजित करता है, एक पूरे के रूप में अनुपयुक्त आधे को छोड़ देता है (क्योंकि डेटा की मात्रा में वृद्धि के साथ, रैखिक में पुनरावृत्तियों की संख्या बाइनरी की तुलना में बहुत तेजी से बढ़ जाती है)। लेकिन सबरेडिट / आर / सिलिकॉनविलेहबो में निम्नलिखित टिप्पणी दिखाई दी:

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

यह रिपोर्ट बहुत दिलचस्प है और वास्तविक प्रदर्शन माप के कुछ आश्चर्यजनक परिणाम दिखाती है। ”

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

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

समझने के लिए, मैंने Reddit द्वारा उद्धृत एक रिपोर्ट खोली। जैसा कि वादा किया गया था, यह दिलचस्प निकला (आश्चर्य की बात नहीं, यह देखते हुए कि यह आंद्रेई अलेक्जेंड्रेस्कु की एक रिपोर्ट है), लेकिन एक हिस्से को देखने और बाकी के माध्यम से क्लिक करने के बाद, मैंने वहां द्विआधारी और रैखिक खोज के तुलनात्मक माप नहीं देखे।

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

इस बारे में आधुनिक इंटरनेट क्या कहता है, यह पता चला - लेकिन मूल रूप से स्टैक ओवरफ्लो के जवाब मिले, जहां वे लिखते हैं कि "बाइनरी का उपयोग करें, कम पुनरावृत्तियों।" ऐसे मामले भी थे, जहाँ उन्होंने बेंचमार्क करने की कोशिश की, लेकिन मुझे बहुत आश्वस्त नहीं लग रहे थे।

यहां, निश्चित रूप से, विकल्प यह है कि "आपको वास्तविक हार्डवेयर पर सब कुछ देखने के लिए खुद को बेंचमार्क करना होगा।"

लेकिन अगर DotNext की मेरी सभी यात्राओं के लिए मैंने दो प्रदर्शन-सचेत एंड्रीव्स (अलेक्जेंड्रेस्कु और अकिंशीना ) से कुछ सीखा है, तो यह अहसास होता है कि लोग कितनी बार गलत तरीके से बेंचमार्क करते हैं और कितना खाते में नहीं लेते हैं। इसलिए, मुझे बेंचमार्क के साथ यादृच्छिक इंटरनेट पोस्ट पर कम भरोसा है, लेकिन खुद को और भी कम।

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

और अगर कोई ज्ञानी टिप्पणीकार नहीं हैं, तो मुझे अगले डोटनेक्स्ट पर अकिंशिन को बैटरी से जोड़ना होगा और बेंचमार्क बनाना होगा।