65.9K
CodeProject 正在变化。 阅读更多。
Home

列表三合一，第 1 部分

Qwertie
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.97/5 (21投票s)

2013年3月26日

LGPL3

21分钟阅读

viewsIcon

38317

downloadIcon

161

A-list 是一种通用列表，一种数据结构，可以支持大多数标准列表操作在 O(log n) 时间内完成，并且还有很多其他功能

介绍 

标准的 List<T> 数据类型非常快，前提是——如果！——你只需要读取它并在末尾添加新项。但是，在随机位置插入和删除需要 O(N) 时间，并且在大型 List<T> 上多次执行此操作会非常慢。如果你真的选择随机位置进行插入和删除，每次插入或删除平均会移动列表的一半元素。当然（这听起来可能很明显），复制整个列表也需要 O(N) 时间*。 

* 如果有新手正在阅读此内容，我将简要解释 O(N) 和 O(log N) 等“大 O”符号的含义。此符号描述了算法随着输入越来越大时的行为（技术上它不会告诉你任何关于小输入的性能信息）。O(N) 操作所需的时间与列表大小成正比，所以当我说插入一个项需要 O(N) 时间时，这意味着插入到包含 200 万个项的列表所需的时间是插入到包含 100 万个项的列表所需时间的两倍。然而，O(log N) 操作所需的时间呈对数增长，这意味着当有 200 万个项时，它只比 100 万个项时稍微长一点。O(1) 意味着一个操作总是花费相同的时间。“大 O”符号不会告诉你任何关于相对性能的信息；例如，一个 O(N) 操作可能比另一个 O(N) 操作花费 5 倍的时间。换句话说，O(5*N) = O(N)，因为此符号总是忽略“常数因子”。如果你连续执行一系列 O(N) 操作，总和仍然是 O(N)。最后，应该警惕 O(N^2)，“二次复杂度”。O(N^2) 操作对于 200 万个项所需的时间是 100 万个项的 4 倍，对于 100 万个项所需的时间是 1000 个项的约 1000 倍。O(N^3)，“三次复杂度”，真的是可怕的，你应该远离它，除非你知道你的数据集会很小。

我曾经认为这些属性是理所当然的，直到我在 StackOverflow 上某个地方读到，可以实现一个列表，以 O(log N) 时间进行插入和删除。我对数据结构的无限热爱再次爆发，经过 9 个月（左右）的工作，我的新宝贝 A-list 诞生了。 

A-list 完成普通列表所做的一切，但时间复杂度为 O(log N)。对于小型列表，它比 List<T> 慢，但在某些情况下，对于大型列表，它可能显着更快。除此之外，它还支持批量插入（将整个列表以 O(log N + M) 的时间插入到大小为 M 的 A-List 中）、快速克隆（O(1) 常数时间）、两个 A-list 之间的 O(log N) 分割和连接、冻结列表以及可观察性。 

尽管 A-list 内部结构相当复杂，但从外部看，它实现了与其他所有列表相同的 IList<T> 接口，此外还有一堆其他很酷的功能。 

它主要为大型列表设计。对于小型列表，内存使用情况不算太差，但如果你主要做 List<T> 擅长的事情，例如按索引随机访问和只在末尾添加项目，那么速度上会受到影响。如果你需要在列表的开头和结尾添加/删除项目，或者你需要在随机位置插入/删除，但你的列表总是很小，那么我的 DList<T> 数据结构（在未来的文章中描述）将比 AList<T> 更适合你。

自从编写 AList 系列类以来，我让它闲置了一年多。我计划对其进行基准测试，并重新考虑一些设计决策，但我一直太忙而没有做，所以我决定在完成度达到 98% 且性能未测量的情况下发布它。（我确实在第 3 部分进行了一些速度测试）。 

AList<T> 将引导你

