为什么 Python 列表实现采用动态数组而不是环形缓冲区？

Question

7

Python中的list现在被实现为指针的动态数组，因此不适合在前端进行插入和删除操作。然而，环形缓冲区也支持O(1)索引。它还可以像动态数组一样扩展和收缩，以支持O(1)摊销的两端插入和删除。为什么CPython没有选择这种实现方式，或者它的主要缺点是什么？

- Jialin Song

2

列表、元组和字典是Python的基本数据结构，它们针对标准用例进行了大量优化，而collections.deque通常不如类似数组的列表快。因此，可能仅仅是出于性能方面的考虑（这并不是确定的答案，只是一个猜测）。 - MSeifert

1

这并不是基于个人观点的问题。他没有问什么是列表的最佳实现，而是询问在Python默认列表中使用非循环数组背后的决策因素是什么。这可以通过客观地列举利弊、运用计算机科学知识和历史记录来进行有益的回答。我投票支持重新开放。 - salezica

谢谢，我已经修改了我的问题使其更具客观性。 - Jialin Song

2

@Chris_Rands 但是collections.deque不是通用的列表类型，也不支持O(1)索引。 - Jialin Song

1

@JialinSong 我投票支持重新开放，现在已经开放了。 - Chris_Rands

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Roland Weber · Accepted Answer

使用环形缓冲区时，除非起始位置恰好在索引0处，否则每次访问都需要进行一些索引转换。但即使如此，您仍需要检查起始位置是否为0。

O（1）只是意味着操作具有固定的成本，但它并不能告诉您该固定成本是高还是低。对于动态数组，通过索引访问元素的成本尽可能低：检查范围，然后访问该项。

Python FAQ在该主题上没有讨论替代实现技术，但它确实提到了通过索引访问元素作为优化目标：https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython。