उत्पन्न तार और सबस्ट्रिंग की पहचान बहुत धीमी गति से

Question

मैं जंग में बेंचमार्क निश्चित संचालनों के लिए करना चाहते हैं, लेकिन मैं लग रहे कुछ परेशानी हो रही किया जाना है रूबी में ऑपरेशन 4.5 सेकंड में खत्म:

needle = 'b' * 100 
haystack = 'a' * 100_000 

puts 'Data ready.' 

1_000_000.times do 
    haystack.include? needle 
end 

मैं मदद नहीं कर सकता लेकिन लगता है कि मैं कुछ मौलिक रूप से गलत कर रहा हूँ। जंग में ऐसा करने का उचित तरीका क्या होगा?

rustc 1.0.0 (a59de37e9 2015-05-13) (built 2015-05-14) 
ruby 2.2.2p95 (2015-04-13 revision 50295) [x86_64-linux] 

Answer 1

इस मुद्दे के लिए एक फ़िक्स आज विलय कर दिया गया था। इसका मतलब है कि यह अगली रात का हिस्सा होना चाहिए, और जंग 1.3 में रिलीज होने की उम्मीद है। फिक्स ने Two-way substring search कार्यान्वयन को पुनर्जीवित किया कि जंग को मानक पुस्तकालय में नए Pattern API पर उपयोग और अनुकूलित किया गया था।

दो-तरफा एल्गोरिदम रस्ट के लिबकोर के लिए एक अच्छा मैच है क्योंकि यह एक रैखिक समय है जो खोज एल्गोरिदम है जो ओ (1) स्पेस का उपयोग करता है और उसे गतिशील आवंटन की आवश्यकता नहीं होती है।

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

सेटअप के दौरान खोजकर्ता सुई के लिए फिंगरप्रिंट का एक प्रकार की गणना करता है: सुई में प्रत्येक बाइट के लिए, अपनी कम 6 बिट है, जो एक संख्या 0-63 है लेते हैं, तो u64 चर byteset में इसी बिट निर्धारित किया है।

let byteset = needle.iter().fold(0, |a, &b| (1 << ((b & 0x3f) as usize)) | a); 

के बाद सुई केवल 'बी का होता है, byteset का मूल्य केवल 34 वीं बिट सेट (98 & 63 == 34) होगा।

अब हम किसी भी बाइट का परीक्षण कर सकते हैं चाहे वह सुई का हिस्सा हो या नहीं। यदि इसका संबंधित बिट byteset में सेट नहीं है, तो सुई मेल नहीं खा सकती है। प्रत्येक मामले में हम इस मामले में घास के मैदान में परीक्षण करेंगे 'ए' (97 & 63 == 33), और यह मेल नहीं खा सकता है। तो एल्गोरिदम एक बाइट पढ़ेगा, इसे अस्वीकार कर देगा, और फिर सुई की लंबाई को छोड़ देगा।

fn byteset_contains(&self, byte: u8) -> bool { 
    (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0 
} 

// Quickly skip by large portions unrelated to our substring 
if !self.byteset_contains(haystack[self.position + needle.len() - 1]) { 
    self.position += needle.len(); 
    continue 'search; 
} 

From libcore/str/pattern.rs in rust-lang/rust