C和Python中插入排序的性能差异

0 投票

5 回答

1801 浏览

提问于 2025-04-15 15:02

我对用C语言和Python实现插入排序的性能很感兴趣，但得到的结果让我觉得我可能做错了什么。我原本以为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语言会更快，但没想到差距这么大。

我不想使用内置函数或其他东西。我想自己实现这个算法。有没有什么“Python风格”的方法可以用在插入排序上？

代码优化 c语言性能分析算法实现编程语言比较随机数生成插入排序效率差异

5 个回答

这里有一些你应该记住的经验教训：

用解释型的Python写代码速度比较慢。别试着在Python里自己写快速傅里叶变换（FFT）、MPEG编码器等。
即使是慢的Python，对于小问题来说也可能足够快。比如说，运行8秒并不算太糟糕，而用C语言写和调试代码可能要花你更多的时间，所以如果你只是想写个一次性的程序，Python更合适。
如果想让Python运行得快一点，尽量依赖内置功能和C语言模块。让别人的C代码来处理复杂的部分。我曾经在一个嵌入式设备上工作，虽然那个设备的处理器很慢，但因为大部分工作都是通过C语言库模块来完成的，所以性能还不错。

为了好玩和学习，请再试一次你的Python测试，这次用内置的.sort()方法对一个列表进行排序；虽然可能没有C语言快，但也差不多。（不过对于特别大的数据集，它可能会比C语言快，因为插入排序效率不高。如果你把C语言的代码改成用C库的qsort()函数，那就会是速度之王。）

一个常见的Python设计“模式”是：首先，用Python写你的应用。如果速度够快，就可以停了；这样就完成了。其次，尝试重写代码以提高速度；看看有没有可以用的C语言模块。如果还是不够快，可以考虑自己写一个C语言模块；或者，写一个C程序，用Python的原型代码作为设计基础。

回答于 2025-04-15 由 Python大师

分享举报

我首先想到的是，我手头的这台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

而你的结果是8.1秒。这个结果是把你的代码放在了insort.py文件里，前面加上了：

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

使用array并没有帮助，反而让速度稍微慢了一点。然后我安装了psyco，这是一个Python的即时编译助手（只支持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倍，这让你非常惊讶;-）。

当然，问题在于第一次运行后，列表已经排好序了，所以插入排序变得非常快。你没有给我们足够的测试环境信息，所以我们不知道你到底测量了什么。一个更现实的例子（在这个例子中，实际列表没有被修改，所以它保持无序，只有一个副本被排序...），没有使用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倍速度的一半。换句话说，你可以预期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快52倍，总体上比不使用psyco的插入排序快1582倍。

但是，当你出于某种原因必须在Python中编写极低级的算法，而不是利用内置函数和标准库的丰富支持时，psyco可以帮助减轻这种痛苦。

还有一点是，当你进行基准测试时，请发布所有代码，这样其他人才能准确看到你在做什么（并可能发现一些问题）——你的“框架”可能和你认为正在测量的代码一样复杂，容易隐藏陷阱！-)

回答于 2025-04-15 由 Python大师

分享举报

Python是一种动态语言，标准的实现方式是通过解释器来执行代码。这意味着，像编译后的C代码可以通过一条机器指令快速完成的事情，比如给vec->v[i+1]赋值，Python的解释器却需要做很多事情：它要先从本地范围内查找这个序列变量，再查找它的类，找到类中的设置项的方法，然后调用这个方法。比较、加法也是一样。更不用说，几乎每执行一条字节码，CPU都会出现间接分支预测错误，这会导致处理器的流水线出现问题。

这样的代码如果能用JIT编译成本地代码，并在运行时进行类型专门化，就能获得很大的性能提升，像unladen-swallow和PyPy正在做的那样。

不过，这段代码在Python中写得还算不错，因为如果要实现插入排序，这就是在Python中实现的方式。但从另一个角度看，这又不太符合Python的风格，因为其实应该使用非常高效的内置排序方法。

回答于 2025-04-15 由 Python大师

分享举报

C和Python中插入排序的性能差异

5 个回答

撰写回答