पर्ल

Question

में एक सरणी में बाइनरी खोज मेरे पास हेक्स संख्याओं की एक सरणी है, और मुझे अन्य नंबरों पर जाना होगा और जांचें कि वे उस सरणी में दिखाई देते हैं या नहीं। अभी मैं foreach लूप का उपयोग कर रहा हूं जो हर बार पूरे सरणी पर जाता है। पहले सरणी को सॉर्ट करके और फिर उस पर बाइनरी खोज को कार्यान्वित करके इसे तेज बनाने का कोई तरीका है।

इस समय कोड:

sub is_bad_str{ 
    my ($str, @keys) = @_; 
    my $flag = 0; 
    my ($key, $hex_num); 
     if ($str =~ m/14'h([0-9a-f][0-9a-f][0-9a-f][0-9a-f])/;){ #'# fixes bad highlighting 
    $hex_num = $1; 
     } 
    if (defined $hex_num){ 
    foreach $key (@keys){ 
     if ($hex_num =~ /\Q$key\E/i){ 
      $flag = 1; 
      last; 
     } 
    } 
    } 
    if (($flag == 0) && (defined $hex_num)){ 
    return 1;#Bad str 
    }else{ 
    return 0;#Good str 
     } 
} 

Answer 1

पर्ल में डेटा के एक सेट में कुशल थोक खोज करने की चार रणनीतियां हैं।

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

---

1. बाइनरी (आधे अंतराल) एक सरणी की खोज।

   यह स्पष्ट रूप से एक मानक एल्गोरिदमिक दृष्टिकोण है।

   प्रदर्शन लागत:

   • प्रारंभिक छंटाई के लिए O(N * log N)।
   • O(N) एक बार सॉर्ट किए गए सूची में डेटा डालने/हटाने के लिए औसत पर। पर्ल एरे सूचीबद्ध नहीं हैं इसलिए यह O(log N) नहीं है। प्रत्येक खोज के लिए
   • O(log N)।
     
     

   कार्यान्वयन: the algorithm इतना आसान है कि DIY आसान है। हमेशा के रूप में, सीपीएएन मॉड्यूल मौजूद हैं और शायद DIY के बजाय शायद इस्तेमाल किया जाना चाहिए: Search::Binary।

   ---

