我怎样才能对这个python计数排序进行矢量化,以便它尽可能快？

Question

我试图在python中编写一个计数排序,以在某些情况下击败内置的timsort.现在它击败了内置的排序函数,但仅适用于非常大的数组(长度为100万个整数,更长,我没有尝试超过1000万个),并且仅适用于不大于10,000的范围.此外,胜利是狭隘的,计数排序仅在专门为其量身定制的随机列表中获得了显着的优势.

我已经读过可以通过矢量化python代码获得惊人的性能提升,但我不是特别了解如何做到这一点或如何在这里使用它.我想知道如何对此代码进行矢量化以加快速度,并欢迎任何其他性能建议.

目前python和stdlibs的最快版本:

from itertools import chain, repeat

def untimed_countsort(unsorted_list):
    counts = {}
    for num in unsorted_list:
        try:
            counts[num] += 1
        except KeyError:
            counts[num] = 1

    sorted_list = list(
        chain.from_iterable(
            repeat(num, counts[num])
            for num in xrange(min(counts), max(counts) + 1)))
    return sorted_list

• 重要的是这里的原始速度,因此为速度增益牺牲更多空间是完全公平的游戏.

• 我已经意识到代码已经相当简短和清晰,所以我不知道有多少空间可以提高速度.

• 如果有人对代码进行了更改以使其更短,只要它不会使它变慢,那也是很棒的.

• 执行时间下降了近80%!在我目前的测试中,现在是Timsort的三倍!

通过LONG镜头执行此操作的绝对最快的方法是使用这个带有numpy的单线程:

def np_sort(unsorted_np_array):
    return numpy.repeat(numpy.arange(1+unsorted_np_array.max()), numpy.bincount(unsorted_np_array))

这比纯python版快了大约10-15倍,比Timsort快大约40倍.它需要一个numpy数组并输出一个numpy数组.

Answer 1

使用numpy,此功能简化为以下内容:

def countsort(unsorted):
    unsorted = numpy.asarray(unsorted)
    return numpy.repeat(numpy.arange(1+unsorted.max()), numpy.bincount(unsorted))

当我从区间[0,10000)以100000随机整数尝试它时,这个速度快了大约40倍.bincount进行计数,并repeat从计数转换为排序数组.