Двоичный поиск вектора в кусках - PullRequest
Новая
       4

Двоичный поиск вектора в кусках

0 голосов
/ 24 февраля 2020

У меня есть файл адресов ipv4, который, как мы знаем, составляет 4 байта каждый. Я sh сделать бинарный поиск по содержимому файла, чтобы найти данный 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)
    }
}

Ответы [ 2 ]

1 голос
/ 24 февраля 2020

Было бы лучше иметь срез с одним элементом на адрес, либо 4-байтовыми массивами ([u8; 4]), некоторой эквивалентной структурой (эй, Ipv4Addr), либо просто u32. К сожалению, я не думаю, что возможно переосмыслить &[u8] с длиной, кратной 4, как &[[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);
}

(детская площадка)

Тогда чтение из файла будет выглядеть примерно так: 

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 вокруг файла.

0 голосов
/ 24 февраля 2020

Я думаю, что у меня сейчас есть рабочее решение, но я не мастер ржавчины, поэтому, пожалуйста, критикуйте его резко.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=6e3102ea622f1ae0d66465f4007ccb03


use std::cmp::Ordering::{self, Equal, Greater, Less};
use std::net::{IpAddr, Ipv4Addr, Ipv6Addr};
use std::str::FromStr;

fn binary_search(s: Vec<u8>, x: Vec<u8>) -> Result<usize, usize> {
    let f = |p: &[u8]| p.cmp(&x);

    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;

        // mid is always in [0, size), that means mid is >= 0 and < size.
        // mid >= 0: by definition
        // mid < size: mid = size / 2 + size / 4 + size / 8 ...

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

        base = if cmp == Greater { base } else { mid };
        size -= half;
    }
    // base is always in [0, size) because base <= mid.
    let cmp = f(s[base*4..(base+1)*4].to_vec());


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

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

    let found = binary_search(vec, Ipv4Addr::from_str("20.0.0.0").unwrap().octets().to_vec());

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