算法找不到集合中的元素

我有一個產品列表{P1，P2，...}，每個產品都可以有屬性列表{a1，a2，...}。找到不具有某些屬性的所有元素（{a2，a6，a10}）的最快算法是什麼？算法找不到集合中的元素

如果 P1 = {A1，A2，A3} P2 = {A3} P3 = {A1，A4} ，該算法應該返回{P2，P3}

的問題是我不」 t知道屬性的輸入列表是由用戶傳入的。產品及其相關屬性的列表存儲在數據庫中：

產品表（擁有超過10000行）

ProductID int, 
ProductName varchar

屬性表（有大約400行，在未來可能會增長）

AttributeID int, 
AttributeName varchar

Product_Attribute_Association表

ProductID int, 
AttributeID int

查詢我的是：

SELECT p.ProductID, p.ProductName 
FROM Product p 
WHERE p.ProductID NOT IN 
(SELECT pa.ProductID FROM Product_Attribute_Association pa 
WHERE pa.AttributeID NOT IN (1, 4, 5) -- What ever being passed in 
) t

這項服務將被打到相當困難，我想在一些數據結構緩存3個表中的數據在內存中寫入一個有效的算法做查找。你能建議一些我應該看看的東西嗎？謝謝

編輯：更新數據庫不是問題。緩存將每小時從數據庫重建，因此建立緩存的時間不再是問題。

內存也不是一個問題。

來源

2010-10-06 David

這可能取決於你將如何經常更新數據庫，如果不是太頻繁，您可以：

對於每個屬性ID，有有它productIds的排序列表（或陣列）。當查詢到達時，取對應於該屬性的產品列表，合併它們，然後將其與productIds的排序列表合併。

在你的榜樣，這看起來像：

A1 - > {P1，P3}
A2 - > {P1}
A3 - > {P1，P2}
A4 - > {p3}
...

來源

2010-10-06 15:55:33 Ssancho

更新數據庫不是問題。緩存將每小時更新一次，因此構建緩存的時間不再是問題。 – David 2010-10-06 16:19:53

這裏的天真的解決方案：

對於每一個屬性，將每個誰擁有此屬性與作爲一個關鍵屬性哈希表的產品;
當用戶輸入到達時，用所有現有產品對結果進行初始化，然後迭代屬性並檢查哈希表中是否存在屬性，如果是，則從結果中刪除與此屬性關聯的所有產品;
迭代完成後的結果就是你的結果。

來源

2010-10-06 16:07:03

您可以實現的「緩存」直接在產品表：

創建一個二進制領域「AttributeCache」，其中每一位代表一個屬性
執行該按位計算的查詢attributeMask = 0

選擇的ProductID

要搜索{A2，A6，A10} attributeMask會明顯地（填充到16個屬性）： 01000100.01億

如果你的數據庫允許的話，你還可以創建爲AttributeCache指數字段以避免全表掃描。

來源

2010-10-07 07:49:42 nang

算法找不到集合中的元素

回答

相關問題