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

DList<T>：循环列表<T>

Qwertie
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.85/5 (14投票s)

2014年8月13日

LGPL3

5分钟阅读

viewsIcon

24974

为我的“列表三部曲”系列创建 AList 数据结构一定花费了数百小时。 DList 是一个极其简单的结构，但在某些情况下可以大大提高你的插入/删除速度。

引言

为我的 列表三部曲系列 创建 AList<T> 数据结构一定花费了数百小时。 DList<T> 是一个极其简单的结构，但在某些情况下可以大大提高你的插入/删除速度，而不会对索引器等其他操作的性能产生不利影响。

DList<T> 是一个“循环缓冲区”。循环缓冲区是一种内存区域，组织起来可以让你高效地在两端添加或删除项，并且通常用于实现队列（它被称为“循环队列”）。

标准的 List<T>，如图所示，是一个包含数组引用 (T[]) 和一个“size”变量的对象，该变量指示数组中有多少项当前正在使用。

List<T> diagram

当你添加项时，列表也会自动扩展。数组从大小 4 开始，当添加第五个项时，会扩展到 8，方法是创建一个新数组并将现有的 4 个项复制到新数组中，然后再添加第五个项。

在 List<T> 中，正在使用的项始终沿着数组的“左侧”（开头）排列。如果你删除第一个项，其余的项将逐个向左移动。当列表很小时，在现代硬件上此类操作非常快，但如果列表足够长并且你执行了足够的插入/删除操作，那么使用你的程序的人可能会开始注意到。

DList<T>

我创建了一个类似的类，名为 DList<T>。它与 List<T> 几乎相同，只是它有一个额外的整数，用于跟踪“起始位置”，即列表中“第一个”项的索引。

DList 中的 D 代表“deque”或双端队列，因为 DList 实现 IDeque<T>，并且非常适合用作双端队列。但它的名字是 DList 而不是 Deque，以强调它还可以做所有常规 List<T> 能做的事情。

起初，项会添加到数组的左侧，与 List<T> 的方式相同。假设你向 DList<T> 添加了五个项，然后又添加了两个（共七个）。

DList<T> diagram

如果你然后删除前五个项，_start 引用将增加到 5；无需移动任何其他项。

DList<T> diagram

如果你在末尾添加 3 个额外项，那么一个大小为 8 的数组肯定有足够的空间容纳这 3 个新项，但新项必须“绕过”到数组的开头。

DList<T> diagram

从外部看，DList<T> 的行为与 List<T> 完全相同，但由于 DList<T> 使用了所谓的循环缓冲区概念，因此在列表开头或接近开头处添加或删除项时，它的速度要快得多。无论何时添加或删除项，DList<T> 都会检查与列表开头和结尾的距离，并选择最佳的插入位置。例如，如果一个 DList<T> 有 100,000 个项，而你在索引 40,000 处插入某项，则前 40,000 个项将被移到左侧以腾出新项的空间，因为这比将最后 60,000 个项向右移动要稍微快一点。

因此，在 DList<T> 中，在随机位置插入和删除项的速度几乎是 List<T> 的两倍，而在列表的开头或结尾插入或删除项的速度是 O(1)，而在中间插入或删除项的速度相同。缺点是读取特定索引处的项稍微复杂一些。你请求的索引必须先被“内部化”，然后才能使用。

// Approximization. The real code is more...layered.
public T this[int index]
{
  get {
    if ((uint)index >= (uint)_count)
      throw new ArgumentOutOfRangeException(...);
    return _array[Internalize(index)];
  }
  Set {...}
}
int Internalize(int index)
{
  index += _start;
  if (index >= _array.Length)
    return index - _array.Length;
  return index;
}

有利的一面是，你可以通过使用 foreach 进行枚举而不是使用索引器来避免这种轻微的额外开销。

为了方便起见，DList<T> 还包含一些额外功能。它具有 First、Last 和 IsEmpty 属性，有一个 Resize(int) 方法可以将列表的大小调整到特定值，还有一个 Slice(int start, int count) 方法，该方法返回 DList 部分内容的“视图”。与 AList<T> 的切片一样，你可以通过切片修改 DList；例如，此代码...

DList<int> list = new DList<int> { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
ListSlice<int> slice = list.Slice(3, 4);
for (int i = 0; i < slice.Count; i++)
    slice[i] = -1;

将项 30、40、50 和 60 替换为 -1。

InternalDList<T>

InternalDList<T> 是 DList<T> 的一个变体，用于其他数据结构。它与 DList<T> 相同，只是有两点不同。首先，它是一个 struct 而不是一个 class，因此在 64 位机器上节省了一个堆分配和 16 字节内存。其次，如果你请求一个越界的索引，它不会抛出异常；它会改用 Debug.Assert 进行检查。

AList 的叶节点包含一个单独的 InternalDList<T> 结构。DList<T> 本身也由一个单独的 InternalDList<T> 结构组成（除此之外别无他物）。

如果你不明白 InternalDList 的用途，请阅读 我关于 InternalList 的文章。InternalList<T> 是相同的概念，只是没有“循环队列”部分。

基准测试

在我的列表三部曲系列文章的最后，我进行了一系列基准测试，并将 DList<T> 加入其中。

这是其中一项基准测试结果。

Results
Results

这表明，对于包含 1000 多个项的列表，DList<T> 的随机插入速度比 List<T> 快两倍。有关更多基准测试结果，请参阅 列表三部曲第三部分（底部附近）。

下载！

我很高兴地宣布一个名为 “LoycCore” 的新 NuGet 包，其中包括 DList、AList、其他数据结构以及各种其他便捷的功能，包括我过去发表过文章的大部分内容。我还创建了一个 Loyc Core 新网站。

DList<T> 是 Loyc.Essentials.dll 的一部分。源代码 位于 GitHub 上。原则上，可以从该程序集中提取 DList<T> 和 InternalDList<T>，但这需要一些工作，因为它们依赖于 Loyc.Essentials.dll 中的接口和其他代码。

历史

  • 几年前：编写了 DList<T>
  • 2014 年 8 月 13 日：发布了本文
© . All rights reserved.