基数排序性能不及预期：对比标准排序的优化问询

我在Python中实现了两种基数排序版本（支持排序值上限为n²的整数，n为待排列表大小），用于与标准排序（Timsort）做基准测试，且使用PyPy进行更公平的对比。令人惊讶的是，即使改用直接访问数组而非哈希表的实现，我的基数排序在更大输入规模下仍慢于标准排序。由于O(n)复杂度理论上最终应优于O(nlogn)，我认为存在未掌握的微优化点。出于学习目的，我不寻求内置函数、库或Python调用的C编译代码，希望获得性能优化建议，并确认我的代码是否真的为O(n)复杂度。以下是运行在AMD Ryzen 9 7950X CPU上耗时可达10秒的实现代码：

import matplotlib.pyplot as plt
import random
import time
from collections import defaultdict

def radix_sort(arr, size):
    least_sig_digit = defaultdict(list)
    for num in arr:
        q, r = divmod(num, size)
        least_sig_digit[r].append(q)
    highest_sig_digit = defaultdict(list)
    for k in range(size):  # k goes in order of lowest significant digit
        for q in least_sig_digit[k]:
            highest_sig_digit[q].append(q*size+k)
    i: int = 0
    for k in range(size):
        for num in highest_sig_digit[k]:
            arr[i] = num
            i += 1
    return arr

def radix_sort_no_hashmap(arr, size):
    least_sig_digit = [[] for _ in range(size)]
    for num in arr:
        q, r = divmod(num, size)
        least_sig_digit[r].append(q)
    highest_sig_digit = [[] for _ in range(size)]
    for k in range(size):  # k goes in order of lowest significant digit
        for q in least_sig_digit[k]:
            highest_sig_digit[q].append(q*size+k)
    i: int = 0
    for k in range(size):
        for num in highest_sig_digit[k]:
            arr[i] = num
            i += 1
    return arr


def benchmark_sorting_algorithms():
    sizes = [1000, 10000, 100000, 200000, 1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 10000000]
    radix_times = []
    radix_sort_no_hashmap_times = []
    std_sort_times = []

    for size in sizes:
        array = random.sample(range(1, size**2), size)

        new_arr = array.copy()
        start_time = time.time()
        a = radix_sort(new_arr, size)
        radix_times.append(time.time() - start_time)

        new_arr = array.copy()
        start_time = time.time()
        b = radix_sort_no_hashmap(new_arr, size)
        radix_sort_no_hashmap_times.append(time.time() - start_time)

        new_arr = array.copy()
        start_time = time.time()
        c = sorted(new_arr)
        std_sort_times.append(time.time() - start_time)

        for k in range(len(array)):
            assert a[k] == b[k] == c[k]

    return sizes, radix_times, std_sort_times, radix_sort_no_hashmap_times


sizes, radix_times, std_sort_times, radix_sort_no_hashmap_times = benchmark_sorting_algorithms()

plt.figure(figsize=(12, 6))
plt.plot(sizes, radix_times, label='Radix Sort (O(n))')
plt.plot(sizes, std_sort_times, label='Standard Sort (O(nlogn))')
plt.plot(sizes, radix_sort_no_hashmap_times, label='Radix Sort (O(n)) - No Hashmap')
plt.xlabel('Input size (n)')
plt.xscale('log')
plt.ylabel('Time (seconds)')
plt.yscale('log')
plt.title('Radix Sort vs Standard Sort')
plt.legend()
plt.grid(True)
plt.show()

复杂度确认 #

你的代码确实是**O(n)**复杂度：

• 每个元素被处理3次（分配到LSD桶、分配到MSD桶、写回原数组），每次操作均为O(1)
• 桶遍历的总次数等于元素总数n，不存在额外的O(n)级冗余操作
• 外层range(size)的循环仅用于按顺序访问桶，实际处理的元素总量仍为n

性能优化建议 #

1. 避免重复计算原始数值 #

当前代码中通过q*size + k重新计算原始数值，完全可以在第一次处理时直接存储原始值，减少计算开销：

# 修改radix_sort_no_hashmap的LSD阶段
least_sig_digit = [[] for _ in range(size)]
for num in arr:
    r = num % size  # 仅取余数，不需要商
    least_sig_digit[r].append(num)

后续MSD阶段直接使用存储的原始数值即可，无需反向推导。

2. 替换嵌套列表为计数排序模式 #

嵌套列表的append操作和内存分配开销较高，可改为计数+前缀和定位的方式：

1. 统计每个桶的元素数量
2. 计算前缀和确定每个桶在目标数组中的起始索引
3. 直接将元素写入对应位置，避免多次列表操作

3. 简化运算逻辑 #

• 用num % size替代divmod(num, size)，不需要商时可节省一次整除计算
• 减少循环层级，将桶遍历与元素写回合并为更紧凑的逻辑，降低Python解释器的循环调度开销

4. 优化基准测试环节 #

array.copy()会带来额外内存拷贝开销，可提前生成多份输入副本，或在算法内部复用内存，避免测试环节的时间干扰。

内容的提问来源于stack exchange，提问作者FluidMechanics Potential Flows