python - 为什么 "counting sort"不是更广泛使用的算法？

Question

我正在绘制一些大型学术文档中的字母频率。作为这个过程的一部分，是将这些文件的大量剪报中的字母按字母顺序排序。我使用的是 Python 的 内置的 sorted 函数，我开始怀疑是否可以让它更快。然后我写了以下函数:

  def count_sort(l):
        items = {'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,'l':0,'m':
 0,'n':0,'o':0,'p':0,'q':0,'r':0,'s':0,'t':0,'u':0,'v':0,'w':0,'x':0,'y':0,'z'
:0}
        for item in l:
            items[item] += 1
        sort_l = []
        for key in items:
            sort_l += key*items[key]
        return sort_l

当在 10000 字母长的文本字符串上测试此代码与 sorted 时，它几乎快 20X。

有了这样的性能提升，为什么标准 libs 中没有这种排序算法？

Answer 1

您重新发现了 counting sort算法。

引用维基百科:

For problem instances in which the maximum key value is significantly smaller than the number of items, counting sort can be highly space-efficient, as the only storage it uses other than its input and output arrays is the Count array which uses space O(k).

计数排序算法变得越来越(相对)高效正在排序。

你可以明白为什么这必须看你自己的代码，或者 Wikipedia example code :

# calculate the histogram of key frequencies:
for x in input:
    count[key(x)] += 1

# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount

# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1

return output

您的函数中有 2 个 for 循环:第一个循环遍历您正在排序的字母，第二个循环遍历 items 字典。正如我之前提出的那样，这使得项目字典比您正在排序的列表小得多，但如果唯一元素的数量相对于正在排序的项目数量增加，它很快就会变得非常低效。

就像@BrenBarn 回答的那样，这只有在您确切知道期望的字符并且您愿意忽略任何其他字符时才会这样做。虽然在您给出的示例中计数排序似乎非常有效，但字母排序问题几乎不是最常见的排序问题。

下面我修复了你的函数，通过遍历列表而不是遍历字典中的键来打印字母(因为 Python 的字典没有排序)

def count_sort(l):
    letters = [chr(i) for i in range(97, 122)]
    items = dict()
    for letter in letters:
        items[letter] = 0
    for item in l:
        items[item] += 1
    sort_l = list()
    for letter in letters:
        sort_l.extend(letter*items[letter])
    return sort_l