独立访客数模块
Module for unique visitors count
我在求职面试中得到了这个：
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
您找到的解决方案绝对适用
对于 (a) 我会有一个唯一 IP 总数的计数器，并会创建一个哈希，其中的键是 IP 地址，您需要存储每个 IP 地址 si
这样，每当你收到一个 IP 时，你都会检查它是否已经在哈希中，如果不在，你将它存储在那里并将计数器加一。
另一方面，对于 (b)，我会在 IP 本身上使用散列函数来进一步压缩它们，然后将它们插入到更小或更高效的散列中。这样碰撞的概率是存在的，但是你也获得了一些性能。
有 2^32 个唯一的 IPv4 地址。
因此实现一个 2^32 布尔值数组，其索引对应于 IP 地址。每次访问：
ip_index = convert_ip_to_32bit_integer(ip)
if !seen[ip_index]:
seen[ip_index] = true
nos_unique_visitors++
这需要 2^29 字节的内存（即 0.5Gb），假设您将布尔值打包为每字节 8 个。
如果你只需要处理 32 位 IPv4 地址，你可以使用 232 的位向量的简单解决方案（由 @Stephen C 提出）位（半千兆字节）。有了它，您可以维护唯一地址的精确计数。
但是现在，有必要考虑 128 位 IPv6 地址，这个命名空间太大而无法使用位向量。但是，如果您只需要一个近似计数，则可以使用 Bloom filter，每个条目需要 k 位，因为 k 的一些小值与您预期的误报数相关准备接受。误报会导致一个唯一的ip地址被统计不出来，所以误报的比例大致是一个计数的预期不准确。
如链接的维基百科页面所述，每个条目使用 10 位有望将误报百分比保持在 1% 以下；使用 8 GB 的内存，您可以维护一个包含大约 680 万个条目的布隆过滤器。
假设没有IPV6地址，IPV4地址使用4个字节255.255.255.255编码。这给了我们 32 位。
您可以使用具有 32 级的二叉树来存储 IP 地址，这将让您知道树中是否存在 IP，快速轻松地插入它，...
查找 ip 的操作次数将 大约 接近 32*2.
您可能更喜欢使用 Trie 树，它有 8 个级别，每个级别存储 4 位。最大运算次数为，运算次数为8*16.
这将是一种比允许存储完整数组更便宜的方法，并且 Trie 也可以用于 IPV6，成本更低。
我在求职面试中得到了这个：
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
您找到的解决方案绝对适用
对于 (a) 我会有一个唯一 IP 总数的计数器，并会创建一个哈希，其中的键是 IP 地址，您需要存储每个 IP 地址 si 这样，每当你收到一个 IP 时，你都会检查它是否已经在哈希中，如果不在，你将它存储在那里并将计数器加一。
另一方面，对于 (b)，我会在 IP 本身上使用散列函数来进一步压缩它们，然后将它们插入到更小或更高效的散列中。这样碰撞的概率是存在的，但是你也获得了一些性能。
有 2^32 个唯一的 IPv4 地址。
因此实现一个 2^32 布尔值数组，其索引对应于 IP 地址。每次访问：
ip_index = convert_ip_to_32bit_integer(ip)
if !seen[ip_index]:
seen[ip_index] = true
nos_unique_visitors++
这需要 2^29 字节的内存（即 0.5Gb），假设您将布尔值打包为每字节 8 个。
如果你只需要处理 32 位 IPv4 地址，你可以使用 232 的位向量的简单解决方案（由 @Stephen C 提出）位（半千兆字节）。有了它，您可以维护唯一地址的精确计数。
但是现在，有必要考虑 128 位 IPv6 地址，这个命名空间太大而无法使用位向量。但是，如果您只需要一个近似计数，则可以使用 Bloom filter，每个条目需要 k 位，因为 k 的一些小值与您预期的误报数相关准备接受。误报会导致一个唯一的ip地址被统计不出来，所以误报的比例大致是一个计数的预期不准确。
如链接的维基百科页面所述，每个条目使用 10 位有望将误报百分比保持在 1% 以下；使用 8 GB 的内存，您可以维护一个包含大约 680 万个条目的布隆过滤器。
假设没有IPV6地址，IPV4地址使用4个字节255.255.255.255编码。这给了我们 32 位。
您可以使用具有 32 级的二叉树来存储 IP 地址，这将让您知道树中是否存在 IP，快速轻松地插入它，... 查找 ip 的操作次数将 大约 接近 32*2.
您可能更喜欢使用 Trie 树，它有 8 个级别，每个级别存储 4 位。最大运算次数为，运算次数为8*16.
这将是一种比允许存储完整数组更便宜的方法，并且 Trie 也可以用于 IPV6，成本更低。