在python中排序小写字母

Question

我试图说服自己，计数排序比Python中的排序方法执行得更快。然而，调用排序的内置函数似乎更快，即使对于像1000万个元素这样的大型输入也是如此。我能做些什么来加快计数排序？你知道吗

我生成一个小写字母列表，将示例简化为26个唯一值：

letters = [random.choice(string.ascii_lowercase) for i in range(10000000)]

然后我对计数排序执行以下操作：

def sorted_count(letters):
 counts = [0] * 26
 for letter in letters:
     counts[ord(letter) - 97] += 1
 out = [None] * len(letters)
 j = 0
 for i in range(len(counts)):
     while counts[i] > 0:
         out[j] = chr(i + 97)
         counts[i] -= 1
         j += 1
 return out

即使在10000000个元素上，对sorted(letters)的调用也要快4倍。 我怎样才能提高我那类人的速度？你知道吗

Answer 1

而不是在最后的forloop中使用while循环。 你可以简单的使用

for i in range(len(counts)):
 if counts[i]>0:
     out[j] =counts[i]*chr(i + 97)
 j+=1
return out

Answer 2

下面是一个修改后的函数，它比建议的函数快3倍，比sorted快两倍：

import random
import string
import timeit
N = 1000000
letters = [random.choice(string.ascii_lowercase) for i in range(N)]


def original_sorted_count(letters):
    counts = [0] * 26
    for letter in letters:
        counts[ord(letter) - 97] += 1
    out = [None] * len(letters)
    j = 0
    for i in range(len(counts)):
        while counts[i] > 0:
            out[j] = chr(i + 97)
            counts[i] -= 1
            j += 1
    return out

def eric(letters):
    counts = [0] * 26
    for letter in letters:
        counts[ord(letter) - 97] += 1
    out = []
    for i in range(len(counts)):
        out += [chr(i+97)] * counts[i]
    return out

print('Original : %.3fs' %timeit.timeit(lambda: original_sorted_count(letters), number=20))
print('Sorted   : %.3fs' %timeit.timeit(lambda: sorted(letters), number=20))
print('Eric     : %.3fs' %timeit.timeit(lambda: eric(letters), number=20))

print(eric(letters) == sorted(letters))

它输出：

Original : 9.616s
Sorted   : 6.367s
Eric     : 3.604s
True