我喜欢称 A-list 为“终极新手数据结构”，因为它像费雪牌玩具保护你的孩子一样保护应用程序性能。它不是一辆精瘦、凶猛的跑车，但大多数操作（除了 Sort()、IndexOf()、Remove(T) 和 RemoveAll()）可以在 O(log N) 或更快的时间内完成，甚至 IndexOf() 和 Remove(T) 也可以加速（如果你愿意为所有其他操作付出 2-3 倍的性能代价）。它也绝对不是内存大户。所以如果你想处理长列表但又没有足够的经验来知道使用什么数据结构，只需使用 A-List。它可能不快，但几乎可以保证不会慢。 

例如，您是否曾想删除一些项目并对其执行一些操作？您无法使用如下所示的 foreach 循环完成此操作：

int sum = 0;
foreach (int item in list)
  if (item > 2) {
    sum += item;
    list.Remove(item);
    // Exception occurs! foreach loop cannot continue after Remove()!
  } 

您可能会尝试使用这样的反向 for 循环来解决此问题

for (int i = list.Count - 1; i >= 0; i--)
  if (list[i] > 2) {
    sum += list[i];
    list.RemoveAt(i);
  }  

这可行，但它运行在 O(N^2) 时间内，因此如果列表很大，它会非常慢。一个更好的解决方案是将分析和删除分成两个阶段

int sum = 0;
foreach (int item in list)
  if (item > 2)
    sum += item;
list.RemoveAll(item => item > 2);

但是，如果你没有想到这个解决方案，并且已经编写了 O(N^2) 版本怎么办？现有大量代码依赖于缓慢的 List<T> 操作。解决由于 List<T> 使用不当造成的性能问题的一种简单方法是简单地在前面加上“A”。AList 几乎可以完全替代 List，因此你只需使用 AList 而不是 List 就可以将 O(N^2) 转换为更快的 O(N log N) 代码。

AList<T> 内部结构

从结构上看，A-Lists 与 B+ 树非常相似。它们使用内存的效率几乎与数组一样高，每个列表都是一个“节点”树。每个节点要么是“叶”节点（保存你的数据，即 T 的实例），要么是“内部”节点，也称为“内节点”。下面是它的类图：

A-List 与其他类型的树的关键区别在于 A-List 是可索引的——你可以写 alist[index]。其工作方式是每个内部节点包含其每个子节点的第一个索引。要找到索引 i 处的项目，内部节点执行二分查找以找到包含索引 i 的子节点。每当插入或删除项目时，所有已更改的“第一个索引”都会相应地更新。

与 B+树一样，A-List 树具有一致的高度：例如，如果树高为 3，那么每个叶节点都恰好通过两个内部节点到达；这是树更新方式的结果。每个节点都有一个允许的大小范围；默认情况下，叶节点为 17 到 48 个项目，内部节点为 8 到 16 个项目（顺便说一句，这些数字是我随意挑选的。）

当你添加项目时，一个叶节点可能会变得过大。当一个节点（叶节点或内部节点）变得过大时，一个项目可能会被转移到兄弟节点，但如果兄弟节点也过大（或者如果节点是根节点而没有兄弟节点），则该节点会被一分为二；这会导致父节点增大 1，这可能会导致父节点也过大并分裂。当根节点分裂时，会创建一个新的根节点来指向数据的两半（这会使树的高度增加 1）。

这是一个示例树结构，由以下代码生成：

var list = new AList<char>(maxLeafSize: 6, maxInnerSize: 4) { 
	'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
	'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
	'U', 'V', 'W', 'X'
};
 

 

给定这棵树的配置，它的容量是深度 2 的 24 个子节点（4 × 6）。如果我们添加第 25 个项目

 list.Add('Y');

结果如下：

