拒绝通知

基于 Raymond Hettinger 的明智建议被拒绝 [4]

在查看了源代码后，我认为它几乎没有机会取代 list()。简单的 C API、小列表的低空间开销、常见用例的良好性能以及易于理解的性能都有太大的价值。BList 实现缺乏这些优点，它在一些不常见的用例中以牺牲一些常见用例的性能为代价换取了更好的性能。作为 Py3.0 PEP，我认为它可以被拒绝。

取决于它作为第三方模块的成功，它仍然有机会被包含在 collections 模块中。为此，它必须是某些真实用例中的最佳选择。我扫描了自己的代码，发现没有任何实例表明 BList 比普通列表更好。但是，该扫描具有选择性偏差，因为它没有反映出如果 BList 可用，我会写什么。因此，在几个月后，我打算在 comp.lang.python 中进行投票，询问 BList 的成功案例。如果存在，那么我不反对将其包含在 collections 模块中。毕竟，它的学习曲线几乎为零——唯一的成本是由于对给定任务最合适的数据结构的犹豫而产生的混乱因素。

摘要

列表操作的常见情况是对小列表进行操作。当前基于数组的列表实现由于对引用的强局部性和内存分配操作的频率较低，因此在小列表上表现出色。但是，数组需要 O(n) 时间来插入和删除元素，这在列表变大时会变得很麻烦。

此 PEP 引入了一种新的数据类型 BList，它具有数组和树状结构。它在小列表上的性能与现有的基于数组的实现一样好，但对大多数操作提供了更好的渐近性能。此 PEP 提出了两个相互排斥的提案，用于将 BList 类型包含在 Python 中

1. 将其添加到 collections 模块中，或者
2. 替换现有的列表类型

动机

BList 诞生于需要重写直观算法的挫败感，这些算法对于小的输入来说工作正常，但由于基于数组的列表的底层 O(n) 行为，对大的输入来说需要 O(n**2) 时间。在 Python 2.4 中引入的 deque 类型解决了最常见的问题，即需要一个快速的 FIFO 队列。但是，如果我们需要反复从长列表的中间插入或删除元素，deque 类型就没有帮助。

各种各样的数据结构为插入和删除提供了良好的渐近性能，但它们要么对其他操作（例如，链表）具有 O(n) 的性能，要么对小列表（例如，二叉树和跳表）具有较差的性能。

此 PEP 中提出的 BList 类型基于 B+ 树的原理，B+ 树具有数组和树状结构。BList 在小列表上提供了类似数组的性能，同时对所有插入和删除操作提供了 O(log n) 的渐近性能。此外，BList 在幕后实现了写时复制，因此即使是像 getslice 这样的操作也需要 O(log n) 时间。下表比较了当前基于数组的列表实现的渐近性能与 BList 的渐近性能。

在 [2] 中可以找到对 Python 的基于数组的列表和 BList 的广泛经验比较。

用例权衡

BList 为许多操作提供了更好的性能，但并非所有操作。为特定用例选择正确的数据类型取决于使用的操作。作为内置类型选择正确的数据类型取决于平衡不同用例的重要性以及性能差异的幅度。

对于小列表的常见用例，基于数组的列表和 BList 具有相似的性能特征。

对于稍微不常见的用例，即大型列表，有两种常见的用例，现有的基于数组的列表胜过现有的 BList 参考实现。它们是

1. 一个大型 LIFO 堆栈，其中有许多 .append() 和 .pop(-1) 操作。对于基于数组的列表，每个操作都是 O(1)，但对于 BList 来说是 O(log n)。
2. 一个不会改变大小的大型列表。对于基于数组的列表，getitem 和 setitem 调用是 O(1)，但对于 BList 来说是 O(log n)。

在对包含 10,000 个元素的列表进行性能测试时，BList 在这两个用例中分别表现出 50% 和 5% 的执行时间增长。

可以通过在根节点中缓存指向最右叶节点的指针，将 LIFO 用例的性能提高到 O(n) 时间。对于不会改变大小的列表，通过在根节点中缓存，常见的顺序访问也可以提高到 O(n) 时间。但是，这些方法的性能尚未经过经验测试。

从基于数组的列表切换到 BList 时，许多操作表现出巨大的加速（从 O(n) 到 O(log n)）。在对包含 10,000 个元素的列表进行性能测试时，诸如 getslice、setslice 以及 FIFO 式插入和删除之类的操作在 BList 上只需要基于数组的列表所需时间的 1%。

鉴于许多操作的性能大幅提升，一些操作的小性能成本对于许多（但并非所有）应用程序来说都是值得的。

实现

BList 基于 B+ 树数据结构。BList 是一棵宽而茂密的树，每个节点包含一个最多包含 128 个指向其子节点的指针的数组。如果节点是叶子节点，那么它的子节点就是用户在列表中放置的用户可见对象。如果节点不是叶子节点，那么它的子节点就是其他不可见的 BList 节点。如果列表只包含少数元素，那么它们都将是单个节点的子节点，该节点既是根节点又是叶子节点。由于节点只是一个指针数组，因此小列表的运行方式与基于数组的数据类型基本相同，并且具有相同的良好性能特征。

BList 维护一些不变性，以确保无论插入和删除操作的顺序如何，都能获得良好的（O(log n)）渐近性能。主要的恒等式如下：

1. 每个节点最多包含 128 个子节点。
2. 每个非根节点至少包含 64 个子节点。
3. 根节点至少包含 2 个子节点，除非列表包含少于 2 个元素。
4. 树的深度一致。

如果插入会导致节点超过 128 个子节点，那么该节点会生成一个兄弟节点，并将一半的子节点转移到兄弟节点。兄弟节点被插入到该节点的父节点中。如果该节点是根节点（因此没有父节点），则会创建一个新的父节点，树的深度增加 1。

