我面臨一個問題，在一些單詞中，我打電話給一個HashMultimap（Guava）來檢索一組整數。結果集分別有10,200和600個項目。我需要計算這三個（或四個，或五個......）集合的交集，並且我需要多次重複這個整個過程（我有許多單詞集合）。然而，我所經歷的是，平均來說，這些集合交點需要很長時間來計算（從0到300毫秒），如果我查看數十萬個單詞集，我的程序需要很長時間才能完成。更快的方法設置交集
是否有任何實質上更快的方法來實現這一點，特別是考慮到我處理（可排序）整數？
非常感謝！
如果您能夠將您的集合表示爲位數組（位圖），則可以使用AND運算將它們相交。你甚至可以實現這個並行運行。
作爲一個例子（使用jlordo的問題）：如果是SET1 {1,2,4}和SET2是{1,2,5}
然後，你的第一組將被表示爲：設置00010110（位對於1,2和4）。 你的第二組將被表示爲：00100110（設置爲1,2和5的位）。
如果你和他們在一起，你會得到：00000110（1位設置和2）
當然，如果你有一個更大範圍的整數，那麼你將需要更多的字節。位圖索引的優點在於，它們每個可能的元素只需要一位，因此佔用相對較小的空間。例如，在Java中，您可以使用BitSet數據結構（不知道它是否可以並行執行操作）。
說set1是'{1,2,4}'而set2是'{1,2,5}'，那麼如何和一個bitset給出結果'{1,2}'，這是交集？ – jlordo
謝謝，我在想這樣的事情，但是 （a）不確定要使用哪種數據結構 （b）我不確定這樣的操作是否比標準交叉點快得多？ – user1980127
@jlordo：我編輯了文本以顯示如何。 – Eduardo
基於位圖的解決方案的一個問題是，即使這些集合本身非常小，但包含非常大的數字（甚至是無界的），檢查位圖也是非常浪費的。
不同的方法是，例如，排序兩個集合，合併它們並檢查重複。這可以通過O（nlogn）時間複雜度和額外的O（n）空間複雜度來完成，給定集合的大小爲O（n）。
您應該選擇符合問題描述的解決方案（輸入範圍，預期集合尺寸等）。
+1我同意，如果集合的元素位於特定範圍內，位圖索引是很好的。他們不一定要從低開始，因爲你的第一位可以代表任何數字。 – Eduardo
但是，通常基於HashMap的解決方案（檢查較小集合的每個元素）只取O（m），其中m是較小集合的大小？ – user1980127
HashMap的東西是它們被設計用於快速訪問元素，但不能用於排序操作。 @Eran的建議與合併類似。您需要更適合保持您的集合順序的數據結構。 – Eduardo
帖子http://www.censhare.com/en/aktuelles/censhare-labs/yet-another-compressed-bitset描述了具有設置操作（聯合，減號和相交）的有序原始長集的實現。根據我的經驗，對於密集或稀疏的價值羣體而言，這非常有效。
你能告訴我們你用來計算交叉點的代碼嗎？ – jlordo
什麼是整數？什麼是最大整數？ – starblue
可以，儘管我不得不縮短它 - 所以基本上我所做的是從Multimap中爲每個單詞檢索一個集合，然後按頻率對集合進行排序，最後以最小的二。 但我發現了另一個可能的瓶頸：我爲每個返回的集合創建了一個新的HashSet。也許這會導致很多開銷。讓我們來看看。 – user1980127