如何有效地将任意函数应用于 BTreeMap 中的移动 window

Question

如何有效地将函数应用于 BTreeMap 的移动 window，其中 window 由键的范围决定？

我当前的代码是这样的，但是当 BTreeMap 变得非常大时（并且可能随着 radius 的增加），它会非常慢。我怀疑这是因为 clone() 但我想不出替代解决方案。我如何有效地做到这一点？

use nalgebra::Vector3;
use std::collections::BTreeMap;

fn get_window(data: &BTreeMap<i64, Vector3<f64>>, center: &i64, radius: &i64) -> BTreeMap<i64, Vector3<f64>> {
    let mut window = data.clone();
    window.retain(|&ts, _| ts >= (center - radius) && ts <= (center + radius));
    window
}

fn kernel(data: BTreeMap<i64, Vector3<f64>>) -> Vector3<f64> {
    // This is just an example function
    let n = data.len() as f64;
    let x = data.iter().map(|(_, vec)| vec[0]).sum::<f64>() / n;
    let y = data.iter().map(|(_, vec)| vec[1]).sum::<f64>() / n;
    let z = data.iter().map(|(_, vec)| vec[2]).sum::<f64>() / n;
    Vector3::new(x, y, z)
}

fn main() {
    let mut btreemap = BTreeMap::<i64, Vector3<f64>>::new();
    btreemap.insert(0, Vector3::new(0.0, 0.0, 0.0));
    btreemap.insert(1, Vector3::new(1.0, 0.0, 0.0));
    btreemap.insert(2, Vector3::new(0.0, 1.0, 0.0));
    btreemap.insert(3, Vector3::new(0.0, 0.0, 1.0));
    btreemap.insert(4, Vector3::new(2.0, 0.0, 0.0));
    btreemap.insert(5, Vector3::new(0.0, 2.0, 0.0));
    btreemap.insert(6, Vector3::new(0.0, 0.0, 2.0));
    
    let mut smoothed = BTreeMap::<i64, Vector3<f64>>::new();
    for (ts, _vec) in btreemap.iter() {
        let window = get_window(&btreemap, &ts, &1);
        let kernel = kernel(window);
        smoothed.insert(*ts, kernel);
    }

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

Answer 1

您可以使用 BTreeMap::range to get an iterator over the items within a range of the map. This is cheap because a btree_map::Range 迭代源地图中的数据，而不是克隆地图然后过滤 window 中的项目；它不会克隆任何内容。

我还建议将中心和半径作为 i64 而不是 &i64 传递。不用借了。

use std::collections::BTreeMap;
use std::collections::btree_map;

fn get_window(data: &BTreeMap<i64, Vector3<f64>>, center: i64, radius: i64) -> btree_map::Range<'_, i64, Vector3<f64>> {
    data.range(center-radius..=center+radius)
}

fn kernel(data: btree_map::Range<'_, i64, Vector3<f64>>) -> Vector3<f64> {
    // This is just an example function
    let n = data.clone().count() as f64;
    let x = data.clone().map(|(_, vec)| vec[0]).sum::<f64>() / n;
    let y = data.clone().map(|(_, vec)| vec[1]).sum::<f64>() / n;
    let z = data.clone().map(|(_, vec)| vec[2]).sum::<f64>() / n;
    Vector3::new(x, y, z)
}

main 中的循环变为：

for (&ts, _vec) in btreemap.iter() {
    let window = get_window(&btreemap, ts, 1);
    let kernel = kernel(window);
    smoothed.insert(ts, kernel);
}

Playground

如何有效地将任意函数应用于 BTreeMap 中的移动 window

How to efficiently apply an arbitrary function on a moving window in a BTreeMap

dictionary

b-tree

rust