Генерация строк и определение подстрок происходит очень медленно

Я хотел бы проверить определенные операции в Rust, но у меня, похоже, возникают проблемы:

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...
        }
    }

}

Вышеупомянутое занимает очень много времени, чтобы завершить ту же операцию в Ruby за 4,5 секунды:

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

puts 'Data ready.'

1_000_000.times do
    haystack.include? needle
end

Я не могу не думать, что я делаю что-то принципиально неправильно. Каким будет правильный способ сделать это в 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]

Ответы

Ответ 1

Исправление для этой проблемы было сегодня объединено. Это означает, что он должен быть частью следующего вечера, и ожидается, что он будет выпущен в Rust 1.3. Исправление возобновило реализацию Двусторонней подстроки, которую Rust использовал и адаптировал к новому API-интерфейсу в стандартной библиотеке.

Двунаправленный алгоритм является хорошим совпадением для Rust libcore, поскольку он представляет собой алгоритм поиска линейной временной подстроки, который использует O (1) пространство и не нуждается в динамическом распределении.

Конкретная реализация содержит простое дополнение, которое будет очень быстро отклонять этот конкретный запрос в вопросе (и нет, он не был написан из-за этого вопроса, он тоже был частью старого кода).

Во время настройки искатель вычисляет отпечаток пальца для иглы: для каждого байта в игле возьмите свои 6 разрядов, которые являются числом 0-63, затем установите соответствующий бит в переменной u64 byteset.

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

Так как игла содержит только "b", значение байта будет иметь только 34-й бит (98 & 63 == 34).

Теперь мы можем проверить любой байт, может ли он быть частью иглы или нет. Если соответствующий бит не установлен в byteset, игла не может совпадать. Каждый байт, который мы тестируем в стоге сена, в этом случае будет "a" (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;
}

От libcore/str/pattern.rs в ржавчине/ржавчине