python - 根据键的组合比较字典

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 个项目，例如['名称'], ['价格', 'url', '重量']...
• 源列表很长，O(n^2) 算法是不可能的

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 ed在一起，对每个人做同样的事情，然后set.intersection所有结果放在一起。

根据您的数据，仅查找第一个索引，然后线性搜索其他因素的结果可能更有效。您可以通过重新排序字段来进一步优化它，以便搜索具有最小 len(indices[field]) 的字段第一的。 (或者，在这种情况下，sum(len(indices[field]) for field in disj)` 最小的那个。)

如果你可以任意嵌套——…的连词的析取的连词，直到你深入到单个元素——你将只需要函数相互递归地调用另一个(平面元素的基本情况)。您甚至可以将其扩展为完全通用的 bool 搜索(尽管您还需要一个 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)