比较基于键组合的词典

Question

我有一个这样的列表"记录"

data = [
    {'id':1, 'name': 'A', 'price': 10, 'url': 'foo'},
    {'id':2, 'name': 'A', 'price': 20, 'url': 'bar'},
    {'id':3, 'name': 'A', 'price': 30, 'url': 'baz'},
    {'id':4, 'name': 'A', 'price': 10, 'url': 'baz'},
    {'id':5, 'name': 'A', 'price': 20, 'url': 'bar'},
    {'id':6, 'name': 'A', 'price': 30, 'url': 'foo'},
    {'id':7, 'name': 'A', 'price': 99, 'url': 'quu'},
    {'id':8, 'name': 'B', 'price': 10, 'url': 'foo'},
]

我想删除"重复"的记录,其中相等性由逻辑条件列表定义.列表中的每个元素都是OR条件,所有元素都是AND.例如:

filters = [  ['name'],   ['price', 'url']  ]

意味着如果两个记录的名称和(它们的价格或URL)相等,则认为它们是相同的.对于上面的例子:

For item 1 the duplicates are 4 (by name and price) and 6 (name+url)
For item 2 - 5 (name+price, name+url)
For item 3 - 4 (name+url) and 6 (name+price)
For item 7 there are no duplicates (neither price nor url match)
For item 8 there are no duplicates (name doesn't match)

因此,结果列表必须包含项目1,2,3,7和8.

请考虑到这一点

• 可能会有更多AND条件: ['name'], ['price', 'url'], ['weight'], ['size'], ...
• 条件列表中的OR组可以超过2个项目,例如 ['name'], ['price', 'url', 'weight']...
• 源列表很长,O(n^2)不可能出现alogirthm

Answer 1

避免O(n^2)及时执行此操作的方法是为要执行的每个查询构建索引.一旦你有机器在恒定时间内查询任何值,你O(n^2)就会变得O(n)平凡.你也可以及时建立所有指数O(n).

假设您的每个值都具有相同的字段,它将如下所示:

indices = defaultdict(lambda: defaultdict(set))
for i, row in enumerate(data):
    for field in 'id', 'name', 'price', 'url':
        key = row[field]
        indices[field][key].add(i)

现在,要搜索特定值,就是这样:

def search(field, key):
    return (data[index] for index in indices[field][key])

要一起搜索一组值or,只需将它们分开搜索并将set.union它们组合在一起,如下所示:

def search_disj(factors):
    sets = (indices[field][key] for field, key in factors)
    return (data[index] for index in reduce(set.union, sets))

并且为了一起搜索一组析取and,为每一个做同样的事情,然后将set.intersection所有结果放在一起.

根据您的数据,只需查找第一个索引,然后线性搜索其他因素的结果,效率会更高.您可以通过重新排序字段来进一步优化,以便搜索具有最小字段的字段len(indices[field]).(或者,在这种情况下,具有最小总和的一个(len(indices [field])对于disj中的字段).)

如果你可以任意嵌套 - 连接的析取连接......直到你得到单个元素 - 你只需要相互递归调用其他函数(使用扁平元素的基本情况).您甚至可以将其扩展为完全通用的布尔搜索(尽管您还需要一个not操作- universe - indices[field][key]其中universe = set(range(len(data)))- 为此).

如果数据非常大,您可能无法将所有索引存储在内存中.

或者,即使你可以将所有索引存储在内存中,缓存甚至页面未命中都可能使哈希表不理想,在这种情况下你可能想要考虑基于B树的东西(例如blist.sorteddict),而不是一个字典.这也为您提供了搜索值范围,订购结果等的优势.缺点是所有这些n时间都变成了n log n,但是如果您需要这些功能,或者您获得了两个数量级的地点效益以换取log(n, base)成本仅为7,这是值得的.

或者,或者使用某种磁盘支持的类似dict的存储,就像一个anydbm.

但是,实际上,您正在构建的是仅具有单个关系(表)的关系数据库.在许多情况下,你最好只使用一个现成的关系数据库,就像sqlite3内置的Python 一样.然后构建索引的代码如下所示:

db.execute('CREATE INDEX id_idx ON data (id)')

......你可以只做查询,他们以最好的方式神奇地使用正确的指数:

curs = db.execute('SELECT * FROM data WHERE name = ? AND (price = ? OR url = ?)', 
                  filters)

Answer 2

基于 Tim Pietzcker 的想法，以下内容对我有用：

我们首先将 CNF 条件转换a&(b|c)为 DNF：(a&b)|(a&c)。使用问题中的列表符号，即[ [a], [b, c] ]，DNF 将是[ [a, b], [a, c] ]。在 python 中，这就像itertools.product(*filters).

然后我们迭代列表并为 DNF 中的每个连接创建一个组合键：

( (a, rec[a]), (b, rec[b]) )

并检查是否已经看到任何键。如果不是，我们认为该记录是唯一的并将其键添加到集合中seen：

代码：

seen = set()
dnf = list(itertools.product(*filters))

for item in data:
    keys = set(
        tuple((field, item.get(field, None)) for field in conjunct) 
        for conjunct in dnf)
    if keys.isdisjoint(seen):
        seen |= keys
        print item # unique

感谢蒂姆给了我一个想法。如果有人发现此解决方案有任何问题，请告诉我。