更详细地说

  1. AList.Add('Y') 调用 AList.Insert(24, 'Y')，后者调用虚拟方法 AListNode.Insert，该方法在其第四个子节点 (STUVWX) 上调用 AListNode.Insert，以在本地索引 6 处（从叶节点的角度）插入项目 'Y'。
  2. 叶节点 STUVWX 将自身一分为二，STU 和 VWX，它们是新对象。
  3. 请求的项 'Y' 被添加到右半部分 (VWXY)，叶子将两半返回给其父节点
  4. 父节点有一个 HandleChildSplit() 方法，该方法会扩大节点并插入新子节点，然后注意到它大于大小限制（我发现先插入项，扩大内部数组，然后再分裂更方便。代码正在做比必要更多的工作，但不用担心，内部节点不需要经常分裂。同时，叶节点会提前分裂以避免不必要的扩大。）
  5. 原始的 AListInner 被另外两个替换，它们被返回给 AList。
  6. AList.Insert() 将一个新的 AListInner（初始化为两个子节点）赋给 _root。

AList 支持大量其他操作，我不会详细介绍。

当您删除项目时，叶节点可能会变得过小。在这种情况下，可以从兄弟节点转移一个项目使其变大，但如果兄弟节点不允许缩小，则该节点会与其中一个兄弟节点合并。这会导致父节点缩小 1，这可能会导致父节点也过小并与其兄弟节点（子节点的“叔叔”）合并。如果根节点缩小到只有一个子节点，则根节点将被消除并替换为该单个子节点（这会使树的高度减少 1）。

如果你真的很聪明，你会理解所有这些。如果不是，快速克隆功能可能会让你大吃一惊。无论如何，考虑阅读 Wikipedia 上关于 B+ 树的条目。AList 和 B+ 树中发生的过程本质上是相同的。事实上，我的库中有三个版本的 AList<T>，它们本质上是 B+ 树加上整数索引（BList<T>、BDictionary<K,V> 和 BMultiMap<K,V>）。

多面手，精通某几样

“A-List”是通用列表的缩写。之所以这样命名，是因为它具有非常丰富的功能和扩展点，可用于进一步扩展此功能。对于大多数任务来说，它不是最快或最小的数据结构，但当你需要对列表执行各种不同的操作，或者计划合并和拆分大型列表时，它非常有用。

对于所有列表大小，A-List 比 List<T> 占用略多的内存。如果你期望在随机位置进行插入和删除，但只是偶尔进行，那么 DList<T>（参见此处文章）可能是更好的选择，因为它具有更快的索引器。这两个类都提供快速枚举（每个元素 O(1)），但 DList<T> 枚举器初始化更快（AList<T> 枚举器需要 O(log N) 时间来准备自身）。 

它还有一些非常独特的功能，我最喜欢的是快速拼接（Append、Prepend、CopySection、RemoveSection）和快速克隆（Clone(bool)）。它还可以以 O(N log N) 的时间进行排序，我发现，当你的数据结构是一棵该死的树时，这比听起来要困难得多。 

您可以订阅 ListChanging 事件，以了解列表何时发生更改（下面将详细介绍）。 

虽然单个插入、删除和随机访问需要 O(log N) 时间，但使用 InsertRange、RemoveRange、GetEnumerator 或 Resize 的任何重载都可以获得更好的性能。其中最慢的 InsertRange 需要 O(log N + M) 时间，其中 M 是您要插入的元素数量，这比重复调用 Insert（O(M log N) 时间）要快得多。 

如果你需要偶尔对树进行快照，AList 是一个很好的选择，因为它支持 O(1) 克隆和写时复制行为（下面将详细介绍）。AList 也可以冻结，这在你需要以只读或可冻结数据结构构建列表时很有用。你还可以冻结列表以返回其只读副本，与克隆相比，其优点是在返回列表时不需要内存分配。如果你稍后需要编辑列表，可以克隆它（克隆可以修改）。

通常，AList<T> 不是多线程安全的。只要集合未被修改，允许多个并发读取器，因此冻结的实例是多线程安全的。 

AList<T> API 深入解析

