8

如果我有两个列表，每个列表长 800 个元素并用整数填充。有没有比使用内置运算符更快的方法来比较它们具有完全相同的元素（如果没有则短路）==？

a = [6,2,3,88,54,-486]
b = [6,2,3,88,54,-486]
a == b 
>>> True

还有什么比这更好的吗？

我很好奇只是因为我有一个巨大的列表来比较。

4

7 回答 7

11

我们不要假设，而是运行一些测试！

设置：

>>> import time
>>> def timeit(l1, l2, n):
        start = time.time()
        for i in xrange(n):
                l1 == l2
        end = time.time()
        print "%d took %.2fs" % (n, end - start)

两个巨大的平等名单： 

>>> hugeequal1 = [10]*30000
>>> hugeequal2 = [10]*30000
>>> timeit(hugeequal1, hugeequal2, 10000)
10000 took 3.07s

第一个元素不相等的两个巨型列表：

>>> easydiff1 = [10]*30000
>>> easydiff2 = [10]*30000
>>> easydiff2[0] = 0
>>> timeit(easydiff1, easydiff2, 10000)
10000 took 0.00s
>>> timeit(easydiff1, easydiff2, 1000000)
1000000 took 0.14s

所以看起来内置的列表相等运算符确实做了短路。

编辑：有趣的是，使用该array.array模块并没有使它更快：

>>> import array
>>> timeit(hugeequal1, hugeequal2, 1000)
1000 took 0.30s
>>> timeit(array.array('l', hugeequal1), array.array('l', hugeequal2), 1000)
1000 took 1.11s

numpy但是，确实可以使您获得很好的加速：

>>> import numpy
>>> timeit(hugeequal1, hugeequal2, 10000)
10000 took 3.01s
>>> timeit(numpy.array(hugeequal1), numpy.array(hugeequal2), 10000)
10000 took 1.11s
于 2013-08-23T20:00:54.283 回答
4

Numpy可以将其加速 10 倍，并且特别相关，因为您的列表是修复（整数）类型。

在纯python中，每次比较都必须遵循对下一个元素的引用，检查类型等。在numpy中，只需要增加一个指针。

这是一个比较：

import numpy as np
from timeit import timeit

N = 10**7

p0 = list(range(N))
p1 = list(range(N))

n0 = np.arange(N)
n1 = np.arange(N)

number = 500
t = timeit("p0==p1", setup="from __main__ import p0, p1", number=number)
print "pure python time =", t/number

number = 500
t = timeit("(n0==n1).all()", setup="from __main__ import n0, n1", number=number)
print "numpy time =", t/number

结果是使用 numpy 快 10 倍：

pure python time = 0.256077399254
numpy time = 0.0286148643494
于 2013-08-23T20:00:18.977 回答
3

CPython 的内置功能（我假设您正在使用）往往是用 C 编写的。因此，除非您编写一些利用上下文某些方面的 C/C++ 代码，否则您不会比这更快。

于 2013-08-23T19:56:59.380 回答
3

另一种选择是使用pypy：

$ python -mtimeit -s 'a=[10]*30000;b=[10]*30000;print(a==b)'
100000000 loops, best of 3: 0.0104 usec per loop

$ pypy -mtimeit -s 'a=[10]*30000;b=[10]*30000;print(a==b)'
1000000000 loops, best of 3: 0.00102 usec per loop

而且，pypy 对这个输入的执行速度提高了 10 倍。

于 2013-08-23T20:09:44.420 回答
2

不，如果两个列表更快，则无法进行比较。但是你说你有一个巨大的列表。听起来你问错了问题。如果我们假设您想要在列表列表中找到相同的列表，那么是的，有一种更快的方法可以做到这一点：

>>> list_of_lists = [[1,2,3,4,5,6,7], [1,3,3,4,5,6,7], [1,2,3,4,5,6,6], [1,2,3,4,5,6,7]]
>>> list_of_hashes = [hash(tuple(x)) for x in list_of_lists]
>>> list_of_hashes
[1738718158840515323, -9068250430673137562, 1738718158842010488, 1738718158840515323]

正如您在此处看到的，我对每个列表进行哈希处理（我必须先将它们变成元组，因为列表不可哈希处理）。然后比较是微不足道的，因为您现在只有一个整数列表而不是列表列表。如果您不关心列表中项目的顺序，请hash(set(x))改用。

>>> list_of_hashes[0] == list_of_hashes[1]
False
>>> list_of_hashes[0] == list_of_hashes[2]
False
>>> list_of_hashes[0] == list_of_hashes[3]
True

如果您有许多长列表并且您将所有列表与所有其他列表进行比较，这会更快。

于 2013-08-23T20:13:22.933 回答
1

不可能。知道两个项目是否相等的唯一方法是比较它们，并且您必须比较所有对以知道它们是否相等。

也就是说，无论如何你都可以得到加速。如果您正确使用 NumPy ndarrays，NumPy 不仅可以加快您的比较速度，还可以加快您对数据所做的几乎所有其他事情。或者，如果您可以使用一些外部信息，或者一对列表是否比较相等与另一对是否相等之间存在某种关系，您可以利用该信息来避免一些比较工作。

于 2013-08-23T20:01:19.590 回答
0

根据您的用例，您可以切换到使用元组（不可变），并将列表放在一组中。

您的另一个选择是在建立列表时跟踪相似性（或不跟踪）。

于 2013-08-23T20:12:42.543 回答