模块的独立访客数

我得到这个在面试：模块的独立访客数

让我们假设你得到了任务：写一个模块，输入其网站访客的IP位址的无限流将指导。

在任何时候模块应该能够快速回答，如何收集许多独特的用户（唯一性由IP地址地址指定）。你怎么会在条件描述解决这个问题（详细）的方法说：

一）它需要获得独立访问者的确切数额

b）用小的误差不超过3近似值-4％是可以接受的

你在这里看到什么解决方案？我发现关于流算法几个白皮书，但我不知道这是否是appliable在这种情况下与否：

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

来源

2015-02-24 paus

如果我给了这个任务，我会指出a）和b）的要求是矛盾的。然后我会问我有多少记忆......以及“无限”流真的是多久。 – 2015-02-24 13:01:00

我们假设RAM是8 Gb。 – paus 2015-02-24 13:05:22

如果您只需处理32位IPv4地址，则可以使用简单的解决方案（由@Stephen C提议）位位向量（半个千兆字节）。这样，您可以保持唯一地址的精确计数。

但是现在，有必要考虑128位的IPv6地址，这是一个太大的命名空间，无法使用位向量。不过，如果您只需要近似计数，则可以使用Bloom filter（每个条目需要k位），用于与您准备接受的预期误报数量相关的某个小值k。假阳性将导致独立的IP地址被计数，因此误报的比例大致是计数的预期不准确。

正如链接的维基百科页面所提到的，每个条目使用10位预计会将假阳性百分比保持在百分之一以内;拥有8 GB内存，您可以维护一个拥有约68亿条记录的Bloom过滤器。

来源

2015-02-24 16:45:51 rici

你找到的解决方案是绝对appliable

对于（一）我会有一个总计唯一IP地址的计数器，并且会创建一个Hash，其中的密钥将是IP地址，您需要存储每个IP地址si 这样，只要您收到IP，就会检查它是否已经在Hash中如果它不存在，则将它存储在那里并将计数器增加1。另一方面，对于（b），我会在IP上使用散列函数来将它们压缩更多，然后将它们插入到更小或更有效的散列表中。这种方式存在碰撞的可能性，但你也获得了一些性能。

来源

2015-02-24 14:24:09 hbejgel

有2^32个唯一的IPv4地址。

因此实现一个索引与IP地址相对应的2^32布尔值数组。每次你访问：

ip_index = convert_ip_to_32bit_integer(ip) 
if !seen[ip_index]: 
    seen[ip_index] = true 
    nos_unique_visitors++

这需要2^29字节的内存（即0.5GB）假设你收拾的布尔值8每字节。

来源

2015-02-24 15:41:28

您认为没有IPv6地址。 – rici 2015-02-24 16:29:59

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

你可以使用一个32级的二叉树来存储IP地址，它会让你知道树中是否存在一个IP，插入它很容易，... 然后找到一个IP的操作数近似于是32 * 2附近的东西。

你可能更喜欢使用Trie树，有8级，每个级别存储4位。最大操作次数为8 * 16。

这将是一个比允许全阵列存储器更便宜的方法，并且Trie也可以用更低的成本用于IPV6。

来源

2015-02-24 19:12:09 Adam

模块的独立访客数

回答

相关问题