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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 2905 天前的主题，其中的信息可能已经有所发展或是发生改变。

我有两个 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 实在太慢了，不知道有没有更高效的办法

list

字典

key

a_list

15 条回复 • 2016-12-12 14:18:44 +08:00

wwti9

2016-12-10 11:18:38 +08:00

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

alexapollo

2016-12-10 11:31:23 +08:00

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

alexapollo

2016-12-10 11:32:25 +08:00

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

SlipStupig

2016-12-10 13:42:32 +08:00

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

ryd994

2016-12-10 13:50:40 +08:00

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

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

noli

2016-12-10 14:36:44 +08:00 via iPhone

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

noli

2016-12-10 14:42:29 +08:00

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

dikT

2016-12-10 14:46:24 +08:00

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

q397064399

2016-12-10 14:59:17 +08:00

@wwti9 sort 之后二分就好了

q397064399

2016-12-10 15:02:21 +08:00

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

dikT

2016-12-10 15:18:15 +08:00

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

2016-12-11 12:27:02 +08:00 via Android

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

scriptB0y

2016-12-12 09:44:11 +08:00

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

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

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

SlipStupig

2016-12-12 12:38:02 +08:00

@scriptB0y hash 分桶？

scriptB0y

2016-12-12 14:18:44 +08:00

@SlipStupig 是的