fid-rs

高性能FID（完全可索引字典）库。

主API文档 | 发布API文档 | 基准测试结果 | 变更日志

快速入门

要使用fid-rs，请将以下内容添加到您的 Cargo.toml 文件中

[dependencies]
fid-rs = "0.1"  # NOTE: Replace to latest minor version.

使用概述

use fid_rs::Fid;

let fid = Fid::from("0100_1");  // Tips: Fid::from::<&str>() ignores '_'.

// Basic operations ---------------------
assert_eq!(fid[0], false);  // [0]1001; 0th bit is '0' (false)
assert_eq!(fid[1], true);   // 0[1]001; 1st bit is '1' (true)
assert_eq!(fid[4], true);   // 0100[1]; 4th bit is '1' (true)

assert_eq!(fid.rank(0), 0);  // [0]1001; Range [0, 0] has no '1'
assert_eq!(fid.rank(3), 1);  // [0100]1; Range [0, 3] has 1 '1'
assert_eq!(fid.rank(4), 2);  // [01001]; Range [0, 4] has 2 '1's

assert_eq!(fid.select(0), Some(0)); // []01001; Minimum i where range [0, i] has 0 '1's is i=0
assert_eq!(fid.select(1), Some(1)); // 0[1]001; Minimum i where range [0, i] has 1 '1's is i=1
assert_eq!(fid.select(2), Some(4)); // 0100[1]; Minimum i where range [0, i] has 2 '1's is i=4
assert_eq!(fid.select(3), None);    // There is no i where range [0, i] has 3 '1's

// rank0, select0 -----------------------
assert_eq!(fid.rank0(0), 1);  // [0]1001; Range [0, 0] has no '0'
assert_eq!(fid.rank0(3), 3);  // [0100]1; Range [0, 3] has 3 '0's
assert_eq!(fid.rank0(4), 3);  // [01001]; Range [0, 4] has 3 '0's

assert_eq!(fid.select0(0), Some(0)); // []01001; Minimum i where range [0, i] has 0 '0's is i=0
assert_eq!(fid.select0(1), Some(0)); // [0]1001; Minimum i where range [0, i] has 1 '0's is i=0
assert_eq!(fid.select0(2), Some(2)); // 01[0]01; Minimum i where range [0, i] has 2 '0's is i=2
assert_eq!(fid.select0(4), None);    // There is no i where range [0, i] has 4 '0's

构造函数

use fid_rs::Fid;

// Most human-friendly way: Fid::from::<&str>()
let fid = Fid::from("0100_1");

// Complex construction in simple way: Fid::from::<&[bool]>()
let mut arr = [false; 5];
arr[1] = true;
arr[4] = true;
let fid = Fid::from(&arr[..]);

迭代器

use fid_rs::Fid;

let fid = Fid::from("0100_1");

for bit in fid.iter() {
    println!("{}", bit);
}
// =>
// false
// true
// false
// false
// true

实用方法

use fid_rs::Fid;

let fid = Fid::from("0100_1");

assert_eq!(fid.len(), 5);

特性

• 支持任意长度，最小工作内存：fid-rs提供几乎任意大小的FID。它被精心设计，以尽可能使用最小的内存空间。
• FID并行构建：构建操作（Fid::from()）需要 O(N) 时间。它是并行化的，并实现了接近最优的扩展。
• 构建操作过程中/后不进行内存复制：在内部创建位向量表示后，任何操作都不会进行内存复制。
• 始终可以访问最新的基准测试结果：fid-rs在Travis CI中使用Criterion.rs进行持续基准测试。图形基准测试结果发布在此。

复杂度

当Fid的长度为N时

（实际上，select()的时间复杂度可以通过复杂实现达到 O(1)，但fid-rs像许多其他库一样，使用rank()的结果的二分搜索。）

版本

fid-rs使用语义版本控制。

当前主版本为0，次要版本更新可能涉及破坏公共API的改变（尽管会尽量避免）。

Rust版本支持

fid-rs在Travis CI中使用以下Rust版本进行持续测试

• 1.33.0
• 最新稳定版本
• beta版本
• 夜间构建

因此，它应该与Rust 1.33.0及其任何更高版本兼容。

较旧版本也可能工作，但没有经过测试或保证。

贡献

任何类型的pull请求都受到欢迎。

指南

• README.md由$ cargo readme命令生成。请不要手动更新README.md，而是编辑src/lib.rs，然后执行$ cargo readme > README.md。
• Travis CI会自动执行以下提交和推送到您的pull-requests
  • $ cargo readme > README.md
  • $cargo fmt --all

许可证

MIT或Apache-2.0