IList<T> 的标准内容 

 

  • O(1)：Count, IsReadOnly, Clear, MoveNext/Current （在枚举器中）
  • O(log N)：this[index]、Add(item)、Insert(index, item)、RemoveAt(index)、GetEnumerator（枚举器本身每次 MoveNext 都是 O(1)）
  • O(N)：IndexOf(item)、Remove(item)、Contains(item)、CopyTo(array, index)

其中一些操作会因“节点观察者”的存在而变慢，例如 AListIndexer<T>；然而，AListIndexer 可以将 IndexOf(item)、Remove(item) 和 Contains(item) 的速度从 O(N) 提高到 O(log N)。 

范围操作 (IListRangeMethods<T>) 

  • AddRange(list)：以 O(log N + list.Count()) 时间插入一个包含 M 个项的列表。有一个重载接受类型为 AList<T> 的列表；如果您将一个大型 AList 插入到另一个 AList 中，则通过克隆子树，插入操作会优化到 O(log N + log M)。
  • InsertRange(index, list)：以 O(log N + list.Count()) 时间在任何索引处插入一个项目列表。同样，当列表为 AList<T> 时，InsertRange 有一个重载；此重载需要 O(log N + log M) 时间。
  • RemoveRange(index, amount)：以 O(log N) 时间删除连续的项范围。 
  • Sort(index, count, comp), Sort(), Sort(comp): 使用标准 Comparison<T> 委托或 IComparer<T> 在 O(N log N) 时间内对整个列表或列表的一部分进行排序。我为此目的编写了自定义代码，因为一个朴素的快速排序需要 O(N (log N)^2) 时间才能在这种树上操作。

快速克隆 

不同的 AList<T> 对象能够共享自身的只读部分。利用这一点，Clone() 方法在 O(1) 时间内返回树的副本。

克隆可以被修改而不影响原始，原始也可以被修改而不影响副本。其工作原理是树被“秘密地”标记为只读（实际上最初只有根被标记为只读，但这会传递地影响整个树），如果任何一个副本想要修改树，则受影响的树节点会被复制。 

这很棒，但不要太兴奋。尽管它**最初**是 O(1)，但在克隆树后进行的任何更改都会比平时花费更多时间，因为必须复制树的一部分以确保克隆之间不会相互干扰。如果树有 4 层深，那么在克隆树后第一次更改单个元素时，将复制 4 个节点：包含您元素的叶节点，以及包括根节点在内的三个父节点。 

如果你这样做 

AList<int> clone = list.Clone(); // very fast
for (int i = 0; i < list.Count; i += 17) list[i] += 2; // slow
for (int i = 0; i < clone.Count; i += 17) clone[i] *= 2; // slow

第一个 for 循环最终将复制整个树，第二个 for 循环将**再次**复制整个树，将原始树节点作为垃圾留给垃圾回收器。在第二个循环中，克隆无法修改原始树，因为它不知道原始列表不再与克隆共享树的任何部分。 

这些循环只更改每第 17 个元素，但大型树中的单个叶节点包含 17 到 48 个元素（默认情况下）。节点总是整体复制，因此更改每第 17 个元素会保证每个节点都会被复制（除了最后一个）。 

不过，别太担心。如果你**再次**运行这两个 for 循环，它们会运行得快得多，因为在第二次运行时不需要复制任何节点。

注意：如果原始树已通过 Freeze() 冻结，则克隆将被解冻（解冻）。

