如何僅在集合A中找到不同集合的網址

有兩組網址，都包含數百萬個網址。現在，我如何從A中得到一個不在B中的URL？什麼是最好的方法？
注意：您可以使用任何技術，使用任何工具，如數據庫，mapreduce，哈希碼等。我們應該考慮內存高效，時間效率高。你必須考慮到每個集合（A和B）都有數以百萬計的URL。我們應該嘗試使用更少的內存和更少的時間來查找特定的URL。如何僅在集合A中找到不同集合的網址

來源

2010-09-29 Charlie Epps

什麼意思？內存高效？時間有效？ – 2010-09-29 01:38:57

你想只找到一個網址或全部網址嗎？ – JoshD 2010-09-29 01:41:52

有多少百萬個網址？特別是，我們可以期待它們都適合記憶嗎？這是你需要做的一次，還是一次重複？ – 2010-09-29 01:43:15

體面算法可能是：所有的集合A

加載到一個HashMap，O（一）

遍歷組B，並且對於每個項，刪除從組A中的相同的值（從hashmap）如果存在，O（b）

然後你的hashmap有結果。這將是O（a + b），其中a是集合A的大小，b是集合B的大小。（實際上，這將乘以散列時間，理想情況下對應於大約O 。）

來源

2010-09-29 01:41:25 JoshD

東西也許有點天真可能會像

程序排序列出一個
排序名單B
導航列表A和B一起這樣的：

一個。增加指向A的指針和元素匹配時指向B的指針

b。到B增量指針，直到元件中的下一個元素匹配a或直到記錄b在B在a的下一個元素之後將出現（治丟棄在乙不在A元素）

℃。當按照這些規則遞增時發現匹配，使得B中的下一個元素b與A中的下一個元素a不匹配。

這實際上可能是適用Bloom filters一個有趣的地方：構建布隆過濾器的集B則集合A中的每一個URL確定它是否是在集B.隨着錯誤的diminishingly小概率你應該能夠找到A中的所有網址不在B中。

來源

2010-09-29 01:44:39

(sort -u A; cat B B) | sort | uniq -u

來源

2010-10-05 08:07:47 piccolbo

如何僅在集合A中找到不同集合的網址

回答

相關問題