为什么我的基数排序python实现比快速排序慢?

2024-06-17 15:51:08 发布

您现在位置:Python中文网/ 问答频道 /正文

我使用来自SciPy的数组重写了来自SciPy的Python原始基数排序算法,以获得性能并减少代码长度,这是我成功完成的。然后,我从文学编程中选取了经典的(内存中,基于枢轴的)快速排序算法,并比较了它们的性能。在

我预期基数排序会超过某个阈值,而快速排序则没有。此外,我发现Erik Gorset's Blog's提出了一个问题“对于整数数组,基数排序是否比快速排序快?。答案是这样的

.. the benchmark shows the MSB in-place radix sort to be consistently over 3 times faster than quicksort for large arrays.

不幸的是,我无法重现结果;不同之处在于:(a)Erik选择了Java而不是Python;(b)他使用MSB代替基数排序,而我只是在Python字典中填充bucket。在

根据理论,与快速排序相比,基数排序应该更快(线性);但显然它很大程度上取决于实现。我的错误在哪里?在

下面是比较两种算法的代码:

from sys   import argv
from time  import clock

from pylab import array, vectorize
from pylab import absolute, log10, randint
from pylab import semilogy, grid, legend, title, show

###############################################################################
# radix sort
###############################################################################

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 splitmergeX (ls, digit): ## python & numpy

    seq = array (vectorize (lambda n: ((n // 10 ** digit) % 10, n)) (ls)).T
    buf = {0:[], 1:[], 2:[], 3:[], 4:[], 5:[], 6:[], 7:[], 8:[], 9:[]}

    return array (reduce (lambda acc, key: acc.extend(buf[key]) or acc,
        reduce (lambda _, (d,n): buf[d].append (n) or buf, seq, buf), []))

def radixsort (ls, fn = splitmergeX):

    return reduce (fn, xrange (int (log10 (absolute (ls).max ()) + 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__":
###############################################################################

    lower = int (argv [1]) ## requires: >= 2
    upper = int (argv [2]) ## requires: >= 2
    color = dict (enumerate (3*['r','g','b','c','m','k']))

    rslbl = "radix sort"
    qslbl = "quick sort"

    for value in xrange (lower, upper):

        #######################################################################

        ls = randint (1, value, size=value)

        t0 = clock ()
        rs = radixsort (ls)
        dt = clock () - t0

        print "%06d -- t0:%0.6e, dt:%0.6e" % (value, t0, dt)
        semilogy (value, dt, '%s.' % color[int (log10 (value))], label=rslbl)

        #######################################################################

        ls = randint (1, value, size=value)

        t0 = clock ()
        rs = quicksort (ls)
        dt = clock () - t0

        print "%06d -- t0:%0.6e, dt:%0.6e" % (value, t0, dt)
        semilogy (value, dt, '%sx' % color[int (log10 (value))], label=qslbl)

    grid ()
    legend ((rslbl,qslbl), numpoints=3, shadow=True, prop={'size':'small'})
    title ('radix & quick sort: #(integer) vs duration [s]')
    show ()

###############################################################################
###############################################################################

下面是比较大小在2到1250(横轴)范围内的整数数组的排序持续时间(对数垂直轴)的结果;下曲线属于快速排序:

快速排序在幂次变化时是平滑的(例如,在10、100或1000),但是基数排序只是跳跃一点,但在其他方面遵循与快速排序相同的路径,只是慢得多!在


Tags: lambdareturn排序valuedefdtsortupper
2条回答

你有几个问题。在

首先,正如在评论中指出的,对于理论上的复杂性来说,您的数据集太小,无法克服代码中的开销。在

接下来,所有那些不必要的函数调用和复制列表的实现是非常低效的。以直接的过程方式编写代码几乎总是比函数式解决方案快(对于Python,也就是说,其他语言在这里会有所不同)。你有一个快速排序的过程实现,所以如果你用同样的风格来写基数排序,那么即使是对于小列表,它也可能更快。在

最后,可能是当你尝试大列表时,内存管理的开销开始占主导地位。这意味着您在小列表和大列表之间有一个有限的窗口,其中实现的效率是主要因素,而大列表的主要因素是内存管理。在

下面是一些使用快速排序的代码,但它是一个简单的按程序编写的radix排序,但要避免大量的数据复制。您将看到,即使对于短列表,它也优于快速排序,但更有趣的是,随着数据大小的增加,快速排序和基数排序之间的比率也会增加,然后随着内存管理开始占主导地位,它又开始下降(例如释放一个包含1000000个项目的列表这样的简单事情需要很长时间):

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)))

运行此命令时的输出是:

^{pr2}$

编辑: 只是想澄清一下。在这里复制列表不是很友好的事情,只是在快速排序表的执行中。原始的radix排序有效地为每个数字复制两次列表:一次复制到较小的列表中,然后在连接列表时再次复制。使用itertools.chain可以避免第二个副本,但仍有大量内存分配/释放正在进行。(另外,“两倍”是近似值,因为附加列表确实需要额外的复制,即使它是按O(1)摊销的,所以我可以说“按比例乘以两倍”。)

你的数据表示非常昂贵。为什么要在bucket中使用hashmap?为什么要用base10表示法来计算对数(=计算成本很高)?在

避免lambda表达式之类的,我认为python还不能很好地优化它们。在

也许可以从为基准测试排序10字节字符串开始。而且:没有哈希图和类似昂贵的数据结构。在

相关问题 更多 >