在Python中比较列表中元素的最快方法

9 浏览
0 Comments

在Python中比较列表中元素的最快方法

这个问题已经有了答案: 如何在Python中计算程序运行时间? [重复]

我很好奇在确定两个列表中是否有非相似元素时，哪种实现方式会更快。在这里，两个列表的长度将相同，并且只有一个元素不相同。

实现方式＃1：

lista = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
listb = ['a', 'b', 'c', 'd', 'e', 'f', 'gslfkjsjf']
difference = list(set(lista) - set(listb))
>>> ['g']

实现方式＃2：

lista = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
listb = ['a', 'b', 'c', 'd', 'e', 'f', 'gslfkjsjf']
for i in range(len(lista)):
    if (lista[i] != listb[i]):
        print(lista[i])
>>> g

我对知道答案很感兴趣，因为我正在尝试找到比较两个相同长度的列表的最快方法（大约2000个左右，每个元素都是一个唯一的字符串。我只是为了举例而使用了字符）。 在此提前感谢所有回复的人。

admin 更改状态以发布 2023年5月24日
0

2 答案

0 Comments

根据此处的文档https://wiki.python.org/moin/TimeComplexity，最佳情况下s-t的集合差需要O(len(s))。可以看看https://stackoverflow.com/a/48044412/3236440。

因此，你的Implementation #1的时间复杂度为O(len(lista))，而你的Implementation #2由于会运行lista的所有元素，所以同样需要O(len(lista))。

对于2000个元素而言，它们可以轻松地适合主存。此外，你提到每个元素都是唯一的，因此在集合散列上不会出现冲突。

这里的另一个关键点是，你始终选择较小集合的集合差，因为它将需要更少的运行时间。

0
0 Comments

以下是如何从live ipython3 repl中进行测量的方法

from timeit import timeit  # import timeit
# declare the lists
lista = ['a', 'b', 'c', 'd', 'e', 'f', 'g']        
listb = ['a', 'b', 'c', 'd', 'e', 'f', 'gslfkjsjf']
# measure
timeit('difference = list(set(lista) - set(listb))', globals=globals())
timeit('''for i in range(len(lista)):         
    if (lista[i] != listb[i]):                
        print(lista[i])''', globals=globals())

这里的结果为循环为4.551160663000701，集合为0.851781547000428。记住，timeit默认情况下运行1000000次。

现在为什么集合要快得多呢？集合使用哈希算法而不是索引。这意味着集合的查找更快，因为它不需要被迭代来查找值。此外，for循环中还有一个print、一个range和一个比较，它不仅速度较慢，而且要做更多的事情。

0