拒绝通知

基于 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. 替换现有的 list 类型

动机

BList 的诞生源于需要重写直观算法的挫败感，这些算法对于小输入来说效果很好，但由于基于数组的列表的 O(n) 行为，对于大输入则需要 O(n**2) 的时间。Python 2.4 中引入的 deque 类型解决了需要快速 FIFO 队列的最常见问题。然而，如果我们需要频繁地在长列表的中间插入或删除元素，deque 类型就没有帮助了。

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

本 PEP 中提出的 BList 类型基于 B+ 树的原理，它兼具数组和树的特性。BList 在处理小列表时提供类似数组的性能，同时为所有插入和删除操作提供 O(log n) 的渐近性能。此外，BList 在底层实现了写时复制，因此即使是 getslice 等操作也只需要 O(log n) 的时间。下表比较了当前基于数组的列表实现的渐近性能与 BList 的渐近性能。

Python 的基于数组的列表与 BList 的广泛实证比较可在 [2] 中找到。

用例权衡

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 个元素的列表进行的性能测试中，BLists 在这两种用例中的执行时间分别增加了 50% 和 5%。

通过在根节点缓存指向最右侧叶节点的指针，LIFO 用例的性能可以提高到 O(n) 时间。对于大小不变的列表，通过在根节点进行缓存，顺序访问的常见情况也可以提高到 O(n) 时间。然而，这些方法的性能尚未经过实证测试。

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

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

实施

BList 基于 B+ 树数据结构。BList 是一种宽而茂密的树，其中每个节点包含一个最多包含 128 个指向其子节点的指针的数组。如果节点是叶节点，其子节点是用户放置在列表中的用户可见对象。如果节点不是叶节点，则其子节点是用户不可见的 BList 节点。如果列表只包含少量元素，它们将全部成为同时作为根节点和叶节点的单个节点的子节点。由于节点不过是一个指针数组，小列表的操作方式与基于数组的数据类型基本相同，并共享相同的良好性能特征。

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

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

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

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

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

内存使用

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

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

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

向后兼容性

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

对于 C API，BList 的接口与现有列表实现不同。由于其更复杂的结构，BList 不太适合被外部源进行探测和检查。幸运的是，现有的列表实现定义了一组函数和宏，用于访问列表对象中的数据。Google Code Search 表明，大多数第三方模块使用定义良好的 API，而不是直接依赖列表的结构。下表总结了搜索查询和结果：

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

1. 重新定义 listobject.h 中的各种访问器函数和宏，以访问 BList。接口将保持不变。函数可以轻松重新定义。宏需要更仔细的处理，并且对于大列表需要诉诸函数调用。

   宏需要对其参数进行多次评估，如果参数具有副作用，这可能会有问题。Google Code Search 搜索“PyList_GET_ITEM([^)]+(”仅发现少数此类情况，因此影响似乎很小。

   少数直接使用列表的未记录结构而不是 API 的扩展模块将会中断。核心代码本身相对一致地使用访问器宏，并且应该很容易移植。

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

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

   这种方法的缺点是，混合使用 BLists 和基于数组的列表的模块可能会因为频繁的转换而导致性能下降。

参考实现

CPython 的 BList 参考实现可在 [1] 获得。

源代码包还包含一个纯 Python 实现，最初是作为 CPython 版本的原型开发的。当然，纯 Python 版本相当慢，并且渐近改进的效果要到列表相当大时才能显现。

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

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

讨论

此提案已在 Python-3000 邮件列表中进行了简要讨论 [3]。尽管许多人支持该提案，但也有一些反对意见。下面总结了帖子中观察到的优点和缺点：

一般性评论

• 优点：在大多数情况下将优于基于数组的列表
• 优点：“我曾多次实现过这个的变体……”
• 缺点：在实际应用中的期望性和性能未经证实

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

• 优点：匹配 list API 降低了学习曲线到几乎为零
• 优点：对中级用户有用；不会妨碍初学者
• 缺点：数据类型的泛滥使开发者的选择更加困难。

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

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

为了评估在实际应用中的期望性和性能，Raymond Hettinger 建议将 BList 作为扩展模块发布（现已在 [1] 提供）。如果它被证明有用，他认为它将成为 2.6 中作为 collections 模块一部分的有力候选者。如果广受欢迎，那么就可以考虑替换基于数组的列表，但不能在其他情况下。

Guido van Rossum 评论说，他反对数据类型的泛滥，但如果能够解决向后兼容性并且 BList 的性能普遍更好，他就支持替换基于数组的列表。

进行中的任务

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

参考资料

版权

本文档已置于公共领域。