2. Binary Search Trees (BSTs)

   प्रदर्शन लागत:

   • प्रारंभिक छंटाई के लिए O(N * log N)।
   • O(log N) सूची में डेटा डालने/निकालने के लिए औसतन
   • O(log N) प्रत्येक खोज के लिए।

   
   

   कार्यान्वयन: Tree::Binary::Search, Tree::Treap, Tree::RedBlack: कई जायके CPAN पर मौजूद हैं। उत्तरार्द्ध दो have better average performance and smaller performance fluctuations, algorithmically।

   तुलना: डेटा बदल जाएंगे, तो आप फिर से तरह लागत से बचने के लिए BST उपयोग करना चाहिए। यदि आपका डेटा यादृच्छिक है और कभी भी क्रमबद्ध नहीं होता है, तो आप बीएसटी पर सरल बाइनरी खोज का उपयोग कर सकते हैं लेकिन बीएसटी को बेहतर प्रदर्शन किया जा सकता है यदि प्रदर्शन के हर अंतिम औंस (बीएसटी को बाइनरी खोज सूची की तुलना में तेजी से औसत खोज के लिए अनुकूलित किया जा सकता है यदि आप अपना लुकअप जानते हैं डेटा वितरण के आधार पर लागत - Wiki's "Optimal binary search trees" section देखें या यदि आपका डेटा वितरण ट्रेप या रेड/ब्लैक जैसे विशेष पेड़ों में से एक का समर्थन करता है)।

   ---

3. Abbreviated (शॉर्ट सर्किट) स्कैन लुकअप।

   ये अनचाहे सूची पर रैखिक स्कैन खोज हैं जो आइटम मिलने के बाद खोज बंद कर देते हैं।

   प्रदर्शन: O(N) यादृच्छिक डेटा के लिए खोज प्रति है, लेकिन एक तेजी से O(N) (जैसे कि, N/2) grep की तरह एक पूर्ण सूची खोज से। कोई अतिरिक्त लागत नहीं

   कार्यान्वयन:

   • Smart match ऑपरेटर (~~): वहाँ उन्हें पर्ल में करने के लिए 3 तरीके हैं। समस्या यह है कि यह केवल पर्ल 5.10 और ऊपर में उपलब्ध है।
   • आपका खुद का लूप जो next; एक बार मिला है।
   • List::MoreUtils मॉड्यूल के first() सबराउटिन।

   तुलना:

   • सबसे पहले, ऊपर 3 कार्यान्वयन के बीच, List::MoreUtils::first DIY पाश क्योंकि यह XS में लागू हो जाता है की तुलना में तेजी है, इसलिए इसका उपयोग 5.10 से पहले पर्ल संस्करणों में किया जाना चाहिए। स्मार्ट मैच शायद उतना तेज़ है, हालांकि पर्ल 5.10+ में एक या दूसरे को चुनने से पहले मैं दोनों को बेंचमार्क कर दूंगा।

     ए मेमोरी की कमी:

   • दूसरा, अन्य पद्धतियों की शॉर्ट सर्किट खोज की तुलना में, वहाँ केवल 3 किनारे मामलों में जहां यह प्रयोग किया जाना चाहिए रहे हैं। दोनों क्रमबद्ध सूची खोज, बीएसटी और हैश लुकअप में कम से कम 2*N पर मेमोरी पदचिह्न है। यदि आपको स्मृति बाधा का सामना करना पड़ता है (आपकी सूची आकार दिया गया है) N बनाम 2*N मेमोरी एक गैर-विचारणीय लागत बाधा बन जाती है, तो आप शॉर्ट सर्किट खोज का उपयोग करते हैं और समय पर प्रदर्शन दंड का भुगतान करते हैं। यह विशेष रूप से सच है जब आप बैच/लाइन-बाय-लाइन में बड़े डेटा सेट को संसाधित कर रहे हैं, ताकि पूरी चीज़ को स्मृति में पहली जगह संग्रहीत करने से बचें।

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

     सी। संक्षिप्त सर्किट खोज बीएसटी या सॉर्ट की गई सूची की खोज से बेहतर है यदि खोज की गई # सूची सूची आकार की तुलना में काफी छोटी है, इस मामले में पहली 2 विधियों (O(N log N)) की शुरुआती सॉर्टिंग लागत से अधिक होगी खोज बचत चूंकि बीएसटी बनाम रैखिक खोज की बचत O(M * N) है जहां एम खोजों की # है, यह निम्नानुसार है कि खोज की # एम औसत से बचत का एहसास करने के लिए ओ (लॉग एन) से कम होना चाहिए, लेकिन दूसरे किनारे के मामले में अधिक हो सकता है जहां डेटा वितरण के कारण औसत स्कैन लागत O(N) से कम है।

   ---

4. हैश लुकअप

   प्रदर्शन लागत:

   • O(N) + epsilon प्रारंभिक हैश निर्माण के लिए (यह सख्ती से बोला हे नहीं कर रहा है (एन) एक यादृच्छिक बड़े के लिए डेटा सेट, संभावित कुंजी टकराव के कारण। मुझे एनो पता नहीं है पर्ल के हैश कार्यान्वयन के बारे में राज्य के अलावा यह स्पष्ट करने के लिए कि यह किसी भी हैशपैप्स के लिए चिंता का विषय बन सकता है।
   • O(1) एक बार सॉर्ट किए गए सूची में डेटा डालने/निकालने के लिए औसतन (+ मुख्य टकराव के कारण प्रारंभिक हैश निर्माण के समान ईपीएसलॉन)। प्रत्येक खोज के लिए
   • O(1) (प्लस एक ही ईपीएसलॉन)।
     
     

   कार्यान्वयन:

   my %lookup = map { $_ => 1 } @list; 
   my @lookup2{ @list } =(); # Alternative method of creating a hash 
   sub find { return exists $lookup{$_[0]; } 
   

   तुलना:

   • पहले, बीएसटी बनाम लघु सर्किट खोज के साथ हैश लुकअप के साथ छोटी सर्किट खोज की तुलना करने के लिए एक ही तर्क लागू होता है। उदाहरण के लिए, आपको हमेशा दो किनारे के मामलों के अपवाद के साथ, रैखिक खोज पर हैशैप्स का उपयोग करना चाहिए (डेटा सेट ऐसा है कि O(N) के बजाय औसत सूची स्कैन O(1) बन जाता है और डेटा सेट आकार में # खोजों का अनुपात कुल बनाता है O(N) से कम खोजों की लागत हैश निर्माण के लिए आवश्यक है)।

   • दूसरा, औसत पर HashMaps जाहिर बहुत तेजी से BSTs या बाइनरी सूची खोज से कर रहे हैं। यहां एकमात्र संभावित एज केस यह है कि आप किसी भी तरह से डेटा सेट में ठोकर खाते हैं जो बाल्टी को अधिभारित करने के लिए प्रबंधन करता है और उस अतिरिक्त "ईपीएसलॉन" लागत को एक बड़े वजन में बदल देता है जो O(log N) के तहत शुरू होता है।

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

Answer 2

तुम सिर्फ ताकि आप के रूप में अच्छी सिर्फ पाशन के साथ छड़ी कर सकते हैं, तो छँटाई एक भी रैखिक स्कैन प्रदर्शन से अधिक समय लग जाएगा एक खोज करने के लिए जा रहे हैं, सरणी एक छोटी सी सरणी के लिए, या यदि आपके पास एकाधिक मिलान हो सकते हैं, तो आप grep फ़ंक्शन को भी देखना चाहेंगे; इसका उपयोग करना थोड़ा आसान है, लेकिन यह हमेशा मैच मिलने पर रोकने के बजाय उम्मीदवार मैचों की पूरी सूची की जांच करेगा।

यदि आप कई बार खोज रहे हैं, तो सरणी के मानों को हैश में डालने और हैश लुकअप करना सरणी को खोजने से तेज़ होगा, भले ही आप इसे सॉर्ट करें और बाइनरी सर्च करें (मान लें कि आप इसे बर्दाश्त कर सकते हैं स्मृति लागत, लेकिन आप लगभग निश्चित रूप से कर सकते हैं)।