将基数排序（和Python）推向极限

Question

我对网上许多Python基数排序的实现非常失望。它们一贯使用基数10，并通过除以10的幂或取数字的log10来得到迭代数字的各个位数。这样做效率极低，因为与快速的位移相比，log10操作要慢近100倍！

一个更为高效的实现方法是使用基数256，并逐字节对数字进行排序。这使得所有“获取字节”的工作都可以使用快速的位运算符来完成。不幸的是，似乎没有人在Python中实现了一种基数排序，它使用位运算符而不是对数。

所以，我自己动手并想出了这个“野兽”，它在小数组上的运行速度大约是有序数组的一半，并且在较大的数组上（例如len约为10,000,000）几乎与sorted的速度相当：

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)时间内得到排序后的数组。

但是，它不如可能快，并且在将其写成比其他所有基数排序更好的基数排序之前，我想使它更快。

对此运行告诉我，很多时间都花在了列表的方法上，这让我认为这个块：

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

radix_sort_offset占用了很多时间，如果你真正去看它，它完成了整个排序90%的工作。这段代码看起来可以使用numpy来提高性能。不幸的是，我不太熟悉numpy的更复杂的功能，所以无法找出解决方法。非常感谢您的帮助。

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

最初，我有一个get_byte函数，它返回一个数字的第n个字节，但将代码内联使我获得了巨大的速度提升，所以我做了这个操作。

关于实现或者挤出更多性能的方式，任何其他评论也都会受到欢迎。我想听听您拥有的所有东西。

- reem

Answer 1

你已经意识到了

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

大部分时间都花在这里 - 很好 ;-)

加快这种类型的操作有两个标准技巧，都涉及将不变量移出循环：

1. 在循环外计算“offset * 8”，并将其存储在本地变量中。每次迭代节省一次乘法。
2. 在循环外添加 bucketappender = [bucket.append for bucket in buckets]。每次迭代节省一次方法查找。

结合使用它们，循环看起来像：

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

将其折叠成一个语句还可以每次迭代节省一对本地变量存储/获取操作码。

但是，从更高的层面上看，加速基数排序的标准方法是使用更大的基数。256有什么神奇之处吗？除了它方便进行位移操作外，没有任何特别之处。但是512、1024、2048等也是如此，这是一个经典的时间/空间权衡。

附：对于非常长的数字，

(num >> offset*8) & 0xff

会运行得更快。这是因为你的 num & byte_check 的时间与 log(num) 成比例 - 它通常需要创建一个大约和 num 一样大的整数。

- Tim Peters

---

好东西。这导致了相当强的加速，并使得这个基数排序在具有4096个基数的长度为10,000,000的列表上击败了排序，尽管这使它在短列表上表现出令人尴尬的差劲。编辑：刚刚意识到你是写timsort的那个人。向您致敬。 - reem

嘿 - 我打赌你的列表里没有任何负整数;-) 基数排序很棒，但是当你超出非负整数时，位操作会变得更加棘手。顺便说一句，我写了Python的list.sort()，而且我并不介意你的排序更快 :-) - Tim Peters

Answer 2

这是一个旧的帖子，但当我想要对正整数数组进行基数排序时，我遇到了这个问题。我试图看看是否可以比已经非常快的timsort（再次向您致敬，Tim Peters）实现Python的内置sorted和sort更好！无论如何，我不理解上面代码的某些方面，或者如果我理解了，那么上面呈现的代码在我看来存在一些问题。

1. It only sorts bytes starting with the highest byte of the smallest item and ending with the highest byte of the biggest item. This may be okay in some cases of special data. But in general the approach fails to differentiate items which differ on account of the lower bits. For example:

   arr=[65535,65534]
   radix_sort(arr)
   

   produces the wrong output:

   [65535, 65534]
   

2. The range used to loop over the helper function is not correct. What I mean is that if lowest_byte and highest_byte are the same, execution of the helper function is altogether skipped. BTW I had to change xrange to range in 2 places.

3. With modifications to address the above 2 points, I got it to work. But it is taking 10-20 times the time of python's builtin sorted or sort! I know timsort is very efficient and takes advantage of already sorted runs in the data. But I was trying to see if I can use the prior knowledge that my data is all positive integers to some advantage in my sorting. Why is the radix sort doing so badly compared to timsort? The array sizes I was using are in the order of 80K items. Is it because the timsort implementation in addition to its algorithmic efficiency has also other efficiencies stemming from possible use of low level libraries? Or am I missing something entirely? The modified code I used is below:

   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
   #    xrange changed to range, lowest_byte deleted from the arguments
       for offset in range(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)
   
   #    xrange changed to range
       buckets = [[] for _ in range(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))
   

- Thomas

Answer 3

您可以简单地使用现有的C或C++实现之一，例如Boost.Sort中的integer_sort或usort中的u4_sort。从Python调用本机C或C++代码非常容易，请参见如何比快速排序更快地对整数数组进行排序？

我完全理解您的挫败感。尽管已经过去两年多了，numpy仍然没有基数排序。我会让NumPy开发人员知道他们可以简单地获取其中一个现有的实现；许可证不应该是问题。

- Ali