python - 为什么在 python 中搜索排序列表需要更长的时间？

Question

我做了一个实验，试图找出搜索 Python 列表所需的时间。我有一个包含随机整数的列表 arr。 arr_s 具有仅排序的相同元素。

arr = np.random.randint(low = 0, high = 1000, size = 500)
arr_s = sorted(arr)

现在我创建一个随机整数数组find，其中包含我要在arr 和arr_s 中搜索的元素。

>>> %%timeit
...:find = np.random.randint(0, 1000, 600)
...:for i in find:
...:    if i in arr:
...:        continue

[OUT]:100 loops, best of 3: 2.18 ms per loop


>>> %%timeit
...:find = np.random.randint(0, 1000, 600)
...:for i in find:
...:    if i in arr_s:
...:        continue

[OUT]:100 loops, best of 3: 5.15 ms per loop

现在我明白我没有使用任何特定的方法来搜索排序的数组(例如二进制搜索)。所以它可能会进行标准的线性搜索，但为什么在排序数组中搜索比在未排序数组中搜索要花费更长的时间？我认为应该花费几乎相同的时间。我已经尝试了各种 find 数组。具有 (0, 1000)、(-1000, -100) 和 (-10000, 10000) 整数的数组对于已排序的数组，循环总是需要更长的时间。

Answer 1

arr = np.random.randint(low = 0, high = 1000, size = 500)
arr_s = sorted(arr)

arr 是一个数组。 arr_s 是一个列表。搜索数组可以通过 numpy 高效处理，但搜索列表需要遵循指针并执行类型检查。它与排序无关。

备注:in does weird things in numpy.将 in 与 numpy ndarrays 一起使用可能不是一个好主意。