6

我做了一个实验，试图找出搜索 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) 整数的数组，对于已排序的数组，循环总是需要更长的时间。

4

3 回答 3

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

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

注意：in在 numpy. 与 numpy ndarrays 一起使用in可能是个坏主意。

于 2013-09-05T18:53:23.570 回答
0

我没有确切的答案，但可能的起点是检查每个对象使用的迭代器。



    In [9]: it = arr.__iter__()
    In [10]: its = arr_s.__iter__()
    In [11]: type(it)
    Out[11]: iterator
    In [12]: type(its)
    Out[12]: listiterator

他们显然使用了两种不同的迭代器，可以解释速度的差异。

于 2013-09-05T19:17:14.970 回答
0

Python 列表不像 C 数组。它们不仅仅是一个简单的内存块，其中元素 1 总是在元素 0 之后，依此类推。相反，Python 以一种灵活的方式存储内容，以便您可以添加和删除任意类型的元素并随意移动内容。

在这种情况下，我的猜测是对列表进行排序的行为会改变底层组织，从而降低访问元素的效率。

于 2013-09-05T18:51:25.347 回答