ciągi generowania i identyfikowania podciągi jest bardzo powolny

Question

Chciałbym porównawczych niektórych operacji w Rust, ale wydaje się mieć pewne problemy:

fn main(){ 

    let needle = (0..100).map(|_| "b").collect::<String>(); 
    let haystack = (0..100_000).map(|_| "a").collect::<String>(); 

    println!("Data ready."); 

    for _ in 0..1_000_000 { 
     if haystack.contains(&needle) { 
      // Stuff... 
     } 
    } 

} 

Powyższy zajmuje bardzo dużo czasu, aby zakończyć podczas gdy ta sama operacja w Ruby zakończy w około 4,5 sekundy:

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

puts 'Data ready.' 

1_000_000.times do 
    haystack.include? needle 
end 

nie mogę pomóc, ale myślę, że robię coś fundamentalnie złego. Jaki byłby właściwy sposób robienia tego w Rust?

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

Poprawka dla tego numeru została dzisiaj scalona. Oznacza to, że powinien on być częścią następnego wieczoru, i zostanie prawdopodobnie ujawniony w Rust 1.3. Poprawka przywróciła implementację, którą Rust posiadał i dostosowała ją do nowej wersji Pattern API w standardowej bibliotece.

Algorytm dwukierunkowy dobrze pasuje do libcore Rusta, ponieważ jest to algorytm wyszukiwania podłańcuchowego czasu, który wykorzystuje przestrzeń O (1) i nie wymaga alokacji dynamicznej.

Konkretna implementacja zawiera prosty dodatek, który bardzo szybko odrzuci to pytanie w pytaniu (i nie, nie został napisany z powodu tego pytania, był także częścią starego kodu).

Podczas konfiguracji wyszukiwarka oblicza rodzaj odcisku palca dla igły: Dla każdego bajtu w igle, weź jego niskie 6 bitów, które jest liczbą 0-63, a następnie ustaw odpowiedni bit w zmiennej u64byteset.

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

Ponieważ igła zawiera tylko „B, wartość byteset będzie miał tylko 34. ustawiony bit (98 & 63 == 34).

Teraz możemy przetestować dowolny bajt, czy może być częścią igły, czy nie. Jeśli odpowiadający mu bit nie jest ustawiony w byteset, igła nie może się dopasować. Każdy bajt, który przetestujemy w stogu siana w tym przypadku będzie "a" (97 & 63 == 33) i nie może się równać. Tak więc algorytm odczyta jeden bajt, odrzuci go, a następnie pominie długość igły.

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