द्विआधारी खोज दक्षता बनाम fortran

Question

में रैखिक खोज दक्षता यह सवाल एक रेखीय खोज सन्निहित भंडारण में एक पूर्व क्रमबद्ध सरणी के लिए एक द्विआधारी खोज की दक्षता बनाम की दक्षता के बारे में है ...

मैं एक है फोर्टन में लिखा गया आवेदन (77!)। कोड के मेरे हिस्से के लिए एक लगातार ऑपरेशन इंडेक्स को एक सरणी में ढूंढना है जैसे कि gx(i) <= xin < gx(i+1)। बयान लेबल और goto के लिए खेद है - - मैं वर्तमान में एक binary search के रूप में इस प्रकार से क्रियान्वित किया मैं टिप्पणी की है बराबर statments fortran 90 का उपयोग करके किया जाएगा क्या ...

 i=1 
     ih=nx/2 
201  continue !do while (.true.) 
      if((xin.le.gx(i)).and.(xin.gt.gx(i+1)))then !found what we want 
       ilow=i+1; ihigh=i 
       s1=(gx(ihigh)-xin)/(gx(ihigh)-gx(ilow)) 
       s2=1.0-s1 
       return 
      endif 
      if(i.ge.ih)then 
       goto 202 !exit 
      endif 
      if(xin.le.(gx(ih))then !xin is in second half of array 
       i=ih 
       ih=nx-(nx-ih)/2 
      else !xin is in first half of array 
       i=i+1 
       ih=i+(ih-i)/2 
      endif 
     goto 201 !enddo 

बहरहाल, आज, मैं पढ़ रहा था विकिपीडिया पर द्विआधारी खोज के बारे में है और मैं इस पार आया:

Binary search can interact poorly with the memory hierarchy 
(i.e. caching), because of its random-access nature. For 
in-memory searching, if the span to be searched is small, a 
linear search may have superior performance simply because 
it exhibits better locality of reference. 

मैं पूरी तरह से इस बयान समझ में नहीं आता - मेरी धारणा इसलिए यदि हम शुरू करते हैं, कि कैश फ़ेच एक समय में बड़े (ish) मात्रा में इकट्ठे हुए थे था सरणी की शुरुआत में, मैंने सोचा कि अधिकांश सरणी पहले से ही कैश में होगी (कम से कम उतनी ही होगी जितनी होगी एक रैखिक खोज के लिए), इसलिए मुझे नहीं लगता था कि इससे कोई फर्क नहीं पड़ता।

तो मेरा सवाल यह है कि क्या यह बताने का कोई तरीका है कि कौन सा एल्गोरिदम बेहतर प्रदर्शन करेगा (रैखिक या बाइनरी खोज?) क्या कोई सरणी आकार सीमा है? मैं वर्तमान में लगभग 100 तत्वों के आकार के सरणी का उपयोग कर रहा हूं ...

Answer 1

छोटे सरणी के लिए, समस्या कैश नहीं है। आप सही हैं: एक छोटी सी सरणी को तुरंत कैश किया जा सकता है।

समस्या यह है कि शाखा भविष्यवाणी द्विआधारी खोज के लिए असफल होने की संभावना है क्योंकि शाखाओं को डेटा-निर्भर तरीके से यादृच्छिक रूप से लिया जाता है या छोड़ दिया जाता है। शाखा भविष्यवाणी सीपीयू पाइपलाइन को रोकता है।

यह प्रभाव गंभीर हो सकता है। आप एक ही बाइनरी खोज शाखा (और आपको कई बाइनरी खोज शाखाएं करने की आवश्यकता होती है) में एक ही समय में 3 से 8 तत्वों को आसानी से खोज सकते हैं। सटीक ब्रेक भी बिंदु को मापने की जरूरत है।

सीपीयू पाइपलाइन को रोकना बेहद महंगा है। एक कोर i7 प्रति घड़ी चक्र के लिए 4 निर्देशों तक सेवानिवृत्त हो सकता है (12 गीगा-निर्देश प्रति सेकंड 3 गीगाहर्ट्ज पर!)। लेकिन केवल, अगर आप रोक नहीं रहे हैं।

सशर्त-चाल CPU निर्देशों का उपयोग करके शाखा-मुक्त एल्गोरिदम बाइनरी खोज कर रहे हैं। ये एल्गोरिदम मूल रूप से 32 खोज चरणों को अनलॉक करते हैं और प्रत्येक चरण में CMOV का उपयोग करते हैं (32 चरण सैद्धांतिक अधिकतम हैं)। वे शाखा मुक्त हैं लेकिन मुफ़्त नहीं हैं: प्रत्येक अगला चरण पिछले एक पर 100% निर्भर करता है ताकि सीपीयू निर्देश धारा में आगे नहीं जा सके। इसे हर समय इंतजार करना है। इसलिए वे इस समस्या को हल नहीं करते हैं, केवल इसे थोड़ा सुधारते हैं।