性能

以下是搜索 767KB 的《傲慢与偏见》书籍中所有 dear 出现的基准结果。

test group_1::stream_find_iter::aho_corasick ... bench:     558,530 ns/iter (+/- 8,705)
test group_1::stream_find_iter::memchr       ... bench:      89,728 ns/iter (+/- 4,979)
test group_1::stream_find_iter::xfind        ... bench:     112,766 ns/iter (+/- 2,453)

test group_2::stream_rfind_iter::memchr      ... bench:     613,183 ns/iter (+/- 10,610)
test group_2::stream_rfind_iter::xfind       ... bench:     681,210 ns/iter (+/- 6,990)

test group_3::memory_find_iter::aho_corasick ... bench:     454,277 ns/iter (+/- 2,030)
test group_3::memory_find_iter::memchr       ... bench:      21,564 ns/iter (+/- 657)
test group_3::memory_find_iter::xfind        ... bench:      41,548 ns/iter (+/- 2,028)

test group_4::memory_rfind_iter::memchr      ... bench:     543,737 ns/iter (+/- 4,420)
test group_4::memory_rfind_iter::xfind       ... bench:     590,744 ns/iter (+/- 14,684)

• 在进行正向流搜索时，xfind 的速度大约比 memchr::memmem (第 1 组) 慢 1.3 倍，但实际上 memmem 本身是在内存缓冲区上操作的，而 xfind 则直接在流上操作。主要区别在于内存使用，xfind 通过使用仅 8KB 的缓冲区来完成工作，但 memmem 需要将整个文件内容读入大小为文件大小的缓冲区（在这种情况下为 767KB）。

• xfind在搜索内存缓冲区时没有任何优势（几乎慢2倍）（组3），因此请勿用于内存搜索。

• 当只搜索一个子串时，xfind在上述所有情况中（组1，3）都击败了aho-corasick，这在一定程度上是公平的，因为aho-corasick主要用于一次性搜索多个子串。

• 由于本质上是反向流搜索比正向流搜索慢得多（组2，4）。xfind和memmem的性能相当接近，只是内存使用不同。

示例

• 检查子串是否存在于文件中。

use std::fs::File;

fn main() -> std::io::Result<()> {
    let mut rdr = File::open("foo.txt")?;
    let found = xfind::find(b"bar", &mut rdr).is_some();

    Ok(())
}

• 获取文件中子串首次出现的10个索引。

use std::fs::File;
use std::io;

fn main() -> io::Result<()> {
    let mut rdr = File::open("foo.txt")?;
    let indexes = xfind::find_iter(b"bar", &mut rdr)
        .take(10)
        .collect::<io::Result<Vec<usize>>>()?;

    println!("{:?}", indexes);
    Ok(())
}

• 构建一个搜索器，并在多个流中搜索相同的针。

use std::fs::File;
use std::io;
use xfind::StreamFinder;

fn main() -> io::Result<()> {
    let mut f1 = File::open("foo.txt")?;
    let mut f2 = File::open("bar.txt")?;

    let mut finder = StreamFinder::new(b"baz");
    let found_in_f1 = finder.find(&mut f1).is_some();
    let found_in_f2 = finder.find(&mut f2).is_some();

    Ok(())
}

• 读取文件的最后一行，而无需将整个文件内容加载到内存中。

use std::fs::File;
use std::io::{self, Read};
use std::path::Path;

fn main() -> io::Result<()> {
    let path = "foo.txt";

    let mut buf = Vec::new();
    read_last_line(path, &mut buf)?;
    // For simplicity, we just assume the contents is valid UTF-8 and unwrap here.
    println!("{}", std::str::from_utf8(&buf).unwrap());

    Ok(())
}

fn read_last_line<P: AsRef<Path>>(
    path: P,
    buf: &mut Vec<u8>,
) -> io::Result<usize> {
    let mut f = File::open(path)?;
    let mut iter = xfind::rfind_iter(b"\n", &mut f)?;

    let read_pos = match iter.next().transpose()? {
        // if the file contains no newline, we read from the start.
        None => 0,
        // if the file ends with a newline, we need to perform another search.
        Some(pos) if pos + 1 == iter.stream_len() => {
            (iter.next().transpose()?.map(|x| x + 1)).unwrap_or(0)
        }
        // if the file doesn't end with a newline, then `pos + 1` is the `read_pos`.
        Some(pos) => pos + 1,
    };

    iter.seek_to(read_pos)?;
    f.read_to_end(buf)
}