列表三巨头，第二部分

• 下载 ALists2.zip - 2 MB

简介

在上一篇文章中，我介绍了 A-List，一个“万能”列表，它是传统 List<T> 和内存中 B+ 树的结合体。它还具有一些有趣的特性，例如在 O(log N) 时间内合并或拆分两个大列表、冻结、快速克隆和可观察性。

在本文中，我将讨论基于 A-List 概念的排序“B”数据结构：BList<T>、BDictionary<K,V> 和 BMultiMap<K,V>。这是一个类图——类似于上一篇文章中的图，但具有不同的派生类。

正如我在第一篇文章中所说，A-List 系列（包括 BDictionary、BList 和 BMultiMap）的数据结构是类似于 B+ 树的树数据结构，但有一个不寻常的特性：它们是可索引的；您可以编写 alist[index]（要了解其工作原理，查看上一篇文章中的图可能有所帮助）。

在我年轻的软件开发者生涯中，我到处都使用了很多索引列表和可增长数组，有时当您在长列表的中间或开头插入大量元素时，它们的性能会变得非常慢。用计算机科学的术语来说，构建一个包含大量元素的列表，当在随机位置插入时，需要 O(n^2) 的时间，这意味着对于大的 n 来说，它的速度非常非常慢！A-List 数据结构没有这个问题；它们从不慢。它们确实比 List<T> 具有更高的常数开销，但随着列表变大，它们的性能下降得不多。

基本的索引功能和树结构的管理是在基类 AListBase<T>、AListNode<K,T>、AListInnerBase<K,T> 和 AListLeaf<K,T> 中实现的。图中新派生的类（那些以“B”开头的类）提供并强制执行数据必须排序的约束。

BDictionary：B 代表 Better（更好）

.NET 框架有一个名为 SortedList<TKey,TValue> 的类。切勿、永远不要使用该类来构建排序列表！ 除非，也就是说，数据已经是排序好的，在这种情况下，您仍然不需要 SortedList。

SortedList 的问题当然是性能。从 n 对随机顺序的键值对构建 SortedList 需要 O(n^2) 的时间。相反，您应该使用 SortedDictionary<TKey,TValue> 或 BDictionary<K,V>，具体取决于您是否需要 BDictionary 的众多功能。

BDictionary<K,V> 非常像 SortedList，只是快得多，而且功能多得多。与 SortedList 一样，BDictionary 是一个按排序顺序存储项目的字典，并且允许按索引访问项目。它对所有操作都高效：Add、Remove、IndexOf、ContainsKey、FindLowerBound、FindUpperBound 以及索引器都以 O(log N) 时间运行。您可以在创建它时指定一个键比较委托，因此类型 K 不需要是直接可排序的，并且您不必按 T 的“自然顺序”进行排序。

它还支持 SortedList 不支持的以下操作：

• FindLowerBound(k)：查找键等于或大于 k 的项目的最低索引。它的行为类似于标准的 C++ 函数 lower_bound。
• FindUpperBound(k)：查找列表中第一个大于 k 的项目的索引（这通常比 FindLowerBound 用处小）。
• AddRange(list)、RemoveRange(list)、RemoveRange(start, count)
• this[key, defaultValue]：查找与键关联的值。如果找不到该键，则返回 defaultValue。
• Clone()：以 O(1) 时间创建副本（此技术在第一部分中已解释）
• CopySection、RemoveSection：在 O(log N) 时间内复制或删除列表的任何部分。
• AddIfNotPresent(k, v)：仅当字典中不存在指定键时，才添加指定的键值对。
• ReplaceIfPresent(k, v)：如果字典中已存在键 k，则替换与之关联的值。
• SetAndGetOldValue(k, ref v)：获取与 k 关联的旧值（如果存在），然后设置 this[k] = v。

并且，与所有派生自 AListBase 的类一样，BDictionary（以及 BList 和 BMultiMap）支持 RemoveAll(lambda)、快速 Clone()、Freeze()、Slice()、ReverseView 和 ListChanging 事件。

发现设计缺陷了吗？

