时间戳

首页 > 解决方案 > 列表列表与元组集的时间复杂度

python - 列表列表与元组集的时间复杂度

问题描述

我一直读到集合操作是 O(1)，最坏的情况是 O(N)，而检查列表成员资格是 O(N)。所以当一个朋友在添加列表之前检查一个列表是否在列表中时，我建议使用一组元组来代替。但是，在对它们计时，列表列表更快！为什么是这样？将元组添加到集合中如何比迭代列表列表慢？

这是一些示例测试代码

import time
a = []
b = []

for i in range(10000):
    a.append(list(range(100)))
    b.append(tuple(range(100)))
    


p=[]
tic=time.perf_counter()
for i in range(100):
    if a[i] not in p:
        p.append(a[i])
toc=time.perf_counter()
print(toc-tic)  # Was about 100ms

q=set()
tic=time.perf_counter()
for i in range(100):
    q.add(b[i])
toc=time.perf_counter()
print(toc-tic)  # Was about 169ms

r=dict()
tic=time.perf_counter()
for i in range(100):
    r[b[i]]=None
toc=time.perf_counter()
print(toc-tic)  # Was about 143ms

标签： pythonlistsetbig-ohashtable

解决方案

您没有做一个很好的测试来查看哪个更快，因为您只添加了一个元素，p,q,r因为a它仅由一个重复的元素组成：list(range(100))，对于b.

一个更好的测试是这个修改后的版本，你会看到你所期望的，因为你在这里添加了不同的元素a和b：

import time
a = []
b = []

for i in range(100000):
    a.append(i)
    b.append(i)
           
p=[]
tic=time.perf_counter()
for i in range(100):
    if a[i] not in p:
        p.append(a[i])
toc=time.perf_counter()
print(toc-tic)  

q=set()
tic=time.perf_counter()
for i in range(100):
    q.add(b[i])
toc=time.perf_counter()
print(toc-tic)  

r=dict()
tic=time.perf_counter()
for i in range(100):
    r[b[i]]=None
toc=time.perf_counter()
print(toc-tic)

推荐阅读