如何比较多个字典列表中的键值？

Question

我有一个字典的列表，这些字典的结构都是一样的。比如说：

test_data = [{'id':1, 'value':'one'}, {'id':2, 'value':'two'}, {'id':3, 'value':'three'}]

我需要做的是比较这些字典，并根据某个键值对返回“相似”的字典。举个例子，给定键 value 和值 oen，我想找到所有与 oen 相似的字典，在这个例子中，结果会是 [{'id':1, 'value':'one'}]。

difflib 里有一个函数 get_close_matches，这个函数很接近我需要的功能。我可以用 列表推导式 来提取特定键的值，然后把这些值和我的搜索进行比较：

values = [ item['value'] for item in test_data ]
found_vals = get_close_matches('oen', values) #returns ['one']

我希望这个过程再进一步，把所有的内容和原始字典联系起来：

In  [1]: get_close_dicts('oen', test_data, 'value')
Out [1]: [{'id':1, 'value':'one'}]

---

注意：这个字典列表非常大，所以我希望能尽可能高效和快速。

Answer 1

无论如何，你最终都会需要遍历每一个字典，这是无法避免的。不过，你可以在一个预处理阶段把所有的工作做好，这样在真正调用函数的时候就能立刻得到结果。

正如ValAyal提到的，使用一个反向查找字典是个不错的主意。我想象一个字典叫做 value_dict，其中 key 是第一个字典中的值，而 value 则包含了所有完全匹配和相似匹配的值。以 d1 和 d2 为例，它们是在你想要搜索的列表中。如果

d1 = {'id':1, 'value':'one'}
d2 = {'id':3, 'value':'oen'}

那么：

value_dict["one"] = {"exact": [d1], "close": [d2]}
value_dict["oen"] = {"exact": [d2], "close": [d1]}

每当你插入一个已经出现过的值的字典时，你可以立即找到所有的完全匹配和相似匹配（只需查找那个值），然后相应地添加到不同的列表中。如果你有一个新的值是之前没有见过的，你就需要把它和当前 value_dict 中的所有值进行比较。例如，如果你想添加

d3 = {'id':5, 'value':'one'}

你会查找 value_dict["one"]，并得到完全匹配和相似匹配的列表。这些列表包含了你需要修改的所有其他 value_dict 条目。你需要把 one 的完全匹配和 oen 的相似匹配都添加进去；这两个值你可以从返回的列表中获取。最后你得到的是

value_dict["one"] = {"exact": [d1, d3], "close": [d2]}
value_dict["oen"] = {"exact": [d2], "close": [d1, d3]}

所以一旦所有的预处理完成，你的函数就变得简单了：像 get_close_dicts(val) 这样的函数（我不知道你例子中的第三个参数是干嘛的）可以直接执行 return value_dict[val]["exact"] + value_dict[val]["close"]。现在你有了一个能立刻给出答案的函数。

预处理这一步比较复杂，但希望在 get_close_dicts 中带来的速度提升能够弥补这一点。如果你想知道如何实现这个，我可以在下班后详细讲讲。希望这能给你一个有用的数据结构的好主意，我没有想得太复杂。

Answer 2

你可以这样做：

return [d for d in test_data if get_close_matches('oen', [d['value'])]]

要注意，get_close_matches 这个函数可能会返回多个结果。

Answer 3

你可以在运行 get_close_dicts 之前，先创建一个反向查找字典。这样一来，当你得到一组返回值后，就可以用这些值来查找相关的字典。

如果你能保证在字典中 'value' 这个键的值是唯一的，那么你可以这样做：

reverselookup = {thedict['value']:thedict for thedict in test_data}

但是，如果你需要处理多个字典中 'value' 键的值可能相同的情况，那么你需要把所有这些值都映射出来（这样你就会得到一个字典，键是 'value' 中的值，值是包含该值的字典列表）：

from collections import defaultdict
reverselookup = defaultdict(list)
for testdict in test_data:
    reverselookup[testdict['value']].append(testdict)

举个例子，如果你的测试数据中有一个额外的字典，像这样：

>>> test_data = [{'id':1, 'value':'one'}, {'id':2, 'value':'two'}, 
                 {'id':3, 'value':'three'}, {'id':4, 'value':'three'}]

那么上面的反向查找构造会给你这个结果：

{
  "three": [
    {
      "id": 3,
      "value": "three"
    },
    {
      "id": 4,
      "value": "three"
    }
  ],
  "two": [
    {
      "id": 2,
      "value": "two"
    }
  ],
  "one": [
    {
      "id": 1,
      "value": "one"
    }
  ]
}

在你得到这些值之后，只需提取字典（如果你有列表的列表的情况，可以链式调用，如果是第一种情况就不需要链式调用）：

from itertools import chain    
chain(*[reverselookup[val] for val in found_vals])