如果 K 恰好是 int，BDictionary<K,V> 会给您带来一个小问题，因为存在一个 this[K] 索引器和一个 this[int] 索引器。所以如果您调用 dict[4]，它会获取第五个元素（类型为 KeyValuePair<K,V>），还是获取与键 4 关联的 V 值？嗯，这两个索引器存在于不同的类中：this[K] 在派生类中，而 this[int] 在基类中。因此，dict[4] 将获取与键 4 关联的 V 值，您可以通过向上转换来获取第五个元素：((AListBase<int,KeyValuePair<int,V>>) dict)[4]。好的，这有点笨拙，但它能正常工作。

BList 和 BDictionary：我撒谎了。B 代表 B+ tree。

BList<T> 只是一个排序列表（像所有其他 A-List 类一样，它被构造为 B+ 树）。与 SortedList<TKey,TValue> 和 BDictionary 不同，它只是一个列表，而不是一个字典。BList 允许重复项，因此它不是一个“集合”类。它允许您在创建时指定一个比较委托，因此类型 T 不需要是直接可排序的，并且您不必按 T 的“自然顺序”进行排序。

BList 拥有 BDictionary 的所有相同特性，只是没有“键”和“值”之间的那种烦人的区别。关于 BList 没有太多可说的了，让我们继续……

BMultiMap<K,V>，它派生自 BList<KeyValuePair<K,V>>，是一种特殊的字典，允许重复键（以及重复值）。或者，从另一个角度看，它允许将多个值与单个键关联。它与 C++ 的 std::multimap 类相当，尽管它能更轻松地完成一些事情（例如，您可以使用 AddIfUnique() 避免重复键值对）。

要使用 BMultiMap<K, V>，K 和 V 都必须是可比较的（与 BDictionary 不同，后者只需要键类型 K 可比较）。某些方法（如 AddIfUnique 和 Remove(KeyValuePair<K,V>)（从 BList 继承））需要此要求才能正确工作。如果您想使用一个实际上不可比较的 V，您可以使用一个假定所有 V 都相等的比较函数（通过始终返回 0）；只是要注意，任何试图区分 V 的方法都会表现得好像它们都相等！您也可以基于 GetHashCode() 进行排序，但要非常、非常小心处理两个不相关的对象具有相同哈希码的可能性（IndexOfExact() 有时有助于处理这种情况）。

BMultiMap 提供了它是一个已排序集合字典的假象。索引器 this[K] 返回一个 BMultiMap<K,V>.Values 结构，它实现了 ICollection<V> 并提供对与特定键关联的所有值的访问。要添加一个新的键值对，您可以调用 multimap 本身的 Add(K, V)，或者调用 this[K].Add(V)。类似地，您可以使用 RemoveAll(k) 或 this[K].Clear() 来删除一个键的所有值。

实际上，BMultiMap 并不是一个集合字典，它只是一个单一的排序列表。该列表首先按键排序，然后按值排序，因此与特定键 k 相关的所有值都相邻地排列在列表中。Values 结构调用 FindLowerBound 和 FindUpperBound 来确定这个“子列表”在整个列表中的开始和结束位置。

请注意，this[K] 返回的集合不是可索引的；您不能编写 this[key][0]，例如，尽管您当然可以使用 this[K].First()，依赖于 LINQ 扩展方法 First()，您还可以使用 foreach 循环迭代特定键的值。Values 集合没有索引器，因为它将不正确或效率低下。不正确，因为如果它缓存第一个项目的位置以提高性能，当项目在地图的其他部分被添加或删除时，该位置将发生变化。另一方面，如果 Values 不缓存第一个项目的位置（它不缓存），像这样的循环可能会非常慢

var values = multimap[key];
for (int i = 0; i < values.Count; i++) {
   DoSomethingWith(values[i]);
} 

