模块，用于唯一的访问者计数

Question

我在求职面试中得到了这个：

让我们假设您完成了任务:编写一个模块，在该模块的输入上将指向站点访问者的无限IP地址流。 在任何时刻，模块应该能够快速回答，收集了多少唯一的用户(唯一性由IP地址指定)。在以下条件下，你将如何(详细地)描述解决这个问题的方法： ( a)它需要获得确切数量的独特游客 ( b)误差小的近似值不超过3-4%是可以接受的。

你在这里看到了什么解决方案？我已经找到了几个关于流算法的白皮书，但我不知道它在本例中是否适用：

http://www.cs.berkeley.edu/~satishr/cs270/sp11/rough-notes/Streaming.pdf 问题

Answer 1

你找到的解决方案绝对是适用的。

对于(a)我将有一个计数器为全部唯一的IP，并将创建一个哈希，其中的密钥将是IP地址，你需要存储每一个IP地址，无论何时你收到一个IP，你检查它是否已经在哈希，如果它不是你存储在那里，并增加一个计数器。

另一方面，对于(b)，我将使用对IP本身的散列功能来进一步压缩它们，然后将它们插入到一个更小或更高效的哈希上。这样，碰撞的概率就会存在，但你也会获得一些性能。

Answer 2

有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字节。

Answer 3

假设没有IPV6地址，则使用4个字节255.255.255.255对IPV4地址进行编码。这给了我们32位

您可以使用32层的二叉树来存储ip地址，这将让您知道ip是否存在于树中，快速而容易地插入它，.然后，查找ip的操作数将接近32*2。

您可能更喜欢使用Trie树，有8个级别，每个级别存储4位。最多的行动次数为8*16次。

这将是一种比允许一个完整数组的内存更便宜的方法，而且Trie也可以以较低的成本用于IPV6。