<p>你有几个问题。在</p>
<p>首先,正如在评论中指出的,对于理论上的复杂性来说,您的数据集太小,无法克服代码中的开销。在</p>
<p>接下来,所有那些不必要的函数调用和复制列表的实现是非常低效的。以直接的过程方式编写代码几乎总是比函数式解决方案快(对于Python,也就是说,其他语言在这里会有所不同)。你有一个快速排序的过程实现,所以如果你用同样的风格来写基数排序,那么即使是对于小列表,它也可能更快。在</p>
<p>最后,可能是当你尝试大列表时,内存管理的开销开始占主导地位。这意味着您在小列表和大列表之间有一个有限的窗口,其中实现的效率是主要因素,而大列表的主要因素是内存管理。在</p>
<p>下面是一些使用快速排序的代码,但它是一个简单的按程序编写的radix排序,但要避免大量的数据复制。您将看到,即使对于短列表,它也优于快速排序,但更有趣的是,随着数据大小的增加,快速排序和基数排序之间的比率也会增加,然后随着内存管理开始占主导地位,它又开始下降(例如释放一个包含1000000个项目的列表这样的简单事情需要很长时间):</p>
<pre><code>from random import randint
from math import log10
from time import clock
from itertools import chain
def splitmerge0 (ls, digit): ## python (pure!)
seq = map (lambda n: ((n // 10 ** digit) % 10, n), ls)
buf = {0:[], 1:[], 2:[], 3:[], 4:[], 5:[], 6:[], 7:[], 8:[], 9:[]}
return reduce (lambda acc, key: acc.extend(buf[key]) or acc,
reduce (lambda _, (d,n): buf[d].append (n) or buf, seq, buf), [])
def splitmerge1 (ls, digit): ## python (readable!)
buf = [[] for i in range(10)]
divisor = 10 ** digit
for n in ls:
buf[(n//divisor)%10].append(n)
return chain(*buf)
def radixsort (ls, fn = splitmerge1):
return list(reduce (fn, xrange (int (log10 (max(abs(val) for val in ls)) + 1)), ls))
###############################################################################
# quick sort
###############################################################################
def partition (ls, start, end, pivot_index):
lower = start
upper = end - 1
pivot = ls[pivot_index]
ls[pivot_index] = ls[end]
while True:
while lower <= upper and ls[lower] < pivot: lower += 1
while lower <= upper and ls[upper] >= pivot: upper -= 1
if lower > upper: break
ls[lower], ls[upper] = ls[upper], ls[lower]
ls[end] = ls[lower]
ls[lower] = pivot
return lower
def qsort_range (ls, start, end):
if end - start + 1 < 32:
insertion_sort(ls, start, end)
else:
pivot_index = partition (ls, start, end, randint (start, end))
qsort_range (ls, start, pivot_index - 1)
qsort_range (ls, pivot_index + 1, end)
return ls
def insertion_sort (ls, start, end):
for idx in xrange (start, end + 1):
el = ls[idx]
for jdx in reversed (xrange(0, idx)):
if ls[jdx] <= el:
ls[jdx + 1] = el
break
ls[jdx + 1] = ls[jdx]
else:
ls[0] = el
return ls
def quicksort (ls):
return qsort_range (ls, 0, len (ls) - 1)
if __name__=='__main__':
for value in 1000, 10000, 100000, 1000000, 10000000:
ls = [randint (1, value) for _ in range(value)]
ls2 = list(ls)
last = -1
start = clock()
ls = radixsort(ls)
end = clock()
for i in ls:
assert last <= i
last = i
print("rs %d: %0.2fs" % (value, end-start))
tdiff = end-start
start = clock()
ls2 = quicksort(ls2)
end = clock()
last = -1
for i in ls2:
assert last <= i
last = i
print("qs %d: %0.2fs %0.2f%%" % (value, end-start, ((end-start)/tdiff*100)))
</code></pre>
<p>运行此命令时的输出是:</p>
^{pr2}$
<p><strong>编辑</strong>:
只是想澄清一下。在这里复制列表不是很友好的事情,只是在快速排序表的执行中。原始的radix排序有效地为每个数字复制两次列表:一次复制到较小的列表中,然后在连接列表时再次复制。使用<code>itertools.chain</code>可以避免第二个副本,但仍有大量内存分配/释放正在进行。(另外,“两倍”是近似值,因为附加列表确实需要额外的复制,即使它是按O(1)摊销的,所以我可以说“按比例乘以两倍”。)</p>