Python中的快速数据比较

Question

我想比较一大堆数据，这些数据是以两个长度不一的字典的形式存在的。

post = {0: [0.96180319786071777, 0.37529754638671875], 
        10: [0.20612385869026184, 0.17849941551685333],
        20: [0.20612400770187378, 0.17510984838008881],...}

pre = {0: [0.96180319786071777, 0.37529754638671875],
       1: [0.20612385869026184, 0.17849941551685333],
       2: [0.20612400770187378, 0.17510984838008881],
       5065: [0.80861318111419678, 0.76381617784500122],...}

我们需要得到的结果是5065: [0.80861318111419678, 0.76381617784500122]。这个结果是基于我们只比较值，而完全不考虑索引。

我使用这个键值对只是为了记住数据的顺序。如果需要的话，数据类型可以换成列表或集合。我需要找出那些在字典中不共有的元素的键值对（索引和值）。

我用的代码非常简单……

new = {}
found = []

for i in range(0, len(post)): 
    found= []
    for j in range(0, len(pre)): 
        if post[i] not in pre.values():
            if post[i] not in new:
                new[i] = post[i]
                found.append(j)             
                break
    if found:
        for f in found: pre.pop(f)

new{}里包含了我需要的元素。

我遇到的问题是这个过程太慢了。有时候处理一个小时都不够。数据量有时还会更大。我希望能让它更快。

有没有什么有效的方法可以实现我想要的？我希望除了Python 2.5（64位）自带的包外，不依赖其他外部包，除非真的必要。

谢谢大家。

Answer 1

你的问题可能出在嵌套的 for 循环和使用 range() 上。每次使用 range() 都会创建一个新的 list，这可能会比较慢。你可以尝试直接遍历 pre 和 post，这样可以自动提高一些速度，避免嵌套的方式。

post = {0: [0.96180319786071777, 0.37529754638671875],
       10: [0.20612385869026184, 0.17849941551685333],
       20: [0.20612400770187378, 0.17510984838008881]}

pre = {0: [0.96180319786071777, 0.37529754638671875],
       1: [0.20612385869026184, 0.17849941551685333],
       2: [0.20612400770187378, 0.17510984838008881],
    5065: [0.80861318111419678, 0.76381617784500122]}

'''Create sets of values, independent of dict key for O(1) lookup'''
post_set=set(map(tuple, post.values()))
pre_set=set(map(tuple, pre.values()))

'''Iterate through each structure only once, filtering items that are found in
   the sets we created earlier, updating new_diff'''
from itertools import ifilterfalse

new_diff=dict(ifilterfalse(lambda x: tuple(x[1]) in pre_set, post.items()))
new_diff.update(ifilterfalse(lambda x: tuple(x[1]) in post_set, pre.items()))

new_diff 现在是一个 dict，它的每个值在 post 和 pre 中都找不到，同时保留了原来的索引。

>>> print new_diff
{5065: [0.80861318111419678, 0.76381617784500122]}

Answer 2

这基本上就是set（集合）设计的目的（计算一组物品之间的差异）。唯一需要注意的是，你放进set里的东西必须是可哈希的，而list（列表）就不是。不过，tuple（元组）是可以的，所以如果你把列表转换成元组，就可以把它们放进集合里：

post_set = set(tuple(x) for x in post.itervalues())
pre_set = set(tuple(x) for x in pre.itervalues())

items_in_only_one_set = post_set ^ pre_set

想了解更多关于set的信息，可以查看这个链接：http://docs.python.org/library/stdtypes.html#set

在你计算出差异后，如果想要得到原来的索引，你可能需要生成反向查找表：

post_indices = dict((tuple(v),k) for k,v in post.iteritems())
pre_indices = dict((tuple(v),k) for k,v in pre.iteritems())

然后你可以通过字典来查找给定元组的索引：

index = post_indices.get(a_tuple, pre_indices.get(a_tuple))