與輸入

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

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

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

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

感謝您閱讀帖子

2013-04-05 linux developer

正在@linuxdeveloper然後gnu排序可以工作，如果你有足夠的磁盤空間。然後，您可以執行您聲明可以執行的已排序序列的交集。 – Paddy3118 2013-04-06 12:27:22

這個問題聲稱「排序和發現相交...不是一個可行的解決方案」。但是，從編碼的簡易性和清晰度的角度來看，排序是最好的解決方案之一。對於任何一次性問題，花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萬個浮點值進行排序。

來源

2013-04-06 04:26:57

假設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

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

來源

2013-04-05 23:37:10 dan

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

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

什麼是統計數字？

來源

2013-04-05 23:37:59

對我來說，問題歸結爲：

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

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

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

來源

2013-04-06 00:13:49 lsk

回答

相關問題