尝试计算“in”运算符的时间

Question

所以我有一个关于 in 运算符内部如何工作的问题。因此，为了测试它，我尝试绘制在列表的不同部分中查找列表成员所需的时间。

import time
import matplotlib.pyplot as plt

# list size
size = 100000
# number of points
n = 100000

# display for not having to count zeros
if size >= 1000000:
    new_size = str(int(size/1000000))+"M"
else:
    new_size = str(int(size/1000))+"K"

if n >= 1000000:
    new_n = str(int(n/10000000))+"M"
elif n >= 1000:
    new_n = str(int(n/1000))+"K"
else:
    new_n = n

lst = list(range(size))
result = []
for number in range(0,size+1,int(size/n)):
    start_time = time.time_ns()
    if number in lst:
        end_time = time.time_ns()
        total_time = (end_time-start_time)/1000000000 #convert ns to seconds
        result.append([total_time,number])
        print(number,total_time)

x_values, y_values = zip(*result)
plt.scatter(x_values, y_values, c='red', marker='o',s=5)
plt.xlabel('Time (sec)')
plt.ylabel('Number')
plt.title(f'List length: {new_size}\nNumber of points: {new_n}\n\nTime to find number in list')
plt.grid(True)
plt.show()

据我所知，在内部通过调用 https://docs.python.org/3/reference/datamodel.html#object.iter 来工作，它从第一的。所以我预计在列表中进一步搜索会花费越来越多的时间。
该列表必须超过一定的长度，以便Python需要足够长的时间来找到我们可以测量的数字，但是摆弄不同的列表大小和点的数量我发现这些点聚集在垂直线的倍数上0.001s，这对我来说很奇怪。由于 python 内部的工作方式，我可以看到一些水平线形成，但不是垂直线。我什至使用 time.time_ns() 来获得更高的时间精度，但它仍然会发生。
我的意思是，如果总是从 0 开始，那么在 [0,1, ... 100000] 列表中如何花费相同的时间找到 539 和 94,598？

请自行尝试代码。
我希望我没有搞砸一些明显的事情。

Answer 1

这似乎表明，根据项目在列表中的位置，搜索数字是一个列表需要越来越长的时间。

import timeit

setup = """
def is_in(data, target):
    return target in data

size = 1_000_000
size_minus_one = size - 1
data = list(range(size))
"""

print(timeit.timeit("is_in(data, 0)", setup=setup, number=1_000))
print(timeit.timeit("is_in(data, size_minus_one)", setup=setup, number=1_000))

搜索一组每个数字所需的时间大约相同：

import timeit

setup = """
def is_in(data, target):
    return target in data

size = 1_000_000
size_minus_one = size - 1
data = set(range(size))
"""

print(timeit.timeit("is_in(data, 0)", setup=setup, number=1_000))
print(timeit.timeit("is_in(data, size_minus_one)", setup=setup, number=1_000))