在一段時間內實時最常見/重複的元素

我有用戶生成的字符串以未定義的速率進來，其中一些是重複的數據，我想保持頂級域名的數量，在Go中，在給定的恆定時間段（例如，過去一小時）內，實時最常見的20個副本。在一段時間內實時最常見/重複的元素

唯一字符串的數目並不以任何方式限定，所以，爲了避免DoS攻擊，該數據結構可能必須具有限定數量最多的元素（例如，頂部-10K-元件和/的大小或1MB的整體大小），並刪除最近插入的元素（如果它們沒有任何重複的話）（但不要刪除任何新來的元素！）。

我的理解是，這究竟是如何ngx_http_limit_req_module.c是implemented，並且這種方法在documentation爲「漏桶」的簡稱，但是，出現wikipedia頁面表明，它是會被丟棄的新數據從隊列中，而不是舊的，所以，不知道這個概念是否適用。無論如何，我試圖在Golang中尋找一個「漏桶」實現，到目前爲止，我發現的最流行的結果是uber-go/ratelimit，它的API看起來並不符合我的問題陳述 - 它只是實現了一些實際的速度限制隊列，而不是實時最後一次Y計數中的前X.

任何人都可以建議我正在尋找什麼，以及最好的方式來完成這個，最好在Go？

來源

2017-08-29 cnst

要實時搜索在你的陰莖你需要數據結構與預測的搜索/插入時間像balansed二叉樹或HashMap的或至少排序陣列。你可以縮短這個結構的週期。我建議布盧姆過濾器在Go中具有不變的搜索/插入時間和常量大小以及多個實現。 – Uvelichitel

你需要確切的計數，還是將概率估計足夠？ – btilly

我很好奇，如果有人認爲這是脫離主題可以解釋爲什麼它不適合https://stackoverflow.com/help/on-topic。該問題要求針對特定編程問題*的*算法*如何保持用戶搜索中顯示的實時前20名術語列表。這是一個實用的，可回答的問題，它是軟件開發所特有的。 - 找到我想要解決這類問題的其他人！儘管符合最初的標準，但這六種問題都不屬於主題。那麼爲什麼4個人得出結論說這是脫離主題？ – btilly

-1

這是兩個問題。

保持跟蹤您選擇要跟蹤的名稱。
注意到趨勢中的名稱不在您的列表中以便跟蹤。

對於第一個問題，我建議保持跟蹤名稱，每分鐘，有多少。完成後，將它們添加到正在運行的總數中，並添加到隊列中以在一小時內將其減去。這給你每個名稱60個小對象，並在運行的基礎上，你將保持散列。

第二個問題更具挑戰性。爲此，我會使用概率方法。我們的想法是，每個名稱都使用一個唯一的ID進行散列，並且只保留您在一分鐘內看到的最小的一千個哈希值（以及相關名稱）。（我會在一分鐘內給出一個算法。）你的散列值應該獨立於名稱平均分佈在2^64之間，所以常用名字最終將顯示在這個列表中。當他們這樣做時，你就開始數它們了！（你會失去頭幾個，但是有更多的工作可以估計你錯過了多少，這個優化可能比它的價值更大。）

現在我們該如何保持最小的一千個哈希值？您可以使用優先級隊列，這通常通過堆實現，以創建可更新的數據結構，以便輕鬆提取最大散列值。所以你運行下面的僞代碼。

create your priority queue of (hash, name) 
for each name: 
    hash hash of name and unique new id 
    entry = (hash, name) 
    if queue size < 1000: 
     insert entry 
    else if hash is smaller than the current max in the queue 
     insert entry 
     remove the largest entry

來源

2017-08-30 03:19:51 btilly

謝謝你的回答。你知道nginx如何實現這個嗎？文件似乎沒有提到任何一種概率不確定性。 – cnst

@cnst我回答了上述問題。這裏的概率設計允許在有限的存儲器需求下執行該操作，即使單個搜索項的數量非常大。在大型集羣上，它可以進行調整，以便進行計算並在多臺機器上合併。但取決於你的問題，這可能是矯枉過正。 – btilly

在一段時間內實時最常見/重複的元素

回答

相關問題