Rust 语言的小波矩阵

它在常数时间内提供了对非常大的无符号整数序列的各种分析。

使用方法

在Cargo.toml中添加后，将此行添加到lib.rs或main.rs中。

extern crate wavelet_matrix;

查看crate文档顶部以获取更多示例。

• https://docs.rs/wavelet-matrix/

基准测试

• 总体性能

  • https://github.com/sekineh/wavelet-matrix-rs/blob/master/BENCH.md
  • 在 Intel Xeon 2800 MHz 上执行基准测试

• O(1) SUM 的错误评估

  • https://github.com/sekineh/wavelet-matrix-rs/blob/master/BENCH_SUM.md

功能

给定一个无符号整数序列 T，它提供以下查询。

基本操作

• .len():
  • 返回 T 的长度。
  • 几乎没有开销，只是返回存储的值。
• .lookup(pos):
  • 返回 T 位置处的值，T[pos]。
  • 比数组查找慢，但仍然是 O(1)。您可能想保存原始 Vector 以加快查找速度。

计数

计数在 O(1) 内完成。

• .count(start..end,value):
  • 返回满足 e == value 且包含在 T[start..end] 的元素 e 的数量
• .count_prefix(start..end,value,ignore_bit):
  • 返回满足 e >> ignore_bit == value >> ignore_bit 且包含在 T[start..end] 的元素 e 的数量
  • 这可以用来统计满足诸如 192.168.10.0/24 这样的 IPv4 前缀的 IPv4 地址的数量。在这种情况下，ignore_bit 将是 8。
• .count_lt(start..end,value):
  • 返回满足条件 e < value 的元素 e 的数量，该条件包含在 T[start..end] 中。
• .count_gt(start..end,value):
  • 返回满足条件 e > value 的元素 e 的数量，该条件包含在 T[start..end] 中。
• .count_range(start..end,val_start..val_end):
  • 返回满足条件 val_start <= e < val_end 的元素 e 的数量，该条件包含在 T[start..end] 中。

搜索

每次搜索的索引的时间复杂度为 O(1)。

• .search(start..end,value):
  • 返回一个迭代器，该迭代器找到满足条件 e == value 的元素 e 的索引，该条件包含在 T[start..end] 中。
• .search_prefix(start..end,value,ignore_bit):
  • 返回一个迭代器，该迭代器找到满足条件 e >> ignore_bit == value >> ignore_bit 的元素 e 的索引，该条件包含在 T[start..end] 中。
• [待办] 实现除等于之外的各种条件。

排名

与元素数量 n 相关的排名操作大致为 O(1)。

• .max_k(start..end,val_start..val_end,k):
  • 按降序列出 (value, count) 对。
  • 值被限制在范围 val_start..val_end 内。
• .min_k(start..end,val_start..val_end,k):
  • 按升序列出 (value, count) 对。
  • 值被限制在范围 val_start..val_end 内。

.top_k() 在最佳情况下也以 O(1) 的速度执行，但在最坏情况下（每个值只出现一次）可能需要 O(n)！

• .top_k(start..end,val_start..val_end,k):
  • 按最频繁出现顺序列出 (value, count) 对。
  • 值被限制在范围 val_start..val_end 内。
  • [待办] 明确相同计数的顺序。

为了在不考虑唯一值数量的情况下实现 O(1) 性能，请使用 .top_k_ranges()

• [实验性] .top_k_ranges(start..end, val_start..val_end, k)
  • 按最频繁出现顺序列出 (v_start..v_end, count) 对。
  • 与 .top_k() 不同，.top_k_ranges() 返回包含所有值的完整范围集。
  • 值被限制在范围 val_start..val_end 内。
  • [待办] 明确相同计数的顺序。