知识卡片

普通读书笔记卡 · 1958.c.12.a.1.bf · 生成模型:未记录

列表按动态数组理解成本

理解等级:中级

CPython的list保存对象引用的连续数组,按索引访问通常O(1),中间插入/删除通常要移动引用,故O(n);连续尾部追加的摊销成本较低不代表任意位置pop都O(1)。它也不会每次增删都重分配,实际保留一定容量。原书list.delete不是现有列表方法,应区别del语句、remove与pop各自语义。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《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)而言,这种说法应该也是正确的,虽然这些项目的文档中没有记录其实现细节。造成这种混淆的原因很清楚。这种数据