🧮 HyperLogLog-rs

这是一个提供HyperLogLog (HLL) 算法实现的Rust库，力求节省内存。

此实现已提供几乎来自HyperLogLog++的所有好处。我们不打算集成稀疏寄存器功能，因为此库的使用案例集中在需要相对较小数量的寄存器和密集集合的情况下。除此之外，HLL++论文中提供的所有其他观察结果都已实现。

什么是HyperLogLog？

HLL是一种概率算法，用于在非常小的内存量下以非常高的精度估计集合的基数。该算法由Philippe Flajolet和Éric Fusy于2007年发明，自那时起，它在许多领域得到了广泛应用，包括数据库系统、搜索引擎和社会网络。

HLL算法基于观察，即集合中唯一元素的数量可以通过计算集合中元素的哈希值二进制表示中的前导零的数量来估计。这个想法简单但强大，它允许我们使用只有几KB的小量内存来估计集合的基数，其精度非常高（误差在几个百分点以内）。

我们的Rust实现HLL算法效率极高，并能提供大型集合基数的非常准确的估计。它设计得易于使用，并易于集成到现有的Rust项目中。该包提供了一个简单的API，允许您创建HLL计数器、向其中添加元素并估计其基数。

本实现中HyperLogLog算法的重点是尽可能提高内存效率。我们通过避免存储参数（如精度或位数）的结构属性来实现这一点，因为这些属性会占用不必要的内存空间。相反，我们将这些参数定义为与类相关联的常量，这允许我们实现更高效且紧凑的代码。

然而，这种方法需要使用Rust语言的几个夜间特性，包括const泛型和关联类型构造函数。通过使用这些特性，我们能够在编译时根据HyperLogLog计数器的精度定义算法使用的内部数据结构的大小。这导致了一个更节省内存的实现，可以在各种应用中使用。

我们希望这个库对您的项目有所帮助，我们欢迎您的反馈和贡献。如果您有任何问题或建议，请随时提出问题或提交pull request。感谢您对我们HLL crate的兴趣，祝您计数愉快！

使用方法

将以下内容添加到您的Cargo.toml

[dependencies]
hyperloglog = "0.1"

并将以下内容添加到您的crate根目录

use hyperloglog_rs::prelude::*;

示例

use hyperloglog_rs::prelude::*;

let mut hll = HyperLogLog::<14, 5>::new();
hll.insert(&1);
hll.insert(&2);

let mut hll2 = HyperLogLog::<14, 5>::new();
hll2.insert(&2);
hll2.insert(&3);

let union = hll | hll2;

let estimated_cardinality = union.estimate_cardinality();
assert!(estimated_cardinality >= 3.0_f32 * 0.9 &&
        estimated_cardinality <= 3.0_f32 * 1.1);

无STD

这个crate设计得尽可能轻量，不需要从Rust标准库(std)中依赖任何内容。因此，它可以在标准库不可用的裸机或嵌入式环境中使用。

这个crate的所有功能都可以在不使用std的情况下使用，并提供了易于访问所有相关类型和特征的prelude模块。如果您在使用这个crate的no_std环境中遇到任何问题，请随时在GitHub上提出问题或提交pull request。

所需功能

请注意，这个crate使用的一些功能（如#![feature(const_float_bits_conv)]）需要夜间Rust编译器。如果您使用的是稳定或beta版本的Rust，您可能需要切换到夜间版本或禁用某些功能来使用这个crate。

const_float_bits_conv功能能够在编译时将浮点值转换为对应的位模式，这在计算哈希值时非常有用。

最后，const_fn_floating_point_arithmetic功能能够在const函数中执行浮点运算，这对于使用f32::to_bits()方法计算哈希值是必要的。

模糊测试

模糊测试是一种通过向代码提供随机输入来发现软件中的安全漏洞和错误的技术。它可以是一种发现其他测试方法可能无法发现的问题的有效方式。在我们的库中，我们非常重视模糊测试，并使用cargo fuzz工具来确保我们的代码健壮和安全。cargo fuzz自动化生成和运行随机测试输入的过程，并有助于识别传统测试方法难以检测的难以捉摸的bug。我们确保我们的模糊目标持续更新，并针对库的最新版本运行，以确保任何漏洞或错误都能迅速识别和解决。

在这里了解更多关于我们如何进行模糊测试的信息

为此项目做出贡献

社区贡献非常受欢迎，并且可以帮助改进这个项目。如果您有任何建议、功能请求或要报告的bug，请在GitHub上打开一个问题。另外，如果您想为项目做出贡献，您可以打开一个包含您建议更改的pull request。在进行任何重大更改之前，请与项目维护者在问题跟踪器或🍇GRAPE🍇 Discord服务器上进行讨论。

如果您喜欢这个项目并希望支持其开发，您可以在GitHub上为其仓库加星，或者考虑进行财务捐赠。项目维护者已设置GitHub赞助页面，您可以通过该页面进行定期财务捐赠以支持项目开发。无论金额大小，任何财务捐赠都将受到高度赞赏，并有助于确保该项目的持续开发和维护。

感谢

我们想感谢GitHub用户Tabac对其HyperLogLog实现的贡献，这对学习和基准测试此实现非常有用。他们的实现可以在这里找到。

引用

一些相关引用以了解更多信息

• Flajolet, Philippe，Éric Fusy，Olivier Gandouet，和Frédéric Meunier. "HyperLogLog：近最优基数估计算法的分析。" 在2007年算法分析会议论文集，第127-146页。2007。