更多酷炫功能 

  • Freeze()：阻止对列表的进一步更改。调用此方法后，任何尝试修改列表的操作都将导致 ReadOnlyException。如有必要，可以在派生类中禁用此功能。
  • Append(other) 和 Append(other, true)：将“other”（另一个 AList<T>）附加到此列表。如果第二个参数为 false 或省略，则被附加的树将被克隆（将其节点标记为只读）。如果第二个参数为 true，则被附加的另一棵树将被清空，并且该树的内容将合并到此树中。请记住，如果克隆了另一棵树，则其节点将是只读的，这将减慢将来对该树的修改。通过将第二个参数设置为 true，节点不会被标记为只读，因此将来可以修改它们而无需复制。Append 在 O(log N+log M) 时间内工作。
  • Prepend(other) 和 Prepend(other, true)：与 Append 相同，只是“other”的内容插入到列表的开头而不是末尾。
  • Resize(newSize)：更改列表的长度。如果 newSize < Count，列表将在 O(log N) 时间内截断。如果 newSize > Count，新项目将以 O(newSize) 时间添加到列表末尾；这些新项目的值为 default(T)。 
  • TrySet(index, value)：与 list[index] = value 相同，但如果索引无效，TrySet 返回 false 而不是抛出异常。TryGet(index, defaultValue) 作为扩展方法可用。
  • ReverseView 属性：返回一个包装器，它为您提供对列表项的只读反向访问。这是一种方便的方式，可以通过 foreach 循环向后枚举集合（反向枚举器每个元素运行时间为 O(1)，就像正向枚举器一样）。 
  • Slice(start, length)：返回一个包装器，它以 O(1) 时间提供列表子部分的只读视图。
  • CopySection(start, count)：类似于 Clone，但只克隆列表的一个部分。大多数情况下，“start”和“start+count”不会恰好落在树节点之间，因此在范围的边缘将不得不复制部分节点。这会稍微减慢操作速度，但此函数在复制大段时仍以 O(log N) 时间工作。
  • RemoveSection(start, count)：删除列表的一个部分并返回它。这与 CopySection 不同，因为 RemoveSection 不需要“克隆”它返回的任何节点，这会将它们标记为只读并减慢将来对该部分的修改。与 CopySection 一样，RemoveSection 通常必须将范围边缘周围的一些元素复制到新节点，或者可能调整范围开头和结尾附近的节点边界。尽管如此，总体上它仍然在 O(log N) 时间内运行。

其他功能（没那么酷，但仍然实用） 

  • First，Last：在 O(log N) 时间内获取第一个或最后一个项目。
  • IsFrozen：告诉你这个列表副本是否被冻结。如果你不喜欢它被冻结的事实，没关系，克隆它就好了。
  • IndexesOf(item) 和 IndexesOf(item, minIndex, maxIndex)：返回表示给定项在列表中出现位置的整数序列。IndexedAList 有一个 IndexesOf(item, bool sorted) 方法，当列表被索引时，该方法可以更快地完成相同的事情。
  • Swap(AList<T>)：原地交换两个列表
  • RemoveAll(Predicate<T>)：删除所有符合条件的项
  • GetIterator：以后再问我 

随机事实：AList<T> 是可序列化的，但它并非专门为序列化而设计或优化。 

列表观察器 

AList<T> 支持两种完全不同的观察方式。一种是传统的“告诉我何时添加或删除项目”的观察方式，可通过 ListChanging 事件获得。为了效率，它不使用与 ObservableCollection 相同的接口；最重要的是，事件在列表更改时调用，而不是更标准的 ListChanged 在列表更改后才调用事件处理程序。事实证明，了解正在进行的更改有时不如了解完成后的更改有用，因此此功能的设计可能会在某天更改（我目前没有积极地重新设计它）。 

另一种观察是低级别的“树观察者”，它会收到关于树中节点如何重新排列以及哪些项目在哪些节点中被添加或删除的通知。大多数人永远不会想使用此功能，并且使用它可能会带来显着的性能损失。要以这种方式进行观察，您必须编写一个实现 IAListTreeObserver<T,T> 的类，然后调用 AddObserver(observer) 将 AList 链接到您的观察者。 

第二种观察器由 AListIndexer<T> 使用，用于跟踪 AList<T> 中每个项目的索引，以加快 IndexOf(item)、Contains(item) 和 Remove(item) 的速度。

IndexedAList<T> 

这是一个 AList<T> 的派生类，当列表很大时，它可以加速 IndexOf(item)、Contains(item) 和 Remove(item)。它是一个简单的包装器，使用 AListIndexer<T,T> 提供索引功能。不幸的是，IndexedAList<T> 改变了这三个函数的行为；它们不再查找项的第一次出现，而是查找任何出现。

