python - 我怎样才能向量化这个 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 shot 做到这一点的绝对最快的方法是使用这个带有 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从计数转换为排序数组。