string - 在不收集的情况下迭代字符串的窗口

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 的最终解决方案的改进是

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 页面上的代码有点奇怪。例如，您尝试使用更冗长的

版本来处理不同长度的开始和结束标签

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

请注意，这仍然算作重叠，因此 /*/ 可能算作开始 /* 紧接着是结束 */。