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

Question

我一直读到集合操作是 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

Answer 1

您没有做一个很好的测试来查看哪个更快，因为您只添加了一个元素，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)  

Answer 2

好的不要紧。事实证明这是由于列表的构造方式：嵌套列表不是唯一的，因此检查列表是否在列表中本质上是 O(1)，因为它始终是第一个列表。做这个轻微的修改让世界上的一切都恢复正常：

a = []
b=[]
m=100
n=100
for i in range(n):
    a.append(list(range(i,i+m)))
    b.append(tuple(range(i,i+m)))
    


p=[]
tic=time.perf_counter()
for i in range(n):
    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(n):
    q.add(b[i])
toc=time.perf_counter()
print(toc-tic) 

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