我试图找到一种快速的方法来在Python中对字符串进行排序,并且语言环境是一个无关紧要的问题,即我只想根据底层字节对词汇进行排序.这非常适合基数排序.这是我的MWE
import numpy as np
import timeit
# randChar is workaround for MemoryError in mtrand.RandomState.choice
# https://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中完成.
最佳答案
R实际上是所有字符串,这意味着它有一个“全局字符缓存”,它充当了程序使用的所有字符串的中心字典.这有其优点：数据占用的内存较少,某些算法(如基数排序)可以利用这种结构来实现更高的速度.对于诸如示例中的情况尤其如此,其中唯一字符串的数量相对于向量的大小较小.另一方面,它也有它的缺点：全局字符缓存阻止对字符数据的多线程写访问.
在Python中,afaik只有字符串文字被实习.例如：
>>> 'abc' is 'abc'
True
>>> x = 'ab'
>>> (x + 'c') is 'abc'
False
在实践中,这意味着,除非您将数据直接嵌入到程序文本中,否则不会实现任何内容.
现在,对于您的原始问题：“在python中对字符串进行排序的最快方法是什么？”使用python datatable包可以实现与R相当的非常好的速度.这是从一组1024中随机选择的N =10⁸字符串的基准测试：
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