默认情况下会创建一个索引，但如有必要，可以在构造函数中或通过将 IsIndexed 属性设置为 false 来暂时禁用索引。但是，如果调用这三个函数中的一个（IndexOf...），索引将自动重新创建。索引构建需要 O(N log N) 时间，其中 N 是长度（Count）。 

反过来，AListIndexer 观察变化并构建树中的项目表。AListIndexer 仅设计用于加速大型列表中的搜索，对小型列表不提供任何性能优势；相反，它只会浪费小型列表中的时间和内存。

一般来说，AListIndexer 比被索引的列表需要更多的内存。具体来说，如果指针使用 P 字节，那么 AListIndexer 本身消耗的内存略多于 X+P*N 字节，其中 X 是被索引列表的大小（以字节为单位），N 是列表中的项目数。因此，例如，一个索引的 Object 列表所需的内存大约是一个未索引的 AList 的三倍。 

此外，更改已索引列表所需的时间至少是原来的两倍，因为索引器必须收到每次更改的通知，并且索引的更新每次需要 O(log N) 时间。涉及 X 个项目且在没有索引器的情况下需要 O(log N) 时间的批处理操作（例如 RemoveRange(i, X)）将需要 O(X log N) 时间，因为索引器必须收到有关每个更改项目的通知。 

尽管如此，在需要频繁搜索列表中项目的应用程序中，这些成本可能是值得的。 

结论

那么我们今天学到了什么？AList<T>（及其基类 AListBase<T>）是一种树结构，它伪装成一个简单的列表。其树结构使其能够有效地操作非常长的列表，支持相对快速的插入、删除和拼接操作（尽管索引单个元素会额外消耗）。节点可以被冻结（并通过自动复制解冻），这使得 AList<T> 能够支持快速克隆和作为“持久”数据结构的有限使用。它有如此多的方法，以至于可以被称为 KS<T> 代表“万能树”。对于短列表，AList<T> 的性能不差，但如果你知道永远不需要处理非常长的列表，那么使用它可能不值得。

A-List 是否已准备好用于关键任务尚不清楚。它内部结构复杂，因此我无法保证它没有错误，尽管它确实有一套相当不错的测试套件。目前，用于加速 IndexOf() 和 Remove(T) 的 IndexedAList<T> 类尚未经过任何测试，尽管已对 AListIndexer<K,T>（IndexedAList<T> 的核心机制）进行了一系列基本测试。 

在第 2 部分和第 3 部分中，您可以阅读有关相关数据结构，例如 BList<T> 和 BMultiMap<T>。BList<T>、AList<T> 和其他类共享一个共同的基类和一些实现。AList<T> 和其他类在内部也使用一种称为 DListInternal<T> 的数据结构，它是一个由数组和两个整数组成的结构。但那是未来文章的故事。 

现已推出：第 2 部分和第 3 部分

下载

我已经将过去几年编写的 AList 和其他 C# 代码打包成一个名为 LoycCore 的 NuGet 包（但我计划将此包拆分为按 DLL 的包，所以也请搜索“Loyc.Collections”看看我是否已经完成了）。AList 源代码作为 Loyc.Collections.dll 的一部分在 GitHub 上提供，还有一个 Loyc Core 网站。

注意：如果不将 Loyc.Essentials.dll 作为依赖项，单独提取和使用 AList 有点困难，因为 AList 依赖于 Loyc.Essentials.dll 中定义的接口和其他部分。

历史

  • 2012年底：完成度96%
  • 2013年3月27日：完成度98% + 发布CodeProject文章
  • 2013年9月9日：“AList<T> 内部结构”：使用两张新图表展示运行时结构
  • 2014年8月12日：修复了几个内部 AList 错误。切换到通过 NuGet 和 GitHub 分发。发布了本系列文章的第 3 部分。

 

© . All rights reserved.