基于键的组合比较字典

Question

基于键的组合比较字典

7

I have a list "records" like this

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)算法是不可行的。

- georg

4

如果你有很多数据，应该认真考虑使用类似于sqlite3的东西来代替一个字典。 - abarnert

那么问题在哪里？你已经设计好了数据，知道函数应该做什么。问题出在哪里呢？这听起来更像是请帮我写代码。 - Sean Perry

2个回答

1

根据Tim Pietzcker的想法，以下内容适用于我：

我们首先将CNF条件转换为DNF，例如a&(b|c)转换为(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

感谢Tim给我提供了一个想法。如果有人发现这个解决方案存在问题，请告诉我。

- georg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- abarnert · Accepted Answer

避免在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])”（或在这种情况下，具有最小“sum(len(indices[field]) for field in disj)”）长度的字段来进一步优化。

如果您可以任意嵌套——由“or”连接的“and”，由“or”连接的“and”等，直到单个元素——那么您只需要让函数相互递归调用（对于平面元素有一个基本情况）。您甚至可以将其扩展到完全一般的布尔搜索（尽管您还需要“not”操作——“universe - indices[field][key]”，其中“universe = set(range(len(data)))”——为此）。

如果数据非常大，则可能无法在内存中存储所有索引。

或者，即使您可以在内存中存储所有索引，缓存和甚至页面漏洞可能会使哈希表不太理想，在这种情况下，您可能需要考虑基于B树（例如“blist.sorteddict”）而不是字典的东西。这还使您能够搜索值的范围，排序结果等。缺点是所有这些“n”次变成了“n log n”，但如果您需要该功能，或者如果您获得两个数量级的局部性优势来换取一个“log(n, base)”成本，而该成本仅为7，则可能值得。

或者，您可以使用某种磁盘支持的类似字典的存储，例如“anydbm”。

然而，实际上，您正在构建具有单个关系（表）的关系数据库。在许多情况下，最好使用现成的关系数据库，例如Python自带的“sqlite3”。然后，构建索引的代码看起来像这样：

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

......你只需要查询，它们会神奇地以最佳方式使用正确的索引：

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