python中set、deque、list、dict内部实现原理 |
您所在的位置:网站首页 › 美国的英语单词全写 › python中set、deque、list、dict内部实现原理 |
几大重要的数据结构:数组(线性表)、链表、hash表 分别对应了python中的list、deque、dict、set,但其内部实现原理比C的要复杂不少,也有很多好用的接口 listpython中的list要满足以下要求: 是数组类型,以索引就可以直接取到元素,O(1)取元素 元素可以是任意类型 可以任意添加新元素,容易扩充 基于以上要求,list的实现设计为: 1. 元素外置,每个元素只存储index 2. 分离式结构,表内元素和表头信息不在一起 3. 动态扩充 在python中创建空list时,会申请一个8个元素大小的内存区域。以后如果满了,就扩容4倍,不断反复,直至当元素总数达到50000时,再扩容就改为2倍 各操作时间复杂度: 参考: https://www.cnblogs.com/yifeixu/p/8893823.html 顺序表的原理与python中的list类型 https://wiki.python.org/moin/TimeComplexity deque各操作时间复杂度: dict 各操作时间复杂度: set 各操作时间复杂度:
判断值是否存在,千万不要用list,list查找的复杂度为O(n),而set和dict由于用hash实现,查找的复杂度为O(1) (待更新)
参考: https://www.cnblogs.com/tianyiliang/p/10330878.html https://www.cnblogs.com/linshuhui/p/9580620.html https://blog.csdn.net/u010366748/article/details/51469937 (Python内置方法的时间复杂度)
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |