整數列表的子集計算

我目前正在實現一個算法，其中一個特定的步驟需要我以下面的方式計算子集。整數列表的子集計算

想象一下，我有整數集（可能是數百萬）。其中，各組可能包含大約1000元：

Set1: [1, 3, 7] 
Set2: [1, 5, 8, 10] 
Set3: [1, 3, 11, 14, 15] 
..., 
Set1000000: [1, 7, 10, 19]

想象一個特定的輸入設置：

InputSet: [1, 7]

我現在要迅速計算出此InputSet是一個子集。在這種特殊情況下，它應該返回Set1和Set1000000。

現在，蠻力它需要太多的時間。我也可以通過Map/Reduce進行並行處理，但我正在尋找更智能的解決方案。而且，在某種程度上，它應該是內存有效的。我已經使用BloomFilters快速消除了輸入集永遠不會成爲子集的集合，從而優化了計算。

任何聰明的技巧，我錯過了？

謝謝！

來源

2013-01-02 user1943042

什麼語言？你有樣品代碼嗎？ – fge

語言並不重要（儘管Java將是首選）。尋找更多的概念性解決方案。 – user1943042

如果這是Java，'Set'已經有'.containsAll（）'，我想你已經試過了？或者你真的想避免內建解決方案？此外，你的集合是否總是排序？ – fge

好吧 - 瓶頸似乎是集合的數量，所以不是通過遍歷所有集合來找到集合，而是通過從元素映射到包含它們的所有集合來提高性能，並返回包含所有集合的集合您搜索的元素。

這是非常相似的information retrieval領域搜索inverted index當什麼是AND查詢完成。

在你的榜樣，你將有：

1 -> [set1, set2, set3, ..., set1000000] 
3 -> [set1, set3] 
5 -> [set2] 
7 -> [set1, set7] 
8 -> [set2] 
...

編輯：
在IR倒排索引，以節省空間，我們有時會使用d-差距 - 這意味着我們存儲的文檔之間的偏移而不是實際的數字。例如，[2,5,10]將變成[2,3,5]。這樣做並使用delta encoding來表示這些數字在涉及太空時會起到很大的幫助作用。（當然還有一個缺點：你需要閱讀整個列表才能找到一個特定的集合/文檔，並且不能使用二分查找，但它有時是值得的，特別是如果它是差別的或者將索引裝入RAM中）。

來源

2013-01-02 14:21:09 amit

我在同一行（倒排索引）思考。唯一的缺點是它大約加倍處理所需的內存量。希望有更高的內存效率...... – user1943042

您可以通過對倒排索引中的鍵進行散列並允許衝突來壓縮索引，並交易一些內存進行計算。作爲一個極端的例子，你可以通過最低有效位索引，所以你有一個包含奇數的集合列表，以及另一個包含偶數集合的列表。 –

現在我想到了更多，是不是我提出的等同於布隆過濾器？ –

如何存儲包含每個數字的集合列表？

1 -- 1, 2, 3, 1000000 
3 -- 1, 3 
5 -- 2 
etc.

來源

2013-01-02 14:21:33

輸入開始從最大號搜索（7）設置和消除其它子集（設置1和Set1000000將返回）。
在其餘集合中搜索其他輸入元素（1）。

來源

2013-01-02 15:32:09 Kad

擴展amit的解決方案，而不是存儲實際的數字，你可以只存儲間隔和它們相關的集合。

例如使用5一間隔尺寸：

(1-5): [1,2,3,1000000] 
(6-10): [2,1000000] 
(11-15): [3] 
(16-20): [1000000]

在（1,7）的情況下，應考慮的時間間隔（1-5）和（5-10）（其可被簡單地確定通過了解間隔的大小）。相交這些範圍給你[2,1000000]。二進制搜索集顯示確實（1,7）存在於兩個集合中。

雖然您需要檢查每個集合的最小值和最大值，以更好地瞭解區間大小應該是多少。例如，如果最小值和最大值從1到100萬，5可能是一個不好的選擇。

您應該保留它以便可以使用二進制搜索來檢查值，因此子集範圍應該類似於（min + max）/ N，其中2N是需要的最大值數在每組中進行二進制搜索。例如，「第3組包含5到10的任何值嗎？」這是通過找到最接近5（3）和10（11）的值來完成的，在這種情況下，它不會。您必須通過每個集合，然後對可能在集合內的區間值執行二進制搜索。這意味着確保當設置僅達到10時不會搜索100.

您也可以只存儲範圍（最小值和最大值）。但是，問題是我懷疑你的號碼將被聚集，因此不能提供太多的用途。雖然如前所述，但它可能對確定如何設置間隔很有用。

選擇使用範圍太大，構建數據結構需要很長時間（1000萬* log（N）），這仍然很麻煩。太小了，你會開始遇到太空問題。該範圍的理想大小可能確保與每個範圍相關的組的數量大致相等，同時還確保範圍的總數不太高。

編輯：一個好處是，你實際上並不需要存儲所有的間隔，只是你需要的。儘管如果您有太多未使用的時間間隔，增加間隔時間並拆分當前時間間隔以確保搜索速度較快可能是明智的做法。如果處理時間不是主要問題，則尤其如此。

來源

2013-01-02 15:34:48 Nuclearman

整數列表的子集計算

回答

相關問題