python中的顺序表
Python中的list和tuple两种类型采用了顺序表的实现技术,tuple是不可变类型,即不变的顺序表,因此不支持改变其内部状态的任何操作,而其他方面,则与list的性质类似。
list的基本实现技术
Python标准类型list就是一种元素个数可变的线性表,可以加入和删除元素,并在各种操作中维持已有元素的顺序(即保序),而且还具有以下行为特征:
1)基于下标(位置)的高效元素访问和更新,时间复杂度应该是O(1);为满足该特征,应该采用顺序表技术,表中元素保存在一块连续的存储区中。
2)允许任意加入元素,而且在不断加入元素的过程中,表对象的标识(函数id得到的值)不变。为满足该特征,就必须能更换元素存储区,并且为保证更换存储区时list对象的标识id不变,只能采用分离式实现技术。
在Python的官方实现中,list就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append(x) (或 list.insert(len(list), x),即尾部插入)比在指定位置插入元素效率高的原因。
在Python的官方实现中,list实现采用了如下的策略:在建立空表(或者很小的表)时,系统分配一块能容纳8个元素的存储区;在执行插入操作(insert或append)时,如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大(目前的阀值为50000),则改变策略,采用加一倍的方法。引入这种改变策略的方式,是为了避免出现过多空闲的存储位置。
List对象的C结构
Python中list是用下边的C语言的结构来表示的。ob_item
是用来保存元素的指针数组,allocated是ob_item
预先分配的内存总容量
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
参考链接:https://www.cnblogs.com/Vito2008/p/5141546.html
最新文章
- 项目中angular js的接口url统一管理
- sys.stdout.write与sys.sterr.write(三)
- iOS开发 - OC - 苹果为大家提供的后台:CloudKit 的简单使用
- 国内外著名B2C系统介绍兼比较ASP.NET和PHP
- php文件上传类
- ${fn:length(worklicenseList)} #表示不在struts堆栈里,没有#表示从struts堆栈里取
- 【java】利用异常机制,往前台写错误信息
- Python之列表生成式、生成器、可迭代对象与迭代器
- B/S和C/S【转载Jane的博客 http://blog.sina.com.cn/liaojane】
- 用Nodejs+Express搭建web,nodejs路由和Ajax传数据并返回状态,nodejs+mysql通过ajax获取数据并写入数据库
- MySQL - 高可用性:少宕机即高可用?
- 【转载】C#中自定义Sort的排序规则IComparable接口
- 这可能是最为详细的Docker入门吐血总结
- 爬虫之scrapy入门
- pthread_create()
- python 数据类型元组与字典内置方法
- MySql修改root密码以及允许外网访问
- Docker Tomcat远程部署到容器
- [auto-download-app] 如何使用 javascript 实现 app 自动下载
- MAYA逼真手枪制作视频教程 中文字幕
热门文章
- Luogu P4643 【模板】动态dp(矩阵乘法,线段树,树链剖分)
- BZOJ 5097: [Lydsy1711月赛]实时导航(最短路 + bitset)
- 【HDU3595】GG and MM(博弈论)
- 状压DP总结
- A1136. Delayed Palindrome
- [luogu5077][Tweetuzki 爱等差数列]
- 【洛谷 P1616 疯狂的采药】
- JDK几个高版本的新特性
- 计算机基础:计算机网络-chapter3
- 关于 C# 中 Dictionary与Hashtable的性能测试