शाखा भविष्यवाणी के चमत्कारों के कारण, एक बाइनरी खोज पूर्णांक की सरणी के माध्यम से एक रैखिक खोज से धीमी हो सकती है। एक ठेठ डेस्कटॉप प्रोसेसर पर, उस सरणी को बाइनरी खोज का उपयोग करना बेहतर होगा इससे पहले कि कितना बड़ा होना चाहिए? मान लें कि कई लुकअप के लिए संरचना का उपयोग किया जाएगा।कौन सी एन बाइनरी खोज एक आधुनिक सीपीयू पर रैखिक खोज से तेज हो जाती है?
मैं एक छोटे से सी ++ बेंच मार्किंग की कोशिश की है और मैं हैरान हूँ - रैखिक खोज कई दर्जन आइटम तक प्रबल रहा है, और मैं एक मामले में जहां द्विआधारी खोज उन आकार के लिए बेहतर है नहीं मिली है। शायद जीसीसी का एसटीएल अच्छी तरह से ट्यून नहीं किया गया है?
#include <vector>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
int data[] = {98, 50, 54, 43, 39, 91, 17, 85, 42, 84, 23, 7, 70, 72, 74, 65, 66, 47, 20, 27, 61, 62, 22, 75, 24, 6, 2, 68, 45, 77, 82, 29, 59, 97, 95, 94, 40, 80, 86, 9, 78, 69, 15, 51, 14, 36, 76, 18, 48, 73, 79, 25, 11, 38, 71, 1, 57, 3, 26, 37, 19, 67, 35, 87, 60, 34, 5, 88, 52, 96, 31, 30, 81, 4, 92, 21, 33, 44, 63, 83, 56, 0, 12, 8, 93, 49, 41, 58, 89, 10, 28, 55, 46, 13, 64, 53, 32, 16, 90
};
int tosearch[] = {53, 5, 40, 71, 37, 14, 52, 28, 25, 11, 23, 13, 70, 81, 77, 10, 17, 26, 56, 15, 94, 42, 18, 39, 50, 78, 93, 19, 87, 43, 63, 67, 79, 4, 64, 6, 38, 45, 91, 86, 20, 30, 58, 68, 33, 12, 97, 95, 9, 89, 32, 72, 74, 1, 2, 34, 62, 57, 29, 21, 49, 69, 0, 31, 3, 27, 60, 59, 24, 41, 80, 7, 51, 8, 47, 54, 90, 36, 76, 22, 44, 84, 48, 73, 65, 96, 83, 66, 61, 16, 88, 92, 98, 85, 75, 82, 55, 35, 46
};
bool binsearch(int i, std::vector<int>::const_iterator begin,
std::vector<int>::const_iterator end) {
return std::binary_search(begin, end, i);
}
bool linsearch(int i, std::vector<int>::const_iterator begin,
std::vector<int>::const_iterator end) {
return std::find(begin, end, i) != end;
}
int main(int argc, char *argv[])
{
int n = 6;
if (argc < 2) {
std::cerr << "need at least 1 arg (l or b!)" << std::endl;
return 1;
}
char algo = argv[1][0];
if (algo != 'b' && algo != 'l') {
std::cerr << "algo must be l or b, not '" << algo << "'" << std::endl;
return 1;
}
if (argc > 2) {
n = atoi(argv[2]);
}
std::vector<int> vv;
for (int i=0; i<n; ++i) {
if(data[i]==-1) break;
vv.push_back(data[i]);
}
if (algo=='b') {
std::sort(vv.begin(), vv.end());
}
bool (*search)(int i, std::vector<int>::const_iterator begin,
std::vector<int>::const_iterator end);
if (algo=='b') search = binsearch;
else search = linsearch;
int nf = 0;
int ns = 0;
for(int k=0; k<10000; ++k) {
for (int j=0; tosearch[j] >= 0; ++j) {
++ns;
if (search(tosearch[j], vv.begin(), vv.end()))
++nf;
}
}
std::cout << nf <<'/'<< ns << std::endl;
return 0;
}
और: लेकिन फिर -) तो यहाँ मेरी कोड है, तो हर कोई देख सकते हैं अगर मैं मूर्ख कुछ है कि समय निहायत विकृत होगा किया है ... - जो आप खोज में से किसी तरह लागू करने के लिए प्रयोग करेंगे? एक कोर की जोड़ी पर मेरे समय की मेरी एक जोड़े:
AmAir:stko aleax$ time ./a.out b 93
1910000/2030000
real 0m0.230s
user 0m0.224s
sys 0m0.005s
AmAir:stko aleax$ time ./a.out l 93
1910000/2030000
real 0m0.169s
user 0m0.164s
sys 0m0.005s
वे बहुत repeatable रहे हैं, वैसे भी ...
ओ पी का कहना है: एलेक्स, मैं अपने कार्यक्रम सिर्फ 1 के साथ सरणी को भरने के लिए संपादित .. n, std :: sort नहीं चलाएं, और लगभग 10 मिलियन (मॉड पूर्णांक विभाजन) खोजें। बाइनरी खोज पेंटियम 4 पर एन = 150 पर रैखिक खोज से दूर खींचने लगती है। चार्ट रंगों के बारे में क्षमा करें।
आप-ओ 3 के साथ संकलित कर रहे हैं? – GManNickG
यह -ओ-ओओ 3 रैखिक खोज थोड़ा खराब बनाता है, 178 एमसीसी या उससे भी अधिक, और द्विआधारी खोज थोड़ा बेहतर, 222 एमएससी या इससे भी ज्यादा है। –
बहुत से नहीं - लेकिन इसे बेंचमार्क किए बिना बिल्कुल कहना मुश्किल है।
व्यक्तिगत रूप से मैं बाइनरी खोज पसंद करना चाहता हूं, क्योंकि दो साल के समय में, जब किसी और ने आपके छोटे सरणी के आकार को चौगुनी कर दिया है, तो आपने अधिक प्रदर्शन खो दिया नहीं है। जब तक मैं बहुत विशेष रूप से नहीं जानता था कि यह अभी एक बाधा है और मुझे इसे यथासंभव तेज़ी से करने की आवश्यकता है।
ऐसा कहकर, याद रखें कि हैश टेबल भी हैं; आप उनके बारे में एक समान सवाल पूछ सकते हैं बनाम बाइनरी खोज।
इसी तरह का प्रश्न SO में पहले से मौजूद है। – joeforker
मुझे नहीं लगता कि शाखा भविष्यवाणी को कोई फर्क नहीं पड़ता क्योंकि एक रैखिक खोज में शाखाएं भी हैं। और मेरे ज्ञान के लिए कोई सिम नहीं है जो आपके लिए रैखिक खोज कर सकती है।
कहा करने के बाद कि, एक उपयोगी मॉडल है कि द्विआधारी खोज के प्रत्येक चरण के एक गुणक लागत सी है
सी लॉग एन = एन
तो ग्रहण करने के लिए किया जाएगा वास्तव में बेंचमार्किंग के बिना इसका कारण बनने के लिए, आप सी के लिए अनुमान लगाएंगे, और अगले पूर्णांक में राउंड एन करेंगे। उदाहरण के लिए यदि आप सी = 3 का अनुमान लगाते हैं, तो n = 11 पर बाइनरी खोज का उपयोग करना तेज़ होगा।
मैं विस्तार से इस सवाल की जांच की है एक मेरी निष्कर्ष in this blog post संक्षेप है।
यह – bdonlan
प्रश्न में डेटा पर तुलना की लागत पर निर्भर करेगा ओपी ने स्पष्ट रूप से स्पष्ट रूप से और स्पष्ट रूप से निर्दिष्ट किया है, वह _integers_ की एक सरणी के बारे में बात कर रहा है - आप किस अन्य भिन्नताओं के बारे में चिंतित हैं ?! –