代码之家 › 专栏 › 技术社区 › David

算法查找不在集合中的元素

set data-structures algorithm

0

David · 技术社区 · 14 年前

我有一个产品列表p1,p2,…每个产品都有一个属性列表a1,a2,…。找到所有没有某些属性的元素(比如a2、a6、a10)的最快算法是什么?

如果 P1=A1、A2、A3_ P2=A3_ P3=A1,A4 ,算法返回p2,p3

问题是,我不知道属性的输入列表是由用户传入的。产品列表及其相关属性存储在数据库中:

产品表(超过10000行)

ProductID int,
ProductName varchar

属性表(大约有400行,将来可能会增长)

AttributeID int,
AttributeName  varchar

产品属性关联表

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个表的数据缓存到内存中,并编写一个有效的查找算法。你能提出一些我应该调查的问题吗?谢谢

编辑: 更新数据库不是问题。缓存将每小时从数据库中重建一次,因此构建缓存的时间就不那么重要了。

记忆也不是问题。

3 回复 | 直到 14 年前

1

0

Ssancho 14 年前

这可能取决于您更新数据库的频率,如果不太频繁,您可以:

对于每个attributeID,都有一个包含它的productID的排序列表(或数组)。当查询到达时,获取与该属性对应的产品列表,合并它们,然后将其与已排序的产品ID列表合并。

在您的示例中,如下所示:

A1->P1,P3
A2->P1_
A3->P1,P2
A4->P3
…

2

0

Victor Sorokin 14 年前

以下是简单的解决方案:

对于每个属性,将拥有该属性的每个产品放入hashtable中,属性用作键;
当用户的输入到达时,使用所有现有产品初始化结果,然后迭代属性并检查属性是否存在于哈希表中,如果存在,则从结果中删除与该属性相关联的所有产品;
当迭代完成时,您所拥有的就是您的结果。

3

0

nang 14 年前

您可以直接在产品表中实现“缓存”:

创建一个二进制字段“attributecache”,其中每个位表示一个属性
执行按位计算缓存字段的查询

从产品中选择ProductID 其中attributeCache&:attributeMask=0

搜索a2、a6、a10 attributemask显然是(最多填充16个属性): 0100010001000000元

如果数据库允许这样做,您还可以为attributeCache字段创建索引,以避免全表扫描。