algorithm - 独立访客数模块

Question

我在工作面试中得到了这个:

Let’s assume that you got the task: to write a module, on input of which an infinite stream of IP-addresses of site visitors will be directed .

In any moment of time module should be able to answer quickly, how many unique users are collected (uniqueness is specified by IP address). How would you describe the method of solving this question (in details) on the condition that:

a) it needs to get exact amount of unique visitors

b) approximate value with small inaccuracy not more than 3-4% is acceptable

您在这里看到了哪些解决方案？我找到了几本关于流算法的白皮书，但我不知道它是否适用于这种情况:

http://www.cs.berkeley.edu/~satishr/cs270/sp11/rough-notes/Streaming.pdf http://en.wikipedia.org/wiki/Count-distinct_problem

Answer 1

如果您只需要处理 32 位 IPv4 地址，您可以使用 2³² 位(半千兆字节)的位向量的简单解决方案(由 @Stephen C 提出)。这样，您就可以维护唯一地址的精确计数。

但如今，有必要考虑 128 位 IPv6 地址，这是一个太大的命名空间，无法使用位向量。但是，如果您只需要一个大概的计数，您可以使用 Bloom filter。 ，每个条目需要 k 位，对于与您准备接受的预期误报数相关的 k 的一些小值。误报会导致唯一IP地址无法统计，因此误报的比例大致是预期的计数不准确。

正如链接的维基百科页面所提到的，每个条目使用 10 位有望将误报百分比保持在 1% 以下；使用 8 GB 的内存，您可以维护一个包含大约 680 万个条目的布隆过滤器。