列表列表与元组集合的时间复杂度
提问于 2021-04-08 13:30:16
我总是读到集合操作是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
回答 2
Stack Overflow用户
发布于 2021-04-08 13:49:18
您并没有做一个很好的测试来查看哪个元素更快，因为您只在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) Stack Overflow用户
发布于 2021-04-08 13:51:11
好吧，不要紧。事实证明，这是由于列表的构造方式造成的:嵌套列表不是唯一的，因此检查列表是否在列表中基本上是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) 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/67005072
复制
腾讯云开发者
