space

一个提供空间数据结构和搜索抽象的库

如果您使用了一个 kNN 数据结构库，并且希望在其类型上原生实现 Knn 特性，请在该库上提出一个问题。同样，定义具有特定距离度量的数据点而不是通用线性代数 crate 的 crate 可以实现 MetricPoint 特性。

请参阅 bitarray crate 以获取使用汉明距离（带有可选的、不稳定的多达 512 位 SIMD 支持，以及始终开启的 64 位 popcnt 指令支持）实现 MetricPoint 的示例。

用法

use space::Metric;

struct Hamming;

impl Metric<u8> for Hamming {
    type Unit = u8;

    fn distance(&self, &a: &u8, &b: &u8) -> Self::Unit {
        (a ^ b).count_ones() as u8
    }
}

use space::{Knn, KnnFromBatch, LinearKnn, Metric, Neighbor};

#[derive(Default)]
struct Hamming;

impl Metric<u8> for Hamming {
    type Unit = u8;

    fn distance(&self, &a: &u8, &b: &u8) -> Self::Unit {
        (a ^ b).count_ones() as u8
    }
}

let data = vec![
    (0b1010_1010, 12),
    (0b1111_1111, 13),
    (0b0000_0000, 14),
    (0b1111_0000, 16),
    (0b0000_1111, 10),
];

let search: LinearKnn<Hamming, _> = KnnFromBatch::from_batch(data.iter());

assert_eq!(
    &search.knn(&0b0101_0000, 3),
    &[
        (
            Neighbor {
                index: 2,
                distance: 2
            },
            &data[2].0,
            &data[2].1
        ),
        (
            Neighbor {
                index: 3,
                distance: 2
            },
            &data[3].0,
            &data[3].1
        ),
        (
            Neighbor {
                index: 0,
                distance: 6
            },
            &data[0].0,
            &data[0].1
        )
    ]
);

基准测试

要运行基准测试，请使用以下命令

cargo bench --all-features

如果您不传递 --all-features，则不会运行基准测试。由于 这个问题，SIMD 功能必须启用。Cargo 没有提供自动将 SIMD 功能应用于基准测试的方法，因此必须在命令行中传递。