使用自己的计数排序函数击败内置的timsort

Question

我试图用Python编写一个计数排序，以便在某些情况下击败内置的timsort。现在，它超越了内置的排序函数，但只对非常大的数组(长度为100万个或更长的整数，我还没有尝试过超过1,000万个整数)和范围不超过10,000。此外，胜利是狭窄的，在特定的随机列表中，计数排序仅以很大的优势获胜。

我读过关于从Python代码矢量化中可以获得惊人的性能提高的文章，但我并不特别了解如何在这里使用它或如何使用。我想知道如何将这段代码向量化以加快速度，任何其他性能建议都是受欢迎的。

def countsort(unsorted_list):
    counts = {}
    for num in unsorted_list:
        if num in counts:
            counts[num] += 1
        else:
            counts[num] = 1

    sorted_list = []
    for num in xrange(min(unsorted_list), max(unsorted_list) + 1):
        if num in counts:
            for j in xrange(counts[num]):
                sorted_list.append(num)

    return sorted_list

GitHub

更多信息：

• 所有重要的是原始速度在这里，所以牺牲更多的空间，为速度的增长是完全公平的游戏。
• 我意识到代码已经相当简短和清晰了，所以我不知道有多少空间可以提高速度。
• 如果有人对代码进行了修改，使其更短，只要它不使代码变慢，那也是很棒的。
• 在做了一些更精确的计时之后，很明显，第一个for循环的执行时间约为执行时间的2/3，而第二个构造函数，循环只占用了1/3的时间。

Answer 1

我使用timeit模块和这个测试数据做了一些基准测试：

random.seed(1)
data = [random.randint(0,10000) for _ in xrange(1000000)]

原版时钟为411毫秒，内置sorted为512毫秒。

使用counts = defaultdict(int)允许无条件的counts[num] += 1把它带到330毫秒。

使用sorted_list.extend(counts[num] * [num])，而不是内部循环，改进到250 ms，或当同时省略第二个if时，提高到246个ms。

使用min(counts), max(counts)代替min(unsorted_list), max(unsorted_list)进一步提高到197 ms。

使用chain和来自itertools的repeat来构造结果需要182 ms (尽管repeat没有很大的区别)。

更改后的代码如下所示：

from collections import defaultdict
from itertools import chain, repeat

def countsort(unsorted_list):
    counts = defaultdict(int)
    for num in unsorted_list:
        counts[num] += 1

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

Answer 2

获得小加速比的一种方法是避免测试添加到counts字典中的值是否已经存在。这个代码成语被称为“请求宽恕比请求许可容易”，而且它的速度更快，因为它只做字典上的最小数量的查找。

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

    sorted_list = []
    for num in range(min(unsorted_list), max(unsorted_list) + 1):
        try:
            for j in xrange(counts[num]):
                sorted_list.append(num)
        except KeyError:
            pass

    return sorted_list

我最初认为collections.Counter实例会更快，但是对于我正在对它进行测试的数据来说，速度要慢一些。我认为这可能是因为它使用等效的dict.get来执行增量，如果大多数使用是针对已经存在的值(d[x] += 1比d[x] = d.get(x,0)+1更快)，则增量要慢一些。