我在哪里可以找到有效的LogLog 算法实现？我尝试自己实现它，但我的实现草案产生了奇怪的结果。

这是：

由于未知原因实现对参数非常敏感max_error，它是决定结果大小的主要因素。我敢肯定，有一些愚蠢的错误:)

更新：这个问题在较新版本的算法中得到解决。我稍后会发布它的实现。

我最近在业余时间学习了不同的算法，我遇到的一个看起来很有趣的算法叫做 HyperLogLog 算法——它估计一个列表中有多少个独特的项目。

这对我来说特别有趣，因为当我看到“基数”值（直到最近我一直认为它是计算而不是估计的）时，它让我回到了我的 MySQL 时代。

所以我知道如何在O ( n ) 中编写一个算法来计算数组中有多少唯一项。我用 JavaScript 写了这个：

但问题是我的算法虽然O ( n ) 使用了大量内存（将值存储在 中Table）。

我一直在阅读这篇论文，了解如何在O ( n ) 时间内计算列表中的重复项并使用最少的内存。

它解释说，通过散列和计数位或可以在一定概率内（假设列表均匀分布）估计列表中唯一项目的数量。

我已经阅读了论文，但我似乎无法理解它。谁能给一个更外行的解释？我知道哈希是什么，但我不明白它们是如何在这个 HyperLogLog 算法中使用的。

Flajolet 等人的HyperLogLog 算法描述了一种仅使用少量内存来估计集合基数的巧妙方法。但是，它确实在计算中考虑了原始集合的所有 N 个元素。如果我们只能访问原始 N 的一小部分随机样本（例如 10%）怎么办？有没有研究过 HyperLogLog 或类似算法如何适应这种情况？

我知道这本质上是描述为不同价值估计的问题，对此存在大量研究（例如，请参阅本文以获取概述）。然而，据我所知，对不同价值估计的研究使用了许多与 HyperLogLog 使用的方法非常不同的临时估计器。因此，我想知道是否有人已经考虑过将 HyperLogLog 用于不同的值估计问题。

我有一系列事件流经系统（例如披萨订购系统），我想计算每个事件的某些属性随着时间的推移。例如，我可能想查看过去 5 分钟内有多少独特的人点了意大利辣香肠比萨，或者 John Doe 在过去一周点了多少比萨。

这是很多事件，所以我们使用 Cassandra 或 HBase 之类的东西，因为即使是计数也不能存储在内存中。此外，由于我们需要跟踪集合成员资格（例如，为了计算订购特定类型披萨的独特人），它变得更大。

我们可以存储一个订单列表，然后查询计数，但这很慢。而且我们大多不在乎谁点了意大利辣香肠比萨，只在乎有多少独特的订单，以及在给定的时间窗口内。

存储此信息的最佳方式是什么，例如在 Cassandra 中，以便可以在某些时间间隔内检索信息？

我一开始尝试使用 Redis + 布隆过滤器，但是存储布隆过滤器位向量需要事务以避免竞争条件，所以我使用了 redis 集。

然后我意识到整个事情太大了，不能只在内存中，所以我决定切换到磁盘支持的存储。但是，没有像 redis 那样的原生集合。

我查看了像 HyperLogLog 这样的草图/流式算法，但结论是，为了保存 hyperloglog 对象，我需要存储位数组（或腌制对象或其他任何东西）......这是洁净的吗，最好的做法是什么，如果这确实是解决方案？

我很想用时间戳单独保存每个事件，然后按需查询和计数，但这很慢。我正在寻找更好的东西，如果它存在的话。

示例请求：

• 过去 10 分钟内有多少独特的人点了意大利辣香肠披萨
• 在过去 30 分钟内，某人 John Doe 订购了多少个独特的意大利辣香肠披萨

有人可以解释或链接到有关如何使用 HLL 计算集合的基数可用于时间序列分析的解释吗？

我很确定druid.io确实做到了这一点，但我正在寻找一个关于如何单独使用 HLL 来做到这一点的一般解释，没有任何特定的库/数据库或特定的 HLL 实现。

一种天真的方法是在我们正在计算的事物上加上时间戳。例如，以redis HLL API 为例，如果您正在计算事件，从第 1000001 秒到第 1000060 秒：

这将遇到的一个问题是，您需要在给定范围内的每一秒进行迭代，以找出最后一分钟特定事件的计数。

Redis recently released their new data structure called the HyperLogLog. It allows us to keep a count of unique objects and only takes up a size of 12k bytes. What I don't understand is that Redis's PFCOUNT command is said to be technically a write command. Why is this the case?

Note: as a side effect of calling this function, it is possible that the HyperLogLog is modified, since the last 8 bytes encode the latest computed cardinality for caching purposes. So PFCOUNT is technically a write command.

我自己实现了HyperLogLog algorithm. 它工作得很好，但有时我必须获取很多（大约 10k-100k）的 HLL 结构并将它们合并。

我将它们中的每一个都存储为一个位字符串，所以首先我必须将每个位字符串转换为存储桶。由于有很多 HLL，它需要的时间比我想要的要多。

目前，大约 80% 的运行时会为每个 HLL 调用一次这行代码：

my @buckets = map { oct '0b'.$_ } unpack('(a5)1024', $bitstring);

有什么方法可以更快地做到这一点？

如果我们将 HyperLogLog 的定义抛在脑后，任务可以这样解释：假设它$bitstring由 1024 个 5 位计数器组成（因此每个计数器的值最高可达 32），我们必须将其转换为 1024 个整数的数组。

根据PFADD 命令的 Redis 文档：

谁能解释以下两点？

1. 这是否意味着如果计数器确实增加了 1，PFADD 将返回“1”？是否保证在运行 PFADD 后，新的 PFCOUNT 将为PFCOUNT(before) + output of PFADD？换句话说，单线程客户端能否仅使用 PFADD 的输出来跟踪计数？
2. 当 PFADD 返回“0”或“1”时，它们是否分别转换为“缓存命中”和“缓存未命中”？

HyperLogLog 算法一直困扰着我的是它对密钥哈希的依赖。我遇到的问题是该论文似乎假设我们在每个分区上都有完全随机的数据分布，但是在经常使用它的上下文中（MapReduce 样式作业），事物通常按其哈希值分布，因此所有重复的键都会在同一个分区上。对我来说，这意味着我们实际上应该添加由 HyperLogLog 生成的基数，而不是使用某种平均技术（在我们通过散列与 HyperLogLog 散列相同的东西进行分区的情况下）。

所以我的问题是：这是 HyperLogLog 的真正问题还是我没有足够详细地阅读论文

尽管项目大致相同，但基数差异太大，这是为什么呢？我一直期待 pfcount 之后的基数约为 12000。

另外，从上面的数据来看，我已经统计了上面pfadd列中pfadd返回1的时候，也执行了上面的pfcount。为什么 pfadd 和 pfcount 如此不同？