模塊的獨立訪客數

我得到這個在面試：模塊的獨立訪客數

讓我們假設你得到了任務：寫一個模塊，輸入其網站訪客的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

模塊的獨立訪客數

回答

相關問題