ordsearch

这个包提供了一种在有序集合中进行近似查找的数据结构。

更具体地说，给定一个包含 A 的 n 个值的集合，以及一个查询值 x，这个库提供了一个高效机制来查找 A 中大于或等于 x 的最小值。特别是，这个库适用于存在许多对同一个数组 A 进行此类查询的重要情况。

这个库基于 Paul-Virak Khuong 和 Pat Morin 在 Array Layouts for Comparison-Based Searching 中确定的最佳解决方案构建。更多信息，请参阅论文，他们的网站，以及C++实现仓库。

当前实现

撰写本文时，此实现使用了一个分支无关的搜索，基于Eytzinger-arranged数组，并基于C++实现，该实现由上述论文的作者编写。这是论文中推荐的算法，也是作者在https://github.com/patmorin/arraylayout/issues/3#issuecomment-338472755中建议的。

请注意，由于https://github.com/aweinstock314/prefetch/issues/1，预取仅在（非默认）nightly功能中启用。欢迎提出解决方案建议。

性能

可以使用以下命令运行包含的基准测试

$ cargo +nightly bench --features nightly

这将针对不同数量的值和不同大小的值进行构建和搜索基准测试 - 寻找与您的数据最接近的行。总体趋势是，只要您使用target-cpu=native 和lto=thin进行编译，ordsearch在 n 较小且 T 较大时速度更快。性能提升似乎在英特尔处理器上最佳，并且由于SliceExt::binary_search性能的相对较近的改进，提升较小。

以下是在英特尔(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz CPU上运行的结果摘要

$ rustc +nightly --version
rustc 1.75.0-nightly (e0d7ed1f4 2023-10-01)
$ env CARGO_INCREMENTAL=0 RUSTFLAGS='-C target-cpu=native' cargo +nightly bench --features nightly

未来工作

• 实现对齐操作: https://github.com/patmorin/arraylayout/blob/3f20174a2a0ab52c6f37f2ea87d087307f19b5ee/src/eytzinger_array.h#L204
• 实现大 T 的深度预取: https://github.com/patmorin/arraylayout/blob/3f20174a2a0ab52c6f37f2ea87d087307f19b5ee/src/eytzinger_array.h#L128