streaming_algorithms

📖 文档 | 💬 聊天

各种 流算法 的 SIMD 加速实现。

这个库仍在开发中。非常欢迎提交 PR！目前实现的算法包括

• Count–min 草图
• Top k（Count–min 草图加上双链表哈希表以跟踪重击者/按聚合值排序的 Top k 键）
• HyperLogLog
• 采样器

该库的目标是使这些算法可组合；例如 Top k + HyperLogLog 可以实现类似以下 SQL 查询的近似版本：SELECT key FROM table GROUP BY key ORDER BY COUNT(DISTINCT value) DESC LIMIT k。

使用 RUSTFLAGS="-C target-cpu=native" 和 nightly 功能运行您的应用程序，以利用 SIMD 加速，如下所示

RUSTFLAGS="-C target-cpu=native" cargo run --features "streaming_algorithms/nightly" --release

请参阅 此 gist 以获取待实现的其他算法的良好列表。其他资源包括 概率数据结构 – 维基百科、DataSketches – 来自雅虎的类似 Java 库 和 Algebird – 来自 Twitter 的类似 Java 库。

由于这些实现通常位于热代码路径中，因此使用了 unsafe，尽管只有在以下情况下才需要：a) 实现渐近最优算法或 b) 缓解观察到的瓶颈。

许可协议

根据以下任一项许可

• Apache 许可协议第 2 版，(LICENSE-APACHE.txt 或 http://www.apache.org/licenses/LICENSE-2.0)
• 麻省理工学院许可证（LICENSE-MIT.txt 或 http://opensource.org/licenses/MIT）

任选。

除非您明确声明，否则根据 Apache-2.0 许可证定义的，您提交的任何有意包含在作品中的贡献，应按照上述方式双重许可，没有任何附加条款或条件。