從一個集合中查找元素的最佳方法不在另一個集合中

我有兩個集合。一個帶有ID和內容的項目列表，我們可以調用這個列表ItemList。我有另一個集合告訴我用戶是否選擇了一個項目。調用此列表收集它將具有用戶標識和項目標識。用戶和項目的數量都非常大。對於不在列表中收集的用戶，從ItemList中查詢項目的最佳方法是什麼？從一個集合中查找元素的最佳方法不在另一個集合中

這裏有一些想法，我有：

加入使用關係數據庫來解決這個問題。我唯一的疑問是，這將處理非常大的數據集。
使用blooms過濾器來存儲收集的項目列表，並在查詢項目時檢查它是否不在過濾器中。

如果上述思想不能擴展，你可以給我提供算法。這些不能成爲內存中的解決方案，因爲我肯定需要保存數據。

來源

2014-09-13 satran

似乎是一個平衡線算法。檢查[this]（http://www.isqa.unomaha.edu/haworth/isqa3300/fs006.htm） – Max 2014-09-13 15:28:25

也可以使用位集。

Load into some bitset ItemList (ItemID is index in the bitset). 
Load into another bitset IDs_for_user for this user. 
Perform opearation: Resut = ItemList ANDNOT IDs_for_user.

免費的bitset庫，你可以在這裏： http://bmagic.sourceforge.net/

來源

2014-09-13 15:48:09 maxihatop

我喜歡這種方法。在我可以設置這個答案之前，我只會對它進行一些研究。 – satran 2014-09-13 16:03:49

從一個集合中查找元素的最佳方法不在另一個集合中

回答

相關問題