rust-lapper

文档 Crates.io

这是 Brent Pendersen 的 nim-lapper 的 Rust 版本。它有几个显著的不同之处，主要是查找和搜索方法都返回迭代器，因此所有适配器方法都可以正常使用。

此包适用于大多数不包含非常长的区间（这些区间会吞并大多数其他区间）的区间数据。与其他方法相比，它仍然相当可比较。如果您在极坏的情况下绝对需要时间保证，请参阅 COItres 和 IITree。

然而，在更典型的数据集上，此包比其他区间重叠方法快 4-10 倍。

还应注意的是，count 方法对数据类型不可知，并且应该在任何数据集上尽可能快。它是 BITS 算法 的实现。

Serde 支持

rust-lapper 支持使用 serde 对 Lapper 和 Interval 对象进行序列化

[dependencies]
rust-lapper = { version = "*", features = ["with_serde"] }

有关简要示例，请参阅 examples/serde.rs。

基准测试

基准测试区间树类数据结构很困难。请参阅 interval_bakeoff 项目以获取基准测试的详细信息... 但它还没有完全准备好，运行起来也很困难。

运行命令

./target/release/interval_bakeoff fake -a -l RustLapper -l
RustBio -l NestedInterval -n50000 -u100000

# This equates to the following params:
# num_intervals	50000
# universe_size	100000
# min_interval_size	500
# max_interval_size	80000
# add_large_span	true (universe spanning)

A / b 创建时间设置

100% 击中率 (A 对 A)

低于100% 击中率 (A 对 B)

嵌套区间 rust-bio 注意，rust-bio 有一个新的区间树结构，应该比这里展示的更快

示例

use rust_lapper::{Interval, Lapper};

type Iv = Interval<usize, u32>;
fn main() {
    // create some fake data
    let data: Vec<Iv> = vec![
        Iv {
            start: 70,
            stop: 120,
            val: 0,
        }, // max_len = 50
        Iv {
            start: 10,
            stop: 15,
            val: 0,
        },
        Iv {
            start: 10,
            stop: 15,
            val: 0,
        }, // exact overlap
        Iv {
            start: 12,
            stop: 15,
            val: 0,
        }, // inner overlap
        Iv {
            start: 14,
            stop: 16,
            val: 0,
        }, // overlap end
        Iv {
            start: 40,
            stop: 45,
            val: 0,
        },
        Iv {
            start: 50,
            stop: 55,
            val: 0,
        },
        Iv {
            start: 60,
            stop: 65,
            val: 0,
        },
        Iv {
            start: 68,
            stop: 71,
            val: 0,
        }, // overlap start
        Iv {
            start: 70,
            stop: 75,
            val: 0,
        },
    ];

    // make lapper structure
    let mut lapper = Lapper::new(data);

    // Iterator based find to extract all intervals that overlap 6..7
    // If your queries are coming in start sorted order, use the seek method to retain a cursor for
    // a big speedup.
    assert_eq!(
        lapper.find(11, 15).collect::<Vec<&Iv>>(),
        vec![
            &Iv {
                start: 10,
                stop: 15,
                val: 0
            },
            &Iv {
                start: 10,
                stop: 15,
                val: 0
            }, // exact overlap
            &Iv {
                start: 12,
                stop: 15,
                val: 0
            }, // inner overlap
            &Iv {
                start: 14,
                stop: 16,
                val: 0
            }, // overlap end
        ]
    );

    // Merge overlaping regions within the lapper to simplifiy and speed up quries that only depend
    // on 'any
    lapper.merge_overlaps();
    assert_eq!(
        lapper.find(11, 15).collect::<Vec<&Iv>>(),
        vec![&Iv {
            start: 10,
            stop: 16,
            val: 0
        },]
    );

    // Get the number of positions covered by the lapper tree:
    assert_eq!(lapper.cov(), 73);

    // Get the union and intersect of two different lapper trees
    let data = vec![
        Iv {
            start: 5,
            stop: 15,
            val: 0,
        },
        Iv {
            start: 48,
            stop: 80,
            val: 0,
        },
    ];
    let (union, intersect) = lapper.union_and_intersect(&Lapper::new(data));
    assert_eq!(union, 88);
    assert_eq!(intersect, 27);

    // Get the depth at each position covered by the lapper
    for interval in lapper.depth().filter(|x| x.val > 2) {
        println!(
            "Depth at {} - {}: {}",
            interval.start, interval.stop, interval.val
        );
    }

}

发布说明

• 1.1.0：感谢 @zaporter 添加了插入功能
• 0.4.0：添加了 BITS 计数算法
• 0.4.2：修复在合并重叠时更新起始/结束向量的错误
• 0.4.3：删除多余的打印语句
• 0.5.0：使区间起始/结束泛型化
• 1.0.0：通过 with_serde 功能标志添加 serde 支持