搜索與大集合整數的區別

Question

我有2個大整數數組。我必須得出這些數組的差異（即第二個數組中的元素，而不是第一個中的元素，反之亦然）。我正在執行線性搜索並將差異存儲在數組中。有什麼方法可以更快地完成（線性時間）？

Answer 1

如果您將一個數組放入散列集，然後運行另一個數組，探查散列集，那麼很容易就可以獲得O（n + m）時間。當然，如果你的數組被排序，那麼你可以直接使用O（n + m）。

Answer 2

我會說可能，這取決於你的需求。您可以將列表分解爲小集合，並使用線程處理每個集合，將結果合併回集中池。

雖然不是非常困難，但您需要進行一些管理，以便將結果組織回正確的順序（因爲線程2可能會在線程1之前完成），並監視進程以瞭解它何時完成。

你可以看看在Executors Tutorial瞭解更多信息

Answer 3

哈希是很好的，但對於一組數據結構？

stromberg@aw50 ~ $ /usr/local/pypy-1.9/bin/pypy 
Python 2.7.2 (341e1e3821ff, Jun 07 2012, 15:38:48) 
[PyPy 1.9.0 with GCC 4.4.3] on linux2 
Type "help", "copyright", "credits" or "license" for more information. 
And now for something completely different: ``<arigato> the AI state is indeed 
close'' 
>>>> s1 = set(range(10)) 
>>>> s2 = set(range(5,15)) 
>>>> s1 
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) 
>>>> s2 
set([5, 6, 7, 8, 9, 10, 11, 12, 13, 14]) 
>>>> s1 - s2 
set([0, 1, 2, 3, 4]) 
>>>> s2 - s1 
set([10, 11, 12, 13, 14]) 
>>>> s1 & s2 
set([8, 9, 5, 6, 7]) 
>>>> s1 | s2 
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]) 
>>>> 

我想這是一個方便的方式，並且快速的列表，適合在同一時間的內存。

還有一些東西，如磁盤BTrees或bloom過濾器。

使用BTrees，您不必將所有內容都放在內存中，並且可以類似於合併排序的合併步驟進行差異化。他們基本上是一個有序的數據庫表。

對於布隆過濾器，如果您需要篩選需要考慮的事物數量，它們非常適合;他們是概率性的，並且可以給出諸如「這絕對不在集合中」以及「這幾乎肯定在集合中」的答案。 Bloom過濾器的主要好處是它們只需要很少的內存（有時每個元素只有一位）。好的實現將允許你指定你的最大允許錯誤概率。 EG，檢測* ix硬鏈接幾乎是一個設置成員資格問題，bloom過濾器非常適合 - 他們給你一個可能的硬鏈接的簡短列表，之後可以很快地做到100％準確，因爲硬鏈接的數量趨向於即使實際文件的數量很大，也很小。

Answer 4

你不需要任何花哨。如果你的數組被排序，那麼通過每個數組的單個傳遞足以獲得差異。只需在每個數組中保留一個索引，並且如果索引指向相等的元素，則增加這兩個索引，否則將下面的元素添加到您的返回數組並增加其索引。

這裏是代碼，在去，做到這一點：http://play.golang.org/p/VZgGWmu-aO

這種解決方案需要O（N + M）時間，O（N + M）的空間，你真的不能做的更好。它也沒有涉及散列表的解決方案的開銷。

Answer 5

這是實現你的目標的生硬方式：

public static Set<Integer> foundInFirstButNotSecond(int[] first, 
     int[] second) { 
    Set<Integer> secondSet = new HashSet<Integer>(second.length); 
    for (Integer i : 
      second) { 
     secondSet.add(i); 
    } 
    Set<Integer> resultSet = new HashSet<Integer>(first.length); 
    for (Integer j : 
      first) { 
     if (!secondSet.contains(j)) { 
      // Current integer from first not found in second 
      resultSet.add(j); 
     } 
    } 
    return resultSet; 
} 

注意，它返回一組，而不是一個數組，但你可以很容易地修改這個代碼，如果適合你更好地產生一個數組來代替。

舉個例子，如果你把這個代碼：

public static void main(String[] args) { 
    int[] first = new int[]{1, 2, 3, 4, 5, 6}; 
    int[] second = new int[]{5, 6, 7, 8}; 
    System.out.println("In first but not second: " + ArrayCompare. 
      foundInFirstButNotSecond(first, second)); 
} 

，你會得到一個集的內容[1，2，3，4]。 （請注意，HashSet不保證任何特定的順序，所以你可以得到這種混亂的變化。）

Answer 6

假設兩個數組排序，你可以使用兩個slinding指針來找到差異。時間複雜度是O（n + m）和空間O（max（n，m））。

void set_difference(std::vector<int> & array1,std::vector<int> & array2,std::vector<int> & output) 
{ 
    auto index1 = 0 ; 
    auto index2 = 0 ; 
    while (index1 != array1.size() & index2 != array2.size()) 
    {  //since the arrays are sorted, we can stop looking right when we find a number bigger 
     while ((array1[index1] < array2[index2]) & index2 != array2.size()) 
      index2++ ; 
     if (array1[index1] != array2[index2]) //array1[index1] is not array2 
      output.push_back(array1[index1]); 
     index1++ ; 
    } 
}