How get closest value in Btreemap?

help
1

Is any crate or Btreemap exposed interface could search closest key's corresponding value more effectively?

O(n) version, I think the tree data structure could do this more effectively,Is that so?

extern crate rand;
extern crate time;

use std::collections::BTreeMap;
use rand::{Rng, Rand};
use time::PreciseTime;

type ID = [u8; 20];

trait Close<K, V> {
    fn get_closest(&self, key :K) -> Option<&V>;
}

impl <V> Close<ID, V> for  BTreeMap<ID, V> {
    fn get_closest(&self, key:ID) -> Option<&V> {
        if self.is_empty() { return None };
        if self.contains_key(&key) {return self.get(&key) };

        let keys = self.keys();
        let mut last_key: Option<&ID> = None;

        for i in keys {
            if i > &key {
                match last_key {
                    Some(k) => if closer(&key, i, k) {
                        return self.get(i)
                    } else {
                        return self.get(k)
                    },
                    None => return self.get(i),
                }
            }
            else {
                last_key = Some(i)
            }
        }

        return self.get(last_key.unwrap());

        fn closer(orig: &ID, id1: &ID, id2: &ID) -> bool {
            for (d1, d2) in  orig.iter().zip(id1.iter()).map(|(x, y)| y - x)
                .zip(orig.iter().zip(id2.iter()).map(|(x, y)| y -x)) {
                    if d1 < d2 {
                        return true
                    } else if d1 > d2 {
                        return false
                    }
                }
            return false
        }
        
    }
}


fn main() {
    fn gen_id() -> ID {
        let mut rng= rand::thread_rng();
        ID::rand(&mut rng)
    }
    let mut bt = BTreeMap::new();

    for i in 0..10000000 {
        bt.insert(gen_id(), "hello".to_string());
    }


    for i in 0..100 {
        let id = gen_id();
        let mut cid = id;
        cid[19] += 1;

        bt.insert(id, "world".to_string());
        let start = PreciseTime::now();
        assert_eq!(bt.get_closest(cid).unwrap().trim(), "world");
        let end = PreciseTime::now();
        println!("{}", start.to(end));
    }
}
2

I think you can use currently unstable range method to do so.

If you are looking for the closest element to key, you can lookup up two ranges, [key, Unbound] and [Unbound, key] and take their respective first and last elements as the two candidates for being closest to the key. This should run in O(log n).

3

@matklad thank your reply， as the doc describe the rang should the correct way.
but I run into some trouble when try implement this feature，
Could someone give my some advice?
like this:
```error[E0283]: type annotations required: cannot resolve _: std::cmp::Ord
--> main.rs:26:27
|
26 | let mut r1 = self.range(Unbounded, Included(key));
| ^^^^^

#![feature(collections_bound)]
#![feature(collections)]
#![feature(btree_range)]

extern crate rand;
extern crate time;

use std::collections::BTreeMap;
use std::collections::Bound::{Included, Excluded, Unbounded};
use std::collections::btree_map::Range;
use rand::{Rng, Rand};
use time::PreciseTime;

type ID = [u8; 20];

trait Close {
fn get_closest(&self, key :&ID) -> Option<&V>;
}

impl Close for BTreeMap<ID, V> {
fn get_closest(&self, key: &ID) -> Option<&V> {
if self.is_empty() { return None };
if self.contains_key(key) {return self.get(key) };

    // let mut r1: Range<ID, V> = BTreeMap::range(self, Unbounded, Included(key));
    // let mut r2: Range<ID, V> = BTreeMap::range(self, Excluded(key), Unbounded);

    let mut r1 = self.range(Unbounded, Included(key));
    let mut r2 = self.range(Excluded(key), Unbounded);
    
    let (fkey, fval): (&ID, &V) = r1.last().unwrap();
    let (bkey, bval): (&ID, &V) = r2.next().unwrap();

    if closer(key, bkey, fkey)  {
        return Some(bval)
    } else {
        return Some(fval)
    }        

    fn closer(orig: &ID, id1: &ID, id2: &ID) -> bool {
        for (d1, d2) in  orig.iter().zip(id1.iter()).map(|(x, y)| y - x)
            .zip(orig.iter().zip(id2.iter()).map(|(x, y)| y -x)) {
                if d1 < d2 {
                    return true
                } else if d1 > d2 {
                    return false
                }
            }
        return false
    }

}

}

fn main() {
fn gen_id() -> ID {
let mut rng= rand::thread_rng();
ID::rand(&mut rng)
}
let mut bt = BTreeMap::new();

for i in 0..10000000 {
    bt.insert(gen_id(), "hello".to_string());
}

for i in 0..100 {
    let id = gen_id();
    let mut cid = id;
    cid[19] += 1;

    bt.insert(id, "world".to_string());
    let start = PreciseTime::now();
    assert_eq!(bt.get_closest(&cid).unwrap().trim(), "world");
    let end = PreciseTime::now();
    println!("{}", start.to(end));
}

}

4

this should be a rust bug，and have a workaround way see https://github.com/rust-lang/rust/issues/35738.

and use range very fast.

1 Like