與輸入

Question

的大序列打交道時，選擇什麼我最近遇到一個問題

如何找到兩個序列的路口時，每個序列可以有重複號碼和規模是相當大的（接近一百萬）處理的數據類型爲Long。

我想到了排序，並找到交集這不是一個可行的解決方案 我甚至想過哈希表中這是行不通的空間考慮必須是最佳

能有人建議什麼將是更好的辦法處理它？

感謝您閱讀帖子

Answer 1

這個問題聲稱「排序和發現相交...不是一個可行的解決方案」。但是，從編碼的簡易性和清晰度的角度來看，排序是最好的解決方案之一。對於任何一次性問題，花10分鐘時間寫分類解決方案比花15分鐘寫一個哈希解決方案更合理，或者花半小時寫一個特殊的樹程序。

使用下面顯示的python代碼排序一百萬雙，我的舊PC（AMD Athlon 5000，大約2GHz）大約需要1.3秒，而且可能比現在的處理器快四到五倍。按時間排序兩個數組O（n lg n），然後按照問題的要求在時間O（n）中查找匹配項，在現代PC上可能需要一兩秒鐘。

In [237]: import random 

In [238]: v = [random.random() for i in range(1000000)] 

In [239]: %time u = sorted(v) 
CPU times: user 1.32 s, sys: 0.00 s, total: 1.32 s 
Wall time: 1.33 s 

請注意，question #8630965是指在1.168秒內對100萬個浮點值進行排序。

Answer 2

假設long爲固定大小，比如說64位。規劃深度最大爲64的部分二叉樹。對於第一個序列中的每個數字，您將生長樹。所有葉子都出現在深度64處。每片葉子有兩個整數，它們是引用這兩個序列的計數器。

for each number n in the first list 
    current_node = root 
    for i ranging from 1 to 64 
     if the i-th bit of n is zero 
      grow/traverse edge labeled 'zero' from current_node 
     else 
      grow/traverse edge labeled 'one' from current_node 
     set current_node to be at end of this edge 
    if the current_node (now at depth 64) is brand new 
     set the node's first counter to 1; second counter to zero 
    else 
     increment current_node's first counter by 1 

的這個第二部分是處理第二個列表，但更新第二計數器來代替。如果你願意，你也可以跳過創建新節點，因爲那裏不會有交集。然後遍歷整個樹並查看兩個計數器都不爲零。

Answer 3

我認爲每個列表有2M個條目的哈希表（所以哈希表加載保持合理的低，在50％或更低）是一個不錯的選擇。如果使用最簡單的實現方式，那麼快速，不是非常大，只有2M * 4B（你的長整型是4字節長，對嗎？）。

如果列表中有很少的唯一值，那麼排序/搜索樹將比哈希表更緊湊，但如果有很多唯一的數字，它將比哈希表更大（您需要子/父樹節點中的指針，這就是開銷）。

什麼是統計數字？

Answer 4

對我來說，問題歸結爲：

• 使用某種數據結構代表稀疏第一輸入
• 與第二輸入作爲密鑰到數據結構在現有步驟中計算遍歷它。

我最初的想法也是一個哈希表。但是每個數字我們都需要一個節點。另一位作者已經有了這個想法。

我的第二個想法是B +樹。我們可以使用這棵樹映射一個稀疏集合。葉子可以包含一系列的nos ...這樣，我們可以在查找與第二個輸入集合的交集時刻更多的cpu來搜索葉子。您確實需要支付內部節點中b +樹索引的成本。假設我們不在樹中存儲重複項...不需要交集。我們可以使用基於位的存儲優化葉片以減少空間。