为什么numpy arrayw的排序算法比列表慢?

dxpyg8gm  于 2023-04-21  发布在  其他
关注(0)|答案(1)|浏览(127)

我尝试用顺序双调排序对列表进行排序,并希望通过对numpy数组而不是列表进行排序来使其更快,但它只会变得更慢。我做错了什么?
以下是排序算法:

from datetime import datetime
import numpy as np

def compAndSwap(a, i, j, dire):
    if (dire == 1 and a[i] > a[j]) or (dire == 0 and a[i] < a[j]):
        a[i], a[j] = a[j], a[i]

def bitonicMerge(a, low, cnt, dire):
    if cnt > 1:
        k = cnt // 2
        for i in range(low, low + k):
            compAndSwap(a, i, i + k, dire)
        bitonicMerge(a, low, k, dire)
        bitonicMerge(a, low + k, k, dire)

def bitonicSort(a, low, cnt, dire):
    if cnt > 1:
        k = cnt // 2
        bitonicSort(a, low, k, 1)
        bitonicSort(a, low + k, k, 0)
        bitonicMerge(a, low, cnt, dire)

def sort_(a, N, up):
    bitonicSort(a, 0, N, up)

这里是运行这个算法的一部分:

with open('data.txt') as f:
    
    line = f.readline()
    a = line[1:-2].split(', ')
    a = list(map(int, a))

n = len(a)

up = 1

time1 = datetime.now()

sort_(a, n, up)

time2 = datetime.now()

print("\nCurrent Time =", time2-time1)

下面是numpy数组:

with open('data.txt') as f:
    line = f.readline()
    a = np.array(line[1:-2].split(', ')).astype('int32')

n = a.size
up = 1

time1 = datetime.now()

sort_(a, n, up)

time2 = datetime.now()

print("\nCurrent Time =", time2-time1)

我错过了什么?

kyxcudwk

kyxcudwk1#

你搞错了numpy。Numpy实际上是一个科学计算包,最适合执行向量化操作,例如数组乘法。它并没有针对一次访问数组中的单个项进行优化。
如果你尝试这个简单的测试:

data = np.random.randint(0, 10000, 1000000)
a = data.tolist()

然后测量一个简单的循环所花费的时间,而不需要任何额外的操作。

%timeit for i in range(data.shape[0]): _ = data[i] # 145 ms ± 50.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

对列表执行相同的操作:

%timeit for i in range(len(a)): _ = a[i] # 85.1 ms ± 28.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

您会发现访问numpy数组中的项需要花费更多的时间。
然而,利用numpy库中预先优化的函数可能会导致性能上的显著差异。

%timeit np.sort(data, kind='mergesort') # 100 ms ± 11.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

如果你在列表中使用sorted

%timeit sorted(a) # 449 ms ± 69.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

这种比较并不准确,因为sorted使用了timsort,它是mergesort的修改版本。尽管如此,性能上的差异仍然很大。

相关问题