归并排序，用c语言与python实现的效率对比

<< tinySQL 开发总结 | 首页 | The art of Unix Programming，读书志1 >>

2008-05-03

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
 http://peterpannju.blogbus.com/logs/20204391.html

对比思路：
   从文件中读取一组整形数据(每行一个)，存入数据结构中，对其进行归并排序。
   用time命令记录排序时间。
   用strace查看系统调用的时间开销。

归并排序的实现思路：

mergeSort

归并排序的算法复杂度：
    Worst Case: O(nlogn)
    Average Case: O(nlogn)
    Best Case: O(nlogn)

误差分析：
    c实现中，有两次文件遍历操作，一次用于计算文件行数(数组长度)，一次用于将所有数据存入数组中；
    python实现中，除了排序本身，估计最大的时间消耗就是list.extend()方法，效率应该比较底(但是影响程序具体到什么程度，不知)；
    假设，当整形数据总数很大时，以上两种误差皆可忽略不计，在这次测试中，让数据总量为200000，存于./num.txt中，由python程序随机产生(不计入python测试时间)，c程序读取该文件；

测试环境：
    OS: Arch Linux(Core Dump)
    Compiler: gcc 4.3.0 & Python 2.5.2-2
    CPU: PM 2.0G Hz

测试命令：
    1. 生成随机数文件，将200000个随机数存入./num.txt文件。

>>>[/tmp/mergeSort/] >% ls
mergeSort.c mergeSort.py
>>>[/tmp/mergeSort/] >% python
Python 2.5.2 (r252:60911, Feb 23 2008, 21:20:32)
[GCC 4.2.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import mergeSort
>>> mergeSort.generateNum("num.txt", 200000)
200000 random numbers writed to num.txt.
>>> exit()
>>>[/tmp/mergeSort/] >% ls
mergeSort.c mergeSort.py mergeSort.pyc num.txt

2. 编译c语言写成的mergeSort.c

>>>[/tmp/mergeSort/] >% gcc mergeSort.c
>>>[/tmp/mergeSort/] >% ls
a.out mergeSort.c mergeSort.py mergeSort.pyc num.txt

3. 将num.txt中的随机数排序，比较运行时间

>>>[/tmp/mergeSort/] >% time ./a.out num.txt >c.out
./a.out num.txt > c.out 0.19s user 0.00s system 98% cpu 0.199 total
>>>[/tmp/mergeSort/] >% time ./mergeSort.py >py.out
./mergeSort.py > py.out 5.75s user 0.03s system 99% cpu 5.832 total
>>>[/tmp/mergeSort/] >% wc -l c.out py.out
200000 c.out
200000 py.out
400000 总计
>>>[/tmp/mergeSort/] >% diff c.out py.out
>>>[/tmp/mergeSort/] >%

    可见，生成的c.out(c程序的排序结果)和py.out(python程序的排序结果)两个文件完全一样。而时间花费，c程序排序200000个整数用了0.19秒，python程序用了5.75秒，30多倍差距。

思考：
    1. python中并没有数组这一数据结构，数组是通过list来近似实现的，而list的每次从文件中读取一行，extend()操作都得分配一次内存，同样的操作执行了200000次；
    2. c语言的200000个数的内存分配是一次完成的；
    3. 通过strace跟踪系统调用，发现时间花费最多的居然是将数据从文件中读入，几乎占用了大部分时间，这样测试就不准确，变成了对比python和c语言的文件操作效率对比；
    4. strace系统跟踪，发现python程序中有一个mmap2系统调用花费了大部分时间，但是我不知道问题出在哪里？相关代码：

>>>[/tmp/mergeSort/] >% strace -rr ./mergeSort.py
     ......
     0.000092 mmap2(NULL, 802816, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xb7846000
     5.284778 rt_sigaction(SIGINT, {SIG_DFL}, {0xb7f46230, [], 0}, 8) = 0
     0.053376 munmap(0xb7846000, 802816) = 0
     0.013651 munmap(0xb7057000, 839680) = 0
     .....

5. 貌似这段时间是在用户级的排序操作。所以系统调用没有显示(?)

附件：
mergeSort.py
mergeSort.c

References:
归并排序(MergeSort)