在不收集字符串的窗口中進行迭代

Question

我需要迭代並比較未知字符串長度的窗口。我目前的實現工作，但我已經做了性能測試，並且效率非常低。該方法需要保證對Unicode是安全的。

fn foo(line: &str, patt: &str) { 
    for window in line.chars().collect::<Vec<char>>().windows(patt.len()) { 
     let mut bar = String::new(); 
     for ch in window { 
      bar.push(*ch); 
     } 
     // perform various comparison checks 
    } 
} 

Answer 1

上Shepmaster的最終解決方案，這顯著開銷降低（由倍〜1.5）的改進，是

fn foo(line: &str, pattern: &str) -> bool { 
    let pattern_len = pattern.chars().count(); 

    let starts = line.char_indices().map(|(i, _)| i); 
    let mut ends = line.char_indices().map(|(i, _)| i); 

    // Itertools::dropping 
    if pattern_len != 0 { ends.nth(pattern_len - 1); } 

    for (start, end) in starts.zip(ends.chain(Some(line.len()))) { 
     let bar = &line[start..end]; 
     if bar == pattern { return true } 
    } 

    false 
} 

這就是說，從GitHub的頁面代碼是有點奇怪。例如，您嘗試處理不同長度的打開和關閉標籤與wordier版本的

let length = cmp::max(comment.len(), comment_end.len()); 

但你的支票，然後

if window.contains(comment) 

可能引發多次！

更好的辦法是迭代縮小的切片。在小例子，這將是

fn foo(line: &str, pattern: &str) -> bool { 
    let mut chars = line.chars(); 
    loop { 
     let bar = chars.as_str(); 
     if bar.starts_with(pattern) { return true } 
     if chars.next().is_none() { break } 
    } 

    false 
} 

（請注意，這由〜1.5的另一個因素再次結束了再次提高了性能。）

，並在更大的例子，這會是這樣的

let mut is_in_comments = 0u64; 

let start = match line.find(comment) { 
    Some(start) => start, 
    None => return false, 
}; 

let end = match line.rfind(comment_end) { 
    Some(end) => end, 
    None => return true, 
}; 

let mut chars = line[start..end + comment_end.len()].chars(); 
loop { 
    let window = chars.as_str(); 

    if window.starts_with(comment) { 
     if nested { 
      is_in_comments += 1; 
     } else { 
      is_in_comments = 1; 
     } 
    } else if window.starts_with(comment_end) { 
     is_in_comments = is_in_comments.saturating_sub(1); 
    } 

    if chars.next().is_none() { break } 
} 

請注意，這仍然會計算重疊，因此/*/可能會計爲開頭/*，緊接着是關閉*/。

Answer 2

的方法必須保證是對Unicode的安全。

pattern.len()返回字節數的字符串需要，所以它已經可能是你的代碼是在做錯誤的事情。我可能會建議你檢查一下像QuickCheck這樣的工具來生成包含Unicode的任意字符串。

這裏是我的測試工具：

use std::iter; 

fn main() { 
    let mut haystack: String = iter::repeat('a').take(1024*1024*100).collect(); 
    haystack.push('b'); 

    println!("{}", haystack.len()); 
} 

而且我通過cargo build --release && time ./target/release/x編譯和時機。創建字符串本身需要0.274s。

我用這個版本的原密碼只是有某種比較：

fn foo(line: &str, pattern: &str) -> bool { 
    for window in line.chars().collect::<Vec<char>>().windows(pattern.len()) { 
     let mut bar = String::new(); 
     for ch in window { 
      bar.push(*ch); 
     } 

     if bar == pattern { return true } 
    } 

    false 
} 

這需要4.565s，或4.291s只是foo。

我看到的第一件事是在內部循環上發生了很多分配。該代碼爲每次迭代創建，分配和銷燬String。讓我們重用String分配：

fn foo_mem(line: &str, pattern: &str) -> bool { 
    let mut bar = String::new(); 

    for window in line.chars().collect::<Vec<char>>().windows(pattern.len()) { 
     bar.clear(); 
     bar.extend(window.iter().cloned()); 

     if bar == pattern { return true } 
    } 

    false 
} 

這需要2.155s或1.881s只是foo_mem。

繼續，另一個外部分配是所有處的String的分配。我們已經有看起來像正確的事情字節，因此我們重新使用他們：

fn foo_no_string(line: &str, pattern: &str) -> bool { 
    let indices: Vec<_> = line.char_indices().map(|(i, _c)| i).collect(); 
    let l = pattern.chars().count(); 

    for window in indices.windows(l + 1) { 
     let first_idx = *window.first().unwrap(); 
     let last_idx = *window.last().unwrap(); 

     let bar = &line[first_idx..last_idx]; 

     if bar == pattern { return true } 
    } 

    // Do the last pair 
    { 
     let last_idx = indices[indices.len() - l]; 

     let bar = &line[last_idx..]; 
     if bar == pattern { return true } 
    } 

    false 
} 

此代碼是醜陋和unidiomatic。我很確定有些想法（我現在懶得做）會使它看起來好多了。

這需要1.409s或1.135s只爲foo_mem。

由於這是〜25％原始時間，Amdahl's Law表明這是一個合理的停止點。