怎么能高效比较两个 list 里面字典的值是否相同呢？

[SlipStupig]

我有两个 list ， list 里面分别有 n 个字典，然后我想得到两个 list 里面 key 相同但是值不同的元素，大致结构如下：

  
       a_list = [{'100024': 100}, {'102234':996}...]
       b_list = [{'100024': 200}, {'102234':996}...]
  

但是这里字典里面的 key 是不固定的，但是两个 list 的所有元素的 key 是相同的（话有点绕，我也不知道怎么表达），当 a_list 的中的 100024 和 b_list 中的 100024 的值得不同的时候如何能快速比较出来呢(两个 list 里面的元素在百万级别左右)，目前我用的 map/cmp 实在太慢了，不知道有没有更高效的办法

[wwti9]

我能想到的就是 sort 两个 list ，再遍历比较。 O(nlgn)

[alexapollo]

一个简单粗暴的思想，
a_key_list ， b_key_list 求交集 C
a_list ， b_list 求差集 D
C ， D 求交集 E
E 即你需要的结果， O(n)

[alexapollo]

另外，为什么要 list 套 map 呢，直接一个大 map 不是好维护多了

[SlipStupig]

@alexapollo 之前设计问题不好变动了

[ryd994]

设计问题没有太好的解， list 这个数据结构决定了这个问题只能 O(n logn)，因为快排是这个效率
而不排序的话更惨，最低不小于 O(n^2)

@wwti9 已知两个 list 有序的情况下，不要从头遍历，从上一个位置继续就行
O(n)

[noli]

如果只是想判断是不是完全一样，那么可以对 list 中的字典内容进行 hash ，比较 hash 值。如果还想知道哪个字典值不一样，那么可以用 merkle tree 的思想

[noli]

忽略我上面的回复吧，感觉我理解错问题了。

[dikT]

很简单,把列表转换成单个字典就行了
然后直接比较

[q397064399]

@wwti9 sort 之后二分就好了

[q397064399]

第一如果是 顺序链表 可以随机访问，很简单 只要 sort 之后 二分就行了
O(nlogn)

[dikT]

a_list = [{'100024': 100}, {'102234': 996}]
b_list = [{'100024': 200}, {'102234': 996}]

a_dict = dict((k, dic[k]) for dic in a_list for k in dic)
b_dict = dict((k, dic[k]) for dic in b_list for k in dic)

common = dict((k, (a_dict[k], b_dict[k])) for k in a_dict if k in b_dict)

print(common) # = {'100024': (100, 200), '102234': (996, 996)}

[meta]

归并排序不是专门干这个的吗

[scriptB0y]

题注你好，我给你一种参考。

将 a 字典进行 hash （ key ）%100 ，这里看你数据大小，如果数据没那么大，也可以 hash （ 30 ），得到 100 种不同的 key ，分别存入 100 个文件（标记为 a001 ， a002...a100 ，如果不是特别大，也可以直接在内存中用）。用相同的方法处理文件 b 。

这样之后，只有 a001 和 b001 两个文件存在 key 相同的元素，然后遍历起来可能快一些（相比于将 a 中一个 key 去和 b 中所有 key 遍历，我们每次只遍历了 1/100 ）。分成的文件越多，遍历速度越快。

[SlipStupig]

@scriptB0y hash 分桶？

[scriptB0y]

@SlipStupig 是的