为何基于NumPy数组的Bitonic Sort排序算法比Python列表更慢？

我尝试用串行Bitonic Sort排序算法处理数据，为了提升运行速度改用NumPy数组替换Python列表，但实际运行速度反而变慢了。请问问题出在哪里？

排序算法实现 #

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)

Python列表测试代码 #

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)

问题原因分析 #

1. 单元素操作的额外开销 #

NumPy数组的设计目标是批量向量化运算，但单个元素的访问（a[i]）和交换操作（a[i], a[j] = a[j], a[i]）开销远高于Python列表。这是因为NumPy需要为每次单元素操作做类型校验、数组边界检查，以及从底层C数组到Python对象的转换；而Python列表的元素访问是更直接的指针操作，额外开销极少。你的Bitonic Sort算法大量依赖逐元素的比较和交换，这种场景下NumPy的优势完全无法发挥，反而被单元素操作的额外开销拖慢。

2. 未利用NumPy的向量化特性 #

当前代码只是把Python列表换成了NumPy数组，但核心逻辑还是Python层的循环和单元素操作，完全没用到NumPy的核心优势——向量化运算。NumPy的底层C实现只有在处理批量操作时才能体现速度优势，比如用切片、布尔索引完成批量比较和交换，而不是用Python循环逐个处理元素。

3. 函数调用的开销放大 #

compAndSwap函数中对NumPy数组的操作，每次调用都会触发NumPy的内部机制，相比Python列表的同类操作，函数调用的额外开销被进一步放大，累加后导致整体速度变慢。

改进方向 #

• 如果要继续用NumPy优化，必须重写算法逻辑，把Python循环替换成NumPy的向量化操作，比如用切片实现批量的元素比较与交换，减少Python层的循环次数。
• 如果坚持使用串行的逐元素排序逻辑，Python列表在这种场景下的效率反而更高。

内容的提问来源于stack exchange，提问作者Diana