python列表底层实现原理
Python 列表的数据结构是怎么样的?书上说的是:列表实现可以是数组和链表。 列表是一个线性的集合,它允许用户在任何位置插入、删除、访问和替换元素。
可参考《Python高级编程(第2版)》 从细节上看,Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着,每次添加或删除一个元素时,由引用组成的数组需要该标大小(重新分配)。幸运的是,Python在创建这些数组时采用了指数分配,所以并不是每次操作都需要改变数组的大小。但是,也因为这个原因添加或取出元素的平摊复杂度较低。 不幸的是,在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。 利用 list.insert(i,item) 方法在任意位置插入一个元素——复杂度O(N)
index() O(1) O括号里面的值越大代表效率越低
list和tuple在c实现上是很相似的,对于元素数量大的时候, 为什么要有tuple,还有很多的合理性。 认为tuple比list快的人大概是把python的tuple和list类比成C++中的数组和列表了。 相关文档深入 Python 列表的内部实现:http://python.jobbole.com/82549/[python]list,tuple,dictionary,set的底层细节:https://blog.csdn.net/siyue0211/article/details/80560783Python列表:初学者应该懂得操作和内部实现:https://mp.weixin.qq.com/s/IkFak4iYYqW7u61P7eu22gpython学习笔记 – list内部实现:https://www.jianshu.com/p/cd75475168ae从底层理解Python的执行:https://www.csdn.net/article/2015-05-28/2824795 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |