C# 中的 VList 数据结构

Qwertie

4.85/5 (12投票s)

2009年4月2日

LGPL3

21分钟阅读

75248

364

一系列类似数组的列表结构，让您可以在任何时间点快速捕获快照。

下载源代码 - 117 KB

引言

VList 数据结构由 Phil Bagwell 设计，旨在替代函数式编程语言中的单向链表。它可以被认为是链表和动态数组（例如 .NET Framework 的 List<T> 类）之间的一种折衷，它融合了两者的优点。

我为 .NET 创建了四个不同 VList 数据类型的家族：

FVList：Phil Bagwell 描述的标准不可变 VList，新项添加到前面（索引 [0] 处）。
RVList：反向 VList。RVList 比 FVList 更适合 .NET Framework，因为新项添加到后面（索引 [Count] 处）。
FWList：FVList 的可变版本，性能接近 List<T>。
RWList：RVList 的可变版本；实际上，它是 List<T> 的替代品。

在内部，所有这些都是在混合可变-不可变 VList 之上构建的，我将在本文中对其进行描述。这些数据类型中的任何一个实例都可以在 O(1) 到 O(log N) 时间内转换为其他任何一个。

注意：最初 FVList 被命名为 VList。然而，最常见的是人们希望使用 RVList 或 RWList，因为它们遵循 .NET 约定，即项在列表的“末尾”添加和删除。因此，在我的 Loyc 项目中，我正在考虑将 RVList 重命名为 VList，这样人们每次创建 RVList 时就不必考虑房车了。但显然，我不能将 RVList 重命名为 VList，除非我首先将正向 VList 重命名为其他名称...所以我将其命名为 FVList。不过，在本文中，我只重命名了 VList，而不是 RVList，以避免对过去阅读过本文的人造成混乱。

在本文中，“VList”一词可能统指 FVList 和 RVList，“WList”可能统指 FWList 和 RWList。

背景

函数式编程语言大量使用“持久性链表”，即其项不可变（永不修改）的链表。由于它们是不可变的，因此在两个链表之间共享链表的一部分总是绝对安全的。如果您不熟悉它们，请查看以下持久性链表数据结构的完整实现：

public struct PList<T> : IEnumerable<T>
{
    private PList(PNode<T> n) { _node = n; }
    private PNode<T> _node;

    public PList<T> Add(T item)
    {
        _node = new PNode<T>(item, _node);
        return this;
    }
    public T Head
    {
        get { return _node.Value; }
    }
    public PList<T> Tail
    {
        get { return new PList<T>(_node.Next); }
    }
    public bool IsEmpty
    {
        get { return _node == null; }
    }
    public IEnumerator<T> GetEnumerator()
    {
        PNode<T> n = _node;
        while (n != null)
        {
            yield return n.Value;
            n = n.Next;
        }
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

}
private class PNode<T> // used internally by PList<T>
{
    public PNode(T value, PNode<T> next) { Value=value; Next=next; }
    public readonly T Value;
    public readonly PNode<T> Next;
}

这是一种简单的单向链表实现，高中时可能会教您编写，但它已经非常有用。您可以使用 Add() 添加项，使用 Tail 删除最后一项，并且由于它实现了 IEnumerable，因此您可以将其与 foreach 或 LINQ 一起使用。

现在，考虑以下代码：

PList<int> A = new PList<int>();
A.Add(7);
A.Add(3);
PList<int> B = A;
A.Add(9);
A.Add(1);
B.Add(3);
B.Add(1);

在内存中，结构如下

不能修改链表中的项意味着您可以将它们视为值类型：如果您将列表传递给函数，您永远不必担心函数会修改您的列表。函数可以随意从列表中添加或删除项，但这些更改不会影响*您的*列表副本。

然而，持久性链表 PList<T> 不如您每天使用的标准 List<T> 好。上面的实现不提供在列表中间的任何位置读取、修改、插入或删除项的方法。我们当然可以添加该功能——我们可以提供在列表中任何位置更改项的*幻觉*——但它会比 List<T> 慢，因为在链表的索引 N 处执行任何这些操作都需要 O(N) 时间。例如，如果我们添加一个索引器，以便您可以编写

B[2] = 5;

为了实现这一点，必须复制前两个项目

此外，在修改项 [N] 之前需要 O(N) 时间来查找它。

最后，计算列表中的项目数量需要 O(Count) 时间。

FVList

Phil Bagwell 的 VList 使用数组链表而不是单个项。它旨在通过以下方式改进持久性链表：

平均 O(1) 时间索引元素（但在列表的远端为 O(log N)）。
O(log N) 时间计算元素（在我的实现中是 O(1)！）。
更紧凑地存储元素。例如，包含 N 个元素的 PList<int> 需要 16*N 字节内存（在 32 位 PC 上），但 RVList<int> 通常需要少于 8*N 字节（大致与 List<int> 相同的内存需求）。此外，VList 更具缓存友好性，因为相邻元素在内存中往往是相邻的；因此，它们速度更快。

理想情况下，数组链表的大小呈指数级增长，因此列表中的第一个数组是最大的。这由下图说明：

VList 的引用是一对值，我称之为“块”和“局部计数”（代码中的 _block 和 _localCount）。例如，图中的“引用 C”由指向块 2 的指针和局部计数 6 组成。因此，VList C 包含 12 个项（块 0 中 2 个，块 1 中 4 个，块 2 中 6 个）。同时，引用 D 的局部计数为 8，因此它包含 14 个项（其中 12 个与 C 共享）。就像链表一样，可以有指向 VList 其他部分的引用。该图显示了四个引用，它们共享三个内存块。

因此，我的 FVList<T> 类表现得很像 PList<T>，但具有更高的性能和更多的功能。FVList 和 RVList 提供完整的 IList<T> 接口，以及其他功能，如 Tail、Push/Pop/Front（用于将 VList 作为堆栈使用）、AddRange、InsertRange、RemoveRange 和 ToArray。

一个 VList 总是以一个大小为 2 的块开始，当创建新块时，它们的大小是前一个块的两倍。理想情况下，索引器*平均*只需要 O(1) 时间（访问随机索引时），因为 50-75% 的列表在前面两个块中，而到达最后几个元素所需的额外 O(log N) 时间对总体运行时间影响不大（只要您访问最后元素的频率不超过访问第一个元素的频率）。在我的实现中，每个 VList 块（由 VListBlock<T> 对象表示）都跟踪所有先前块中的元素总数，因此 Count 属性花费 O(1) 时间。

假设我们再次尝试相同的示例，但使用 FVList 而不是 PList：

FVList<int> A = new FVList<int>();
A.Add(7);
A.Add(3);
FVList<int> B = A;
A.Add(9);
A.Add(1);
B.Add(3);
B.Add(1);

与 PList<T> 一样，FVList<T> 也是一个值类型，因此简单的赋值语句会创建副本。结果如下：

现在，假设我们创建第三个列表，其中包含 { 7, 8, 9 }：

// A contains { 1, 9, 3, 7 }.
FVList<int> C = A.WithoutFirst(3); // Remove 3 items to get { 7 }.
C.Add(8).Add(9);                   // Add 8, then 9 to get { 9, 8, 7 }.

由于 Block0[1] 已经被占用，当我们向 C 添加 8 时必须分配一个新块。向 C 添加 9 后，内存布局如下：

请注意，C 无法知道 Block0[1] 中值 3 是否仍有任何引用存在。在我们向 C 添加任何项之前，变量 A 和 B 可能已经超出范围，但 C 并不知道。因此，C 必须假设值 3 正在使用中并保持不变，创建新数组而不是替换现有值。

另请注意，新块 3 只有两个项目而不是四个；这是因为块大小是前一个块*使用*大小的两倍：C 在块 0 中只使用 1 个项目，所以它的两倍大小是 2。因此，当您与 VLists 进行大量共享和分支时，块往往会变小，更像链表。我相信这是件好事，否则就有可能分配非常大的块，而其中只有一小部分数组条目被使用。

例如，假设我们这样做

FVList<int> D = new FVList();
D.Add(1).Add(-1);            //    { -1, 1 } 
D.RemoveAt(0);               //        { 1 }
D.Add(2).Add(-1);            // { -1, 2, 1 }
D.RemoveAt(0);               //     { 2, 1 }
D.Add(3)                     //  { 3, 2, 1 }

这种访问模式（重复添加 2 并删除 1）是最坏的情况。它实际上迫使 VList 退化为低效的链表

在这种情况下，块大小不会呈指数级增长是件好事，否则会很快浪费大量空间。

事实上，为了防止子列表共享和分叉时出现的某些病态问题，我决定将所有块限制为最多 1024 个项，并且我的 Add() 方法使用了一种技术（在 VListBlockArray.Add 的源代码中记录），以避免保留一个不足 1/3 满的数组（从垃圾回收器的角度来看）。

VList 的“流畅”接口

在开发 FVList<T> 结构时，我注意到 FVList<T> 在与属性一起使用时存在一个问题，因为它是一个值类型。考虑当你尝试向 Foo.List 属性添加内容时会发生什么：

class Foo {
    private FVList<int> v;
    public  FVList<int> List { 
        get { return v; }
        set { v = value; }
    }
}

Foo f = new Foo();
f.List.Add(777); // FAIL

这种对 List 属性的使用是**绝对错误的**，因为它**在运行时没有效果**。为什么？FVList<int> 是一个值类型，所以 List 属性返回列表的*副本*。当你调用 Add 方法时，777 被添加到列表的*副本*中，然后该副本立即消失。

不幸的是，C# 编译器无法检测到此问题（很遗憾，我无法将 [Mutator] 属性应用于 Add() 以使编译器在这种情况下发出错误。）

如果 FVList<T> 只实现了返回 void 的标准 Add 方法，您将不得不使用以下代码来解决这个问题：

Foo f = new Foo();
FVList<int> temp = f.List;
temp.Add(777);
f.List = temp;

因此，我决定通过将返回 void 的方法更改为返回被修改列表的副本，来简化操作。这样，您只需编写

Foo f = new Foo();
f.List = f.List.Add(777); // WORKS!

但是，这种更改也恰好使得列表更易于使用，因为您可以在一行中执行多次修改：

VList<string> Q = new VList<string>("Captain", "Joe");
Q.RemoveAt(1).Add("Kirk").Add("T").Add("James");
// Q = { "James", "T", "Kirk", "Captain" }

我没有为 FWList 和 RWList 实现相同的功能，它们是引用类型，因此不会出现相同的问题。

RVList

FVList 对于普通的 C# 程序员来说有点奇怪，因为项目是添加到前面（索引 0）而不是后面。这就是我创建 RVList<T> 的原因。它与 FVList<T> 相同，只是它的 Add() 方法将项目添加到列表的末尾而不是开头。您可以在 O(1) 时间内将 FVList<T> 转换为 RVList<T>，反之亦然（但项目顺序会颠倒！），并且列表会按您期望的从索引 0 到 Count-1 的顺序枚举。

RVList<T> 不过是列表的一种不同“视图”。这就像你写了一个名为 BackwardList<T> 的包装器，它反转了 List<T> 的元素显示顺序。

RVList<T> 中项目的枚举以“反向”顺序发生，这意味着从索引 0 到 Count 的遍历就像从链表的远端到前端的遍历。我决定借助一种算法来实现枚举，该算法向后搜索单向链表。理想情况下，枚举需要 O(N + (log N)^2) = O(N) 时间，但如果列表已退化为链表，则需要 O(N + N^2) = O(N^2) 时间。相比之下，FVList<T> 的枚举器总是需要 O(N) 时间，因为链表以自然方式遍历。

可以使用临时列表来跟踪需要遍历的块，从而以 O(N) 时间枚举任何 RVList<T>。如果需要，我可能会更改实现。

FWList 和 RWList

如上所示，FVList<T> 有时会浪费内存，并且如果您使用某些修改模式，会产生很长的块链。此外，调用 setter 修改索引 [N] 处的 FVList<T> 至少需要 O(N) 时间——有时更像是 O(Count) 时间。

为了使 VList 真正有用，我认为，有必要有一个不会出现这些问题的可变版本。我决定将其命名为 WList，或“可写 VList”（MList 代表“可变 VList”已被占用），分为 FWList 和 RWList 两种变体（正向和反向 WList）。

当单独使用时，RWList<T> 是标准 List<T> 的直接替代品。以这种方式使用时，它保证总是产生一个呈指数级增长的块链。它可以做到这一点，因为它可以在块中覆盖现有项——它永远不必“分叉”块。

因此，RWList<T> 具有与 List<T> 相同的 Big-O 性能

索引器在读写时平均需要 O(1) 时间。
在列表头部添加或删除项目需要 O(1) 时间。
在索引 K 处插入或删除项目需要 O(K) 时间。
在索引 K 处搜索项目需要 O(K) 时间，如果未找到则需要 O(N) 时间。
枚举列表需要 O(N) 时间。

正如你可能猜到的，RWList<T> 是 FWList<T> 的反向形式。对于 C# 开发，通常首选 RWList<T> 而不是 FWList<T>，因为 Add 方法将项目添加到索引 [Count] 而不是索引 [0]。

当然，与 List<T> 具有相似的 Big-O 性能并不是替换 List<T> 的理由，尤其是 RWList<T> 整体可能更慢（尽管我尚未进行基准测试）。FWList 和 RWList 有用的真正原因是您可以立即将列表——甚至只是列表的一部分——转换为 FVList<T> 或 RVList<T>。此外，一旦完成此操作，您仍然可以像以前一样继续修改 FWList<T> 或 RWList<T>——可变性的幻觉始终得以保留。

在内部，FWList 或 RWList 分为两部分或“两半”：可变部分和不可变部分。当您创建新列表并添加项目时，它是 100% 可变的。当您调用 ToVList() 或 ToRVList() 时，它被标记为 100% 不可变。如果您随后将项目添加到 WList 的末尾，它仍然需要 O(1) 时间，因为您没有更改列表的不可变部分。但是，如果您修改了列表中已设置为不可变的部分，则最多需要 O(N) 时间，因为必须复制许多或所有不可变项目以使其再次可变。

可变项仅由一个 FWList 或 RWList 独占拥有；不可变项可以在不同的 FWList、RWList、FVList 和 RVList 之间共享。当列表从一种形式转换为另一种形式时，列表中的所有项都被标记为不可变。这只需通过增加块的一个名为 ImmCount 的属性，使其与列表中的项数匹配即可完成。在 100% 可变块中，ImmCount 为 0；在完全 100% 可变块中，ImmCount 等于块的 Capacity。

为了说明其工作原理，我们来看一个示例。假设我们创建一个 FWList，其中包含从 0 到 8 的项：

FWList<int> W = new FWList<int>(9);
for (int i = 0; i < 9; i++)
    W[i] = i;

此列表由三个块表示...

我们不调用 ToFVList() 使整个列表不可变，而是使用 WithoutFirst(4) 来获取列表末尾的不可变版本，同时保持前四个项目可变：

FVList<int> V = W.WithoutFirst(4);  // V = { 4, 5, 6, 7, 8 }

（注意：RWList<T> 有 WithoutLast() 而不是 WithoutFirst()。它保持列表的末尾可变而不是开头。）

由于前四个项目仍然可变，我们可以在 O(1) 时间内修改它们。例如，我们可以这样做：

W[3] = 33; // fast

然而，如果我们修改列表中不可变部分的一个项目，WList 将复制它需要复制的块，以修改不可变项目。例如，

W[4] = 444;

产生以下结果

请注意，WList 不支持可变和不可变块的交错。列表中只有头部部分可以是可变的，只有尾部部分可以是不可变的。如果您在索引 Count-1 处修改 WList（或者如果您在索引 0 处修改 RWList），则整个列表被迫变为可变。

我在这里实现了一个优化：如果您正在将 VList 转换为可变 WList，并且 VList 有很多小块（如上面显示的病态链表情况），WList 将尝试将小块合并为更大的块，呈指数级增长，以便 WList 的可变部分比它创建的 VList 更高效。但是，它不会复制超出执行您立即操作所需的块，这可能会限制重构的数量。

如果你怀疑你的 RVList 已经退化成一个长链，你可以使用这个小函数将链重构为一个高效的短链

// Restructures an RVList if it has degraded severely. Restructuring needs O(Count) time.
void AutoOptimize<T>(ref RVList<T> v)
{
    // Check if the chain length substantially exceeds Sqrt(v.Count)
    int bcl = v.BlockChainLength-2;
    if (bcl * (bcl - (bcl>>2)) > v.Count) {
        RWList<T> w = v.ToRWList();  // This is basically a no-op
        w[0] = w[0];                 // Restructure & make mutable
        v = w.ToVList();             // Mark immutable again
    }
}

VListBlock

所有四种 VList 类型都使用通用块类 VListBlock<T>。现在，FVList 和 RVList 显然需要共享大部分相同的代码，并且由于 C# 结构不允许拥有基类，我将管理 VList 的大部分共享逻辑放在 VListBlock<T> 中。在 VListBlock 的源代码中，“标准”列表是 FVList；如果一个方法需要列表作为参数，它会优先选择 FVList 而不是 RVList。在 VListBlock 中，“前端”指链表的头部，尾部块则被称为“先前”块。

当我为可变 VList 添加新算法时，我给它们添加了 Mu 前缀，以区别于为不可变列表设计的算法。由于 FWList 和 RWList 是类，我给了它们一个基类 WListBase<T>，它实现了 IList<T> 并包含大部分通用代码，但最底层的代码位于 VListBlock（或其两个派生类中，这些类用于小列表优化，如下所述）。

块所有权

我想我应该说一些关于块所有权的事情，因为当前的实现比它需要的更复杂。跟踪谁拥有什么是很重要的，因为两个 WList 可以共享相同的块，但最多只有一个 WList 可以拥有每个块。一个 VListBlock 不知道它的所有者，因为它不保留对其拥有的 WListBase 的引用；相反，WListBase 包含一个标志 (IsOwner)，用于指定它是否拥有其头块，并且每个块都包含一个隐式标志 (PriorIsOwned)，用于指定该块是否拥有链中先前的块。如果一个 WList 拥有头块，那么它也拥有所有先前连续的块，其 PriorIsOwned 属性为 true。两个 WList 不可能声称拥有同一个块。即使它们在不同的线程上，也不会发生这种情况，因为 MutableFlag 是使用原子操作 (Interlocked.CompareExchange) 设置的。

MutableFlag 表示一个块由 FWList 或 RWList 拥有，但它不指示谁拥有它。两个不同的 WList 当然可以共享一个设置了此标志的块，但至少其中一个 WList 将只包含块中不可变的项目。因此，WList 依赖于其 IsOwner 标志和 PriorIsOwned 来确定它拥有多少个块。正如我所提到的，PriorIsOwned 是一个“隐式”标志，这是混乱的部分。如果满足以下条件，PriorIsOwned 返回 true：

前一个块是可变的（具有 MutableFlag）。
Prior._localCount > PriorBlock.ImmCount.

这种逻辑依赖于可变和不可变块不能交错的事实，以及在所有先前块都未满之前不会创建新的可变块的事实。正因为如此，可以保证 Prior 列表中的第一个项目是可变的，**或者** Prior 列表完全由不可变项目组成。当 ImmCount 达到块的 Capacity 时，此逻辑会使 PriorIsOwned 返回 false。这是可以的，因为如果一个块充满了不可变项目，那么它和任何先前的块都不能以任何方式修改；因此，谁拥有该块的问题就无关紧要了。

现在，如果有人想，例如，修改源代码以允许在所有先前块未满之前分配新的可变块（例如，为了支持当前不可用的可设置 Capacity 属性），那么此逻辑将不再有效，并且需要引入和管理一个显式标志来指示先前块是否被拥有。

线程安全

线程安全是一个问题。单个列表实例不是线程安全的，但我已努力确保共享相同内存的不同列表是线程安全的。VListBlock.cs 中描述 _immCount 的注释解释了如何处理线程安全，但基本上，_immCount 是唯一需要关注线程安全的字段，因为 VListBlock 中没有其他数据可能同时被两个不同线程修改。

小列表优化

对于某些应用程序，通常会有大量的短列表（两个或更少项）。例如，抽象语法树是 N 叉树，但许多节点有 0、1 或 2 个子节点。因此，我优化了列表中第一个块的内存使用，使其不是一个包含两个项的数组，而是具有两个名为 _1 和 _2 的字段。第一个块由 VListBlockOfTwo 类表示，而所有其他块由 VListBlockArray 类表示（两者都派生自 VListBlock）。VListBlockOfTwo 比相同大小的 VListBlockArray 少使用约 28 字节内存。作为更小尺寸的交换，性能会略有下降，因为某些操作需要虚拟函数调用。如果 FVList 或 RVList 没有项，它根本不使用堆空间。

结论

那么，VLists 有什么用呢？简而言之，它们在函数式算法中作为持久链表的替代品很有用。我将在我的可扩展 C#/boo 编译器项目 Loyc 中使用它们（这个项目还处于非常早期的阶段，顺便说一下，我正在寻求帮助，因为这个项目太庞大了，无法独自完成！）。

我的想法是，Loyc 不仅可以用作编译器，还可以用于 IDE 中提供“智能感知”。现在，为了在您输入程序时提供深入检查，Loyc 将通过许多“编译器步骤”来运行您的代码，以发现深层含义。例如，假设有人编写了一个扩展来支持 C# 中的 C 预处理器。那么，像这样的代码

#define EMPTY(c) internal class c {}
EMPTY(Foo)
EMPTY(Bar)

必须翻译成

internal class Foo {}
internal class Bar {}

这样 IDE 才能知道 Foo 和 Bar 类的存在。Loyc 必须经过一系列这样的转换：

与其在用户每次按下字符时都经历所有这些步骤，我曾想最终以更增量的方式进行，这样就不必在每次按下字符时从头开始重新分词源文件，而只会重新解析那些可能已更改的标记。然后，也许可以通过所有编译器阶段推送一系列“修补”（增量修改），以更短的时间生成重新解析的文件。

要使这远程可行，有必要保留令牌列表的旧副本，可能还有原始 AST 的旧副本。但是，由于整个目的将是*提高*效率，所以实际上花费时间制作令牌列表和 AST 的完整副本可能会适得其反。相反，我想到，只应在需要时按需制作 AST 的部分副本。然后，VList 有助于支持持久性 AST，即只要有人持有对它的引用，旧版本的 AST 就继续存在。

此外，由于这个编译器应该允许第三方修改 AST，因此 AST 不可变且编译器阶段以函数式风格编写可能更好。这样，一个编译器扩展意外地破坏另一个扩展所做的更改的可能性就会降低，并且调试也会更简单。不过，我正在考虑一个折衷方案，因为完全的不可变性可能会损害性能。

如果您能想到 FVList、RVList、FWList 和 RWList 的其他用途，请留下您的想法！

关于依赖关系的说明

希望您不介意：VList 源代码包含依赖于 nunit.framework.dll 的单元测试。此外，还有一个对 Loyc.Runtime.dll 的次要依赖，这是一个用于通用用途的小型简单实用程序集合。最重要的依赖是 CollectionDebugView<T>，这是一个这里描述的微型类，它允许 VList 在调试器中看起来与普通的 List<T> 对象相同。另一个依赖是 Localize.From，一个可插拔的字符串本地化工具。您可以随意将其剥离，只需从源代码中删除所有字符串“Localize.From”的实例即可。

历史

2008年5月：完成 VList 和 RVList。
2009年4月1日：完成 WList 和 RWList。我们称之为 1.0 版本。
2009年12月14日：添加了 LINQ 风格的 Where、Select、SmartSelect 和 Transform 方法。您不需要 C# 3.0 或 .NET 3.0 来使用这些方法（事实上，我**正在** .NET 2.0 中使用它们），但如果您使用的是 .NET 2.0，则需要在 System.Linq 命名空间中手动定义 Func<T,TResult>。或者使用 LinqBridge。
2009年12月14日：将 VList/WList 重命名为 FVList/FWList。