h3o-ice — 对于H3单元索引的冻结（即只读）集合和映射

这些数据结构基于有限状态转换器构建，允许它们非常紧凑同时提供快速的查找。

这特别适用于只读索引（无论是内存中还是磁盘上）。

安装

Cargo

• 按照此指南安装rust工具链，以便安装cargo。
• 运行 cargo install h3o-ice

使用

use h3o::{LatLng, Resolution};
use h3o_ice::FrozenSet;

let coord = LatLng::new(48.872280706 2.332697839).expect("valid coord");
let set = FrozenSet::try_from_iter(
    coord.to_cell(Resolution::Nine)
        .children(Resolution::Ten)
)
.expect("failed to create set");

set.contains(CellIndex::try_from(0x8a1fb4666417fff).expect("valid cell"));

与其他数据结构的比较

关于查找时间

• 输入数据集是法国覆盖范围，分辨率为10
  • 原始数据集：44,250,550个单元（333.60M）。
  • 压缩后（即用祖先单元替换单元簇）：127,264个单元（0.97M）
• 查找分辨率为10的单元
  • 在原始数据集中的单个查找。
  • 在压缩数据集中的前缀查找（如果不支持，则为重复查找）。

您可以运行提供的基准测试以获取与您的机器相关的度量。

总之

• 如果您可以承受内存使用量并且不关心顺序（例如范围查询），请选择HashSet以获得最大速度。
• 如果您需要排序但不需要处理压缩集合，请选择BTreeSet。
• 如果您有一个大型的只读数据集，希望优化内存使用并能够直接查询压缩数据，那么FrozenSet将是您的朋友。

Frozen{Map,Set} 并不是通用数据结构。它们附带许多额外约束（只读，必须从预先排序的输入构建，...），但在特定领域表现出色，并提供许多优点（例如，键压缩，可映射到内存映射文件，前缀查找，...）。

许可证

BSD 3 条款

[^1]: Frozen{Set,Map} 压缩键的公共前缀和后缀，结果比输入数据集更小（例如，333MB 测试数据集可以放入 176KB 的 FrozenSet） [^2]: Rust 中 HashMap 的开销度量