rust - 二进制搜索大块向量

Question

我有一个ipv4地址文件，众所周知，每个文件都是4个字节。我希望对文件内容进行二进制搜索以找到给定的IP地址。 Rust具有内置的二进制搜索功能，但它不允许您传递len，而是从向量中读取它。

我试图调整内置的rust二进制搜索，但是有点迷路了。这是我到目前为止的位置。也许有一种使用内置方法的方法？

fn binary_search(s: &Vec<&u8>, x: &u32) -> Result<usize, usize> {
    let f = |p: &[u8]| p.cmp(x); // need to compare byte slices somehow

    let mut size = s.len() / 4;
    if size == 0 {
        return Err(0);
    }
    let mut base = 0usize;
    while size > 1 {
        let half = size / 2;
        let mid = base + half;

        let cmp = f(s[mid..mid+4]);

        base = if cmp == Greater { base } else { mid };
        size -= half;
    }

    let cmp = f(s[base..base+4]);

    if cmp == Equal {
        Ok(base)
    } else {
        Err(base + (cmp == Less) as usize)
    }
}

Answer 1

最好有一个每个地址包含一个元素的切片，它可以是4字节数组([u8; 4])，某些等效结构(hey，Ipv4Addr)或只是u32。不幸的是，我认为尚无法将长度为4的&[u8]重新解释为&[[u8; 4]](其他选项需要对齐)。不过，您可以在分块读取文件的同时执行此转换。

因此，首先，在一个等效的示例程序中:

use std::net::Ipv4Addr;

fn main() {
    let vec: Vec<Ipv4Addr> = vec![
        [10, 0, 0, 0].into(),
        [20, 0, 0, 0].into(),
        [30, 0, 0, 0].into(),
    ];
    println!("vec {:?}", vec);

    let found = vec.binary_search(&Ipv4Addr::from_str("20.0.0.0").unwrap());

    println!("found {:?}", found);
}

(playground)

然后从文件中读取将类似于:

let mut vec: Vec<Ipv4Addr> = vec![];

loop {
    let mut address = [0; 4];

    match f.read_exact(&mut address) {
        Ok(()) => {},
        Err(err) if err.kind() == ErrorKind::UnexpectedEof => break,
        err => err?,
    }

    vec.push(address.into());
}

(尽管该字节有些松懈，因为它忽略了所有不构成4的倍数的尾随字节)

其中f是文件周围的BufReader。