知识卡片
列表按动态数组理解成本
CPython的list保存对象引用的连续数组,按索引访问通常O(1),中间插入/删除通常要移动引用,故O(n);连续尾部追加的摊销成本较低不代表任意位置pop都O(1)。它也不会每次增删都重分配,实际保留一定容量。原书list.delete不是现有列表方法,应区别del语句、remove与pop各自语义。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 语法最佳实践——类级别以下 2.1.2 集合类型 · 查看原书依据
列表被实现为长度可变的数组
参考来源
- 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第2章 语法最佳实践——类级别以下,spine011单元004;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00010.html。
- 结论依据:原文以变长数组解释列表,索引与移动引用的工作不同,因此中间增删和尾部追加不能使用同一种成本结论。补充核验入口:https://raw.githubusercontent.com/python/cpython/v3.5.10/Objects/listobject.c。未在本机运行示例或改变环境。
- 原始内容:的列表根本不是列表。在CPython中,列表被实现为长度可变的数组。对于其他Python实现(如Jython和IronPython)而言,这种说法应该也是正确的,虽然这些项目的文档中没有记录其实现细节。造成这种混淆的原因很清楚。这种数据