python - 将基数排序(和 python)推向极限

Question

我对网络上的许多 python radix sort 实现感到非常沮丧。

他们始终使用 10 的基数，并通过除以 10 的幂或取数字的 log10 来获得他们迭代的数字的数字。这是非常低效的，因为与位移位相比，log10 并不是一个特别快的操作，位移位快了将近 100 倍!

一个更有效的实现使用基数 256 并逐字节对数字进行排序。这允许使用快得离谱的位运算符完成所有“字节获取”。不幸的是，似乎绝对没有人在 python 中实现了使用位运算符而不是对数的基数排序。

所以，我自己动手并想出了这个野兽，它在小型数组上的运行速度大约是排序的一半，而在较大的数组上运行速度几乎一样快(例如 len around 10,000,000):

import itertools

def radix_sort(unsorted):
    "Fast implementation of radix sort for any size num."
    maximum, minimum = max(unsorted), min(unsorted)

    max_bits = maximum.bit_length()
    highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1

    min_bits = minimum.bit_length()
    lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1

    sorted_list = unsorted
    for offset in xrange(lowest_byte, highest_byte):
        sorted_list = radix_sort_offset(sorted_list, offset)

    return sorted_list

def radix_sort_offset(unsorted, offset):
    "Helper function for radix sort, sorts each offset."
    byte_check = (0xFF << offset*8)

    buckets = [[] for _ in xrange(256)]

    for num in unsorted:
        byte_at_offset = (num & byte_check) >> offset*8
        buckets[byte_at_offset].append(num)

    return list(itertools.chain.from_iterable(buckets))

这个版本的基数排序通过找到它必须排序的字节来工作(如果你只传递小于 256 的整数，它只会排序一个字节，等等)然后通过将每个字节从 LSB 向上排序通过将它们转储到按顺序存储桶，然后将桶链接在一起。对每个需要排序的字节重复此操作，您将在 O(n) 时间内得到排序好的数组。

但是，它并没有想象中的那么快，在我将它写成比现有的所有其他基数排序更好的基数排序之前，我想让它变得更快。

在此运行 cProfile 告诉我很多时间花在列表的 append 方法上，这让我认为这个 block :

    for num in unsorted:
        byte_at_offset = (num & byte_check) >> offset*8
        buckets[byte_at_offset].append(num)

在 radix_sort_offset 中消耗了很多时间。这也是一个 block ，如果你仔细观察它，它会为整个排序完成 90% 的工作。这段代码看起来可能是 numpy 化的，我认为这会带来相当大的性能提升。不幸的是，我不太熟悉 numpy 的更复杂的功能，所以没能弄明白。非常感谢您的帮助。

我目前正在使用 itertools.chain.from_iterable 来展平 buckets，但如果有人有更快的建议，我相信它也会有所帮助。

最初，我有一个返回数字的第 n 字节的 get_byte 函数，但是内联代码给了我巨大的速度提升，所以我做到了。

对于实现或提高性能的方法的任何其他评论也表示赞赏。我想听听你的一切。

Answer 1

你已经意识到了

for num in unsorted:
    byte_at_offset = (num & byte_check) >> offset*8
    buckets[byte_at_offset].append(num)

是大部分时间去的地方 - 很好 ;-)

有两个标准技巧可以加快这种事情的速度，都与将不变量移出循环有关:<​​/p>

1. 在循环外计算“offset*8”。将其存储在局部变量中。每次迭代保存一个乘法。
2. 在循环外添加 bucketappender = [bucket.append for bucket in buckets]。保存每次迭代的方法查找。

将它们结合起来，循环看起来像:

for num in unsorted:
    bucketappender[(num & byte_check) >> ofs8](num)

将其折叠为一个语句还会在每次迭代时保存一对本地 vrbl 存储/获取操作码。

但是，在更高的层次上，加速基数排序的标准方法是使用更大的基数。 256有什么神奇之处？没什么，除此之外它便于移位。但 512、1024、2048 也是如此……这是经典的时间/空间权衡。

PS:对于非常长的数字，

(num >> offset*8) & 0xff

会跑得更快。那是因为您的 num & byte_check 花费的时间与 log(num) 成正比 - 它通常必须创建一个与 num 一样大的整数。