将Radix Sort(和python)推到极限

Question

我对Web上的许多python radix实现的排序感到非常沮丧.

它们一直使用10的基数,并通过除以10的幂或得到数字的log10来得到它们迭代的数字的数字.这是非常低效的,因为与位移相比,log10不是特别快的操作,这几乎快了100倍!

更高效的实现使用256的基数并逐字节地对数字进行排序.这允许使用可笑的快速位运算符完成所有"字节获取".不幸的是,似乎绝对没有人在python中实现了使用位运算符而不是对数的基数排序.

因此,我亲自动手并想出了这只野兽,它的运行速度大约是小型阵列的一半,并且在大型阵列上的运行速度几乎一样快(例如len大约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列表方法上花了很多时间,这让我觉得这个块:

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

在radix_sort_offset吃很多时间.这也是一个块,如果你真的看它,它可以完成90%的工作.这段代码看起来像是numpy-ized,我认为这会带来相当大的性能提升.不幸的是,我不是很擅长numpy更复杂的功能,所以无法弄明白.非常感谢帮助.

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

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

关于实施的任何其他评论或挤出更多性能的方法也受到赞赏.我想听到你所拥有的一切和一切.

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)

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

但是,在更高的层次上,加速基数排序的标准方法是使用更大的基数.什么是神奇的256？没什么,除了它便于位移.但512,1024,2048也是如此......这是一个经典的时间/空间权衡.

PS:很长的数字,

(num >> offset*8) & 0xff

会运行得更快.那是因为你num & byte_check需要花费时间log(num)- 它通常必须创建一个大约相同的整数num.