首先，测量 Count 需要对 multimap 进行两次搜索：一次找到下界（Values 开始于指定 key 的位置），另一次找到上界（该 key 的 Values 结束的位置）。然后，由于这些索引没有缓存，values[i] 将不得不再次查找下界，然后查找从下界偏移 i 处的项目，最后检查以确保该项目的键相同（如果不同，则必须抛出 IndexOutOfRangeException）。由于所有这些工作都会减慢您的代码速度，因此不提供索引器。请改用 foreach 循环；下界将在循环的第一次迭代之前计算一次，并且上界不会被计算（相反，Values 枚举器会继续向前扫描 B+ 树，直到当前 KeyValuePair 的键发生变化）。

调用索引器 this[K] 时，指定的键不必存在于集合中。如果它不存在，索引器将返回一个空集合（顺便说一句，不要不必要地调用 this[k].Count；请记住，需要两次搜索才能测量集合的长度。）

BMultiMap 具有一些您可能会发现有用的方法。

• FindLowerBound(k)：就像 BDictionary 中同名的方法一样，它查找第一个等于或大于 k 的元素。同样，FindUpperBound 查找第一个大于 k 的元素。
• FirstIndexOf(k)：类似于 FindLowerBound(k)，除了如果找不到 k，它会返回 -1。
• AddIfUnique(k, v)：如果不存在与新键值对相等的键值对，则添加该键值对。
• Remove(k, max)：删除与指定键关联的前 max 个值。
• RemoveAny(k)：删除具有指定键的任意一个键值对（它类似于 Remove(k, 1)，但运行速度稍快，您无法预测会删除哪一个）。
• RemoveAll(k)：删除所有具有指定键的键值对。
• IndexOfExact(k)、FindLowerBoundExact(k)：查找一个值 k 的索引，该值不仅使用比较函数比较相等，而且也使用 object.Equals 进行比较。如果比较函数仅基于对象的一部分进行排序，但您还想匹配比较函数忽略的对象的其余部分，这将非常有用。

结论

好了，这就是您需要了解的一堆排序数据结构。

就性能而言，我尚未对任何这些数据结构进行基准测试，但我可以自信地预测：

• 对于索引、枚举（foreach）、在末尾添加元素、从末尾删除元素以及任何涉及短列表（小于 20-50 个元素）的操作，AList<T> 系列数据结构通常比 List<T> 慢。
• 对于长列表，在随机位置插入和删除、合并列表、拆分列表、克隆等操作，AList<T> 系列数据结构通常比 List<T> 快。
• AList<T> 系列数据结构通常比 List<T> 使用稍多的内存。
• 对于中等大小的列表（大于 50 个元素），BDictionary<K,V> 通常比 SortedList<K,V> 快得多。BList<T> 和 BMultiMap<K,V> 的性能与 BDictionary<T> 相似。
• BDictionary<K,V> 会比 Dictionary<K,V> 慢，但通常使用的内存会更少。
• 我不知道 BDictionary<K,V> 是否比 SortedDictionary<K,V> 快或慢，但它肯定会使用更少的内存。
• BMultiMap<K,V> 的内存要求与 BDictionary<K,V> 相同，并且它使用的内存将比 Dictionary<K,List<V>> 少得多。

在第三部分，我将讨论更简单得多的 DList<T> 和 DListInternal<T> 数据结构，它们在某些情况下比 List<T> 和 AList<T> 更快。

与本文相关的下载自上一篇文章以来已被重构为两个库，但仍然包含许多与 ALists 无关的内容。除了 ALists，我还编写了几个其他集合类和各种其他“实用”库——符号、VLists、扩展方法等等——我太忙（太懒？）了，现在无法剥离它们。当我写到本系列的第三部分时，我会努力做得更好。现在，Loyc.Essentials.dll 包含杂项代码，其中一些与我的集合类有关，一些无关。Loyc.Collections.dll 是主要的集合类集合，包括所有 AList 数据结构。还有一个测试套件（基于 NUnit），包含的 Tests.exe 程序将运行它。

项目和解决方案适用于 Visual Studio 2010，目前编译为 .NET 4，尽管 A-Lists 的实现中没有任何东西需要 .NET 4。如果您将 A-Lists 适配到 .NET 2.0、Silverlight、XNA 等，请随时发表评论分享您的成功。

历史 

• 2013 年 3 月 27 日：第一部分发布
• 2013 年 9 月 8 日：第二部分发布