金源在线客服

在线咨询

QQ在线咨询

QQ咨询

01Jan

Python适合写算法和数据结构实现吗?

不少算法类入门书籍、培训机构贩卖的算法教程会拿CPython的易用性跟算法实现作为卖点,他们所指的“Python”其实就是CPython。因为执行效率极低的CPython跑Python代码实现的算法和数据结构,跟其他静态语言跑相同的算法相比,其时间开销放大数十倍到数百倍、甚至数千倍。

在C、C++、C#、Java这些静态语言中找到算法实现的种种合理性,只要你稍微理解过CPvthon源代码实现,这种合理性在CPython中是不存在的。算法学习的最终目地是令你写的代码执行效率尽可能地快,并且更好的阅读性

一条Python语句等价2-4条指令字节码指令不等。每条字节码指令实质上在CPython内核opcode.h头文件中有一个特定整数与其对应CPython虚拟机执行字节码指令是依靠ceval.c源文件中的一个事件主循环来不断匹配switch 控制结构每个case分支中字节码指令。

每个字节码case 分支分别静态调用了对应多条的CPython内核的C函数。那么执行一个字节码指令行最终实质上调用该字节码case分支的多条C函数。

当你使用Python语句实现某个排序算法,该算法实现本身在语义上增加了多余的代码语句,CPython解释器在编译对应的Python语句时会额外生成多余的字节码指令。那么执行纯Python代码实现的算法与会比CPython调用其C底层实现相同算法实现要慢成百个甚至上千倍都不止。CPython内置的查找、排序这些算法本来就是C实现的。本来很轻松的一个C调用就能解决的问题。非的用CPython去绕一大圈来解决同一个问题。这不是蛋疼是什么!

另外,CPython的虚拟机执行指令是非常低效的,其CPython函数调用执行纯粹是基于CPython构建的栈帧对象执行,一条指令少则2-3次入栈/出栈操作,多则4-5次。其次CPython的虚拟机实现无法像C/C++程序那样 充分利用x86_64架构多余的物理寄存器缓存多个内部变量,因此无法减少其函数栈的时间开销。

选择一门开发语言学习算法和数据结构,更不应该使用CPython之类的解析语言,学习算法实现的其中一个重要阶段是算法/数据结构的效能测试,也就是在检测一个算法在不同阶段,测试代码执行该算法/数据结构返回的时间开销和空间开销,以判断你的算法实现上下文中找出性能瓶颈的代码用一个纯CPython实现的算法或数据结构,从CPython的内存管理和其底层的执行机制来说CPython返回和其他更低层静态语言实现相同算法(或数据结构)相比,返回更大偏差的参考数据,这样的效能测试得到结果毫无参考意义可言,这样对于算法学习者是一种严重的误导。对于熟悉C、C++的开发者并且稍微阅读过CPython实现源代码都能悟出的一个基本共识--CPython不适合用于算法和数据结构实现!!


   

上一篇:在未来,何时、何故会让Python被取代?
下一篇:RPython、CPython、Cython的关系