C和python中insert-sort的性能差异

Question

我很好奇使用C和python进行insert-sort的性能,但是我得到的结果让我想到如果我做错了什么.我怀疑C会更快,但不是那么多.

我已经分析了两个代码,插入排序功能是花费时间最多的地方.

这是C函数:

void
insert_sort (vec_t * vec)
{
    int j;
    for (j = 1 ; j < vec->n ; j++){
        int key = vec->v[j];
        int i = j - 1;
        while (i >= 0 && vec->v[i] > key){
            vec->v[i+1] = vec->v[i];
            i--;
        }
        vec->v[i+1] = key;
    }
}

这是python函数:

def insert_sort (ln):
    for j in range(1, len(ln)):
        key = ln[j]
        i = j-1
        while i >= 0 and ln[i] > key:
            ln[i+1] = ln[i]
            i-=1
        ln[i+1] = key

用10000个整数进行测试,每个整数随机生成0到10000之间.

每个函数花费的时间的结果是:

• C时间:0.13秒
• python时间:8.104秒

我在这里做错了吗？就像我说的,我希望看到C代码更快,但不是那么快.

我不想使用内置函数或任何东西.我想实现这个算法.是否有一种pythonic方式来做我可以在插入排序中使用的东西？

Answer 1

Python是一种动态语言,标准实现使用解释器来评估代码.这意味着编译的C代码可以使用单个机器指令进行转义,例如分配给vec-> v [i + 1],Python的解释器必须从本地范围中查找序列变量,查找其类,查找类上的项设置方法,调用该方法.同样的比较,添加.更不用说执行几乎每个字节码都会导致CPU中的间接分支误预测导致管道泡沫.

这种代码可以从JIT编译到本机代码和运行时类型专业化中受益匪浅,比如unladen-swallow和PyPy正在开始这样做.

否则,代码几乎是pythonic,因为如果需要实现插入排序,这就是人们如何在Python中实现它.它也是非常不合理的,因为你应该使用非常有效的内置排序.

Answer 2

我的第一个想法是,我现在手头的笔记本电脑,一台Macbook Pro,必须与你的机器相当但略胜一筹 - 我没有足够的周围代码来试试你的C例子(什么是vec_t,等等),但运行你编码的Python给我:

$ python -mtimeit -s'import inso' 'inso.insort(inso.li)'
10 loops, best of 3: 7.21 msec per loop

vs 8.1秒.这就是你输入的代码insort.py,前面是:

import random
li = [random.randrange(10000) for _ in xrange(10000)]

array没有帮助 - 实际上减慢了一点.然后我安装了psyco,Python JIT助手(仅限x86,仅限32位),进一步添加:

import psyco
psyco.full()

得到了:

$ python -mtimeit -s'import inso' 'inso.insort(inso.li)'
10 loops, best of 3: 207 usec per loop

所以加速度大约是7.21/0.000207 = 34830倍 - 相比8.04/0.13 = 62倍,让你大吃一惊;-).

当然,问题是在第一次之后,列表已经排序,因此insort必须更快.你没有给我们足够的周围测试线束来确切知道你测量的是什么.一个更现实的例子(实际列表没有被触及,所以它保持无序,只有一个副本被排序......),没有psyco:

$ python -mtimeit -s'import inso' 'inso.insort(list(inso.li))'
10 loops, best of 3: 13.8 sec per loop

哎呀 - 所以你的机器比Macbook Pro更快(记得,核心不计算:我们在这里只使用一个;-) - 哇...否则,你是错误的测量.无论如何,与psyco:

$ python -mtimeit -s'import inso' 'inso.insort(list(inso.li))'
10 loops, best of 3: 456 msec per loop

因此psyco的加速比率仅为13.8/0.456,30倍 - 大约是纯C编码60倍以上的一半.IOW,你希望python + psyco的速度是纯C的两倍.这是一个更现实和典型的评估.

如果我们编写合理的高级代码,psyco的速度会从(比如说)30倍降低到更低 - 但C的优势也会超过Python.例如,

$ python -mtimeit -s'import inso' 'sorted(inso.li)'
100 loops, best of 3: 8.72 msec per loop

没有psyco(在这种情况下,psyco实际上 - 略微 - 减慢了执行速度 ;-),这是另一个因素而不是psyco,比非psyco insort总计1582.

但是,由于某种原因,你必须在python中编写极低级别的算法,而不是使用内置函数和stdlib的大量支持,psyco可以帮助减轻痛苦.

另一点是,当您进行基准测试时,请发布所有代码,以便其他人可以准确地看到您正在做什么(并且可能发现陷阱) - 您的"脚手架"非常棘手并且可能隐藏陷阱,因为您认为自己的代码重新测量! - )