如果删除会导致节点的子节点少于 64 个，那么该节点会尽可能地从其兄弟节点中移动元素。如果它的两个兄弟节点也只有 64 个子节点，那么这两个节点会合并，空的节点从其父节点中删除。如果根节点减少到只有一个子节点，那么它的唯一子节点将成为新的根节点（即树的深度减少 1）。

除了树状渐近性能和对小列表的类似数组的性能之外，BList 还支持透明的 **写时复制**。如果非根节点需要被复制（作为 getslice、copy、setslice 等的一部分），那么该节点将在多个父节点之间共享，而不是被复制。如果它以后需要被修改，它将在那个时候被复制。这完全是在幕后进行的；从用户的角度来看，BList 的工作方式就像普通的 Python 列表一样。

内存使用

在最坏的情况下，BList 的叶子节点每个只有 64 个子节点，而不是完整的 128 个，这意味着内存使用量大约是最佳情况数组实现的两倍。非叶子节点使用的额外内存量可以忽略不计，因为叶子节点的数量至少是非叶子节点的 63 倍。

现有的基于数组的列表实现必须在添加和删除项时增长和收缩。为了提高效率，它只在列表呈指数级增长或收缩时增长或收缩。在最坏的情况下，它的内存使用量也是最佳情况的两倍。

总之，BList 的内存占用量与现有的基于数组的实现没有显著差异。

向后兼容性

如果 BList 被添加到 collections 模块中，则向后兼容性不是问题。本节重点介绍用 BList 替换现有的基于数组的列表的选项。对于 Python 解释器的用户来说，BList 与当前的列表实现具有相同的接口。对于几乎所有操作，除了执行速度之外，行为都相同。

对于 C API，BList 与现有的列表实现具有不同的接口。由于其更复杂的结构，BList 不适合外部资源的探查和操作。值得庆幸的是，现有的列表实现定义了一个 API，该 API 包含用于从列表对象访问数据的函数和宏。Google 代码搜索表明，大多数第三方模块使用定义良好的 API，而不是直接依赖列表的结构。下表总结了搜索查询和结果

这可以通过以下两种方式实现

1. 在 listobject.h 中重新定义各种访问器函数和宏，以便访问 BList。接口将保持不变。函数可以很容易地被重新定义。宏需要更多小心，对于大型列表，它们必须使用函数调用。

   宏需要多次计算其参数，如果参数有副作用，这可能是一个问题。Google 代码搜索中 “PyList_GET_ITEM([^)]+(” 发现只有少数情况下会发生这种情况，因此影响似乎很小。

   少数直接使用列表的未公开结构（而不是使用 API）的扩展模块将无法正常工作。核心代码本身非常一致地使用访问器宏，应该很容易移植。

2. 弃用现有的列表类型，但继续包含它。希望使用新的 BList 类型的扩展模块必须明确地这样做。BList C 接口可以更改为匹配现有的 PyList 接口，以便简单的搜索替换足以满足 99% 的模块编写者。

   现有的模块将继续编译并正常工作，但它们需要做出有意的（但很小的）努力迁移到 BList。

   这种方法的缺点是，混合使用 BList 和基于数组的列表的模块可能会导致速度下降，尤其是在频繁需要转换的情况下。

参考实现

BList 的参考实现可供 CPython 使用，位于 [1]。

源代码包还包含一个纯 Python 实现，最初作为 CPython 版本的原型开发。当然，纯 Python 版本相当慢，并且直到列表非常大时，渐进改进才会胜出。

在用 Py_DEBUG 编译时，C 实现会在进入和退出大多数函数时检查 BList 不变式。

源代码包中还包含一组广泛的测试用例。测试用例包括现有的 Python 序列和列表测试用例作为子集。当解释器使用 Py_DEBUG 构建时，测试用例还会检查引用泄漏。

讨论

这个提案曾在 Python-3000 邮件列表上进行过简短讨论 [3]。虽然许多人赞成该提案，但也有一些反对意见。下面总结了发帖者对该主题的意见中观察到的优缺点。

一般评论

• 优点：在大多数情况下，性能将优于基于数组的列表
• 优点：“我已经实现了这个的变体……几次了”
• 缺点：在实际应用程序中的可取性和性能尚未得到证实

关于将 BList 添加到 collections 模块的评论

• 优点：与列表 API 匹配，学习曲线几乎为零
• 优点：对中级用户有用；不会影响初学者
• 缺点：数据类型的激增使开发人员的选择更加困难。

关于用 BList 替换基于数组的列表的评论

• 缺点：对扩展模块的影响（在 向后兼容性 中解决）
• 缺点：BList 速度较慢的用例很重要（请参阅 用例权衡，了解如何解决这些问题）。
• 缺点：基于数组的列表代码简单易于维护

为了评估实际应用程序中的可取性和性能，Raymond Hettinger 建议将 BList 作为扩展模块发布（现在可从 [1] 获取）。他认为，如果它被证明有用，它将成为 2.6 中作为 collections 模块一部分包含的强有力候选者。如果它广受欢迎，那么可以考虑用它替换基于数组的列表，但否则不行。

Guido van Rossum 评论说，他反对数据类型的激增，但赞成用 BList 替换基于数组的列表，只要可以解决向后兼容性问题，并且 BList 的性能始终更好。

正在进行的任务

• 减少小型列表的内存占用
• 为 BList 实现 TimSort，以便最佳情况排序为 O(n) 而不是 O(log n)。
• 实现 __reversed__
• 在根节点中缓存指向最右边叶节点的指针，使 LIFO 操作的时间复杂度为 O(n)。

参考文献

版权

本文件已置于公共领域。