python - 如果不关心语言环境，在 Python 中对字符串进行排序的最快方法是什么？

Question

我试图找到一种在 Python 中对字符串进行排序的快速方法，并且语言环境不是问题，即我只想根据底层字节对数组进行词法排序。这非常适合基数排序之类的东西。这是我的 MWE

import numpy as np
import timeit

# randChar is workaround for MemoryError in mtrand.RandomState.choice
# http://stackoverflow.com/questions/25627161/how-to-solve-memory-error-in-mtrand-randomstate-choice
def randChar(f, numGrp, N) :
   things = [f%x for x in range(numGrp)]
   return [things[x] for x in np.random.choice(numGrp, N)]

N=int(1e7)
K=100
id3 = randChar("id%010d", N//K, N)   # small groups (char)
timeit.Timer("id3.sort()" ,"from __main__ import id3").timeit(1) # 6.8 seconds

如您所见，它花费了 6.8 秒，几乎比下面 R 的基数排序慢 10 倍。

N = 1e7
K = 100
id3 = sample(sprintf("id%010d",1:(N/K)), N, TRUE)
system.time(sort(id3,method="radix"))

我知道 Python 的 .sort()不使用基数排序，是否有某种实现可以让我像 R 一样高效地对字符串进行排序？

AFAIK R 和 Python 都是“实习生”字符串，因此 R 中的任何优化也可以在 Python 中完成。

“基数排序字符串python”的顶级谷歌结果是this gist在对我的测试数组进行排序时产生错误。

Answer 1

确实，R 实习了所有字符串，这意味着它有一个“全局字符缓存”，作为程序使用过的所有字符串的中央字典。这有它的优点:数据占用更少的内存，某些算法(如基数排序)可以利用这种结构来实现更高的速度。对于诸如您的示例中的场景尤其如此，其中唯一字符串的数量相对于向量的大小较小。另一方面，它也有它的缺点:全局字符缓存阻止了对字符数据的多线程写访问。

在 Python 中，afaik，只有字符串文字被实习。例如:

 >>> 'abc' is 'abc'
 True
 >>> x = 'ab'
 >>> (x + 'c') is 'abc'
 False

实际上，这意味着，除非您将数据直接嵌入到程序的文本中，否则不会有任何内容。

现在，对于您最初的问题:“在 python 中对字符串进行排序的最快方法是什么”？你可以达到非常好的速度，与 R 相当，使用 python datatable包裹。这是对 N = 10⁸ 个字符串进行排序的基准测试，这些字符串是从 1024 个字符串中随机选择的:

import datatable as dt
import pandas as pd
import random
from time import time
n = 10**8
src = ["%x" % random.getrandbits(10) for _ in range(n)]
f0 = dt.Frame(src)
p0 = pd.DataFrame(src)
f0.to_csv("test1e8.csv")

t0 = time(); f1 = f0.sort(0); print("datatable: %.3fs" % (time()-t0))
t0 = time(); src.sort(); print("list.sort: %.3fs" % (time()-t0))
t0 = time(); p1 = p0.sort_values(0); print("pandas:    %.3fs" % (time()-t0))

其中产生:

datatable: 1.465s / 1.462s / 1.460s (multiple runs)
list.sort: 44.352s
pandas:    395.083s

R (v3.4.2) 中的相同数据集:

> require(data.table)
> DT = fread("test1e8.csv")
> system.time(sort(DT$C1, method="radix"))
   user  system elapsed 
  6.238   0.585   6.832 
> system.time(DT[order(C1)])
   user  system elapsed 
  4.275   0.457   4.738 
> system.time(setkey(DT, C1))  # sort in-place
   user  system elapsed 
  3.020   0.577   3.600