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

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表明这是一个合理的停止点。