为什么在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有效地处理,但搜索列表需要跟随指针并执行类型检查.它与排序无关.

注意:innumpy中的怪异事物.使用innumpy ndarray可能是一个坏主意.