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

更好的排序列表和字典

Trent Tobler
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.88/5 (16投票s)

2011年10月28日

BSD

9分钟阅读

viewsIcon

68161

downloadIcon

1092

一个基于内存的 B 树 ICollection 和 IDictionary 实现。

引言

大约一年前，我需要一种动态数据集合类型，以便根据排序顺序进行快速键查找。在评估了 .NET 的 SortedDictionary 提供的功能，并四处寻找可用的东西后，我决定基于内存中的 B 树集合编写自己的排序数据集合版本。我最近再次需要这个功能，于是决定将代码发布给其他人。

更新

当我发布最初的代码和文章时，我曾认为我能够处理重复键。在我开始尝试在自己的项目中使用这段代码后，我发现重复项的处理功能不可用。

在添加管理重复项的功能时，我发现最初的接口有点难以理解，主要是因为我使用的名称。我决定更新接口，使用更能描述它们功能的名称。

我还清理了一下代码：添加了更多注释来解释逻辑，并试图使集合和字典之间的实现更接近（有很多复制代码；我评估了重构它们，但决定暂时不处理）。

背景

在 .NET 中，我通常看到的“首选”查找数据结构是 Dictionary<K,V> 泛型集合。虽然它速度非常快（查找、插入和删除为 O(1)），但它缺少任何排序约束。如果您需要，例如，在不断变化的大量数字集合中找到值大于或等于 52941 的下一个 10 个键，那么您别无选择，只能执行昂贵的集合扫描（平均性能为 O(N*M)，其中 N 是项目数，M 是需要执行扫描的次数）。

通常，为了解决这类问题，我们会使用平衡树结构：红黑树（2-3-4）树、2-3 树。我决定尝试实现 B 树，一种通常用于文件 I/O 的结构，但正如我发现的，它的性能与平衡二叉树结构相当。实现自己的解决方案还允许我添加一些我发现非常实用的功能。

如果 .NET 的 SortedDictionary<K,V> 泛型集合实现了我最初需要的功能，“上限”和“下限”迭代，我可能永远不会尝试实现自己的解决方案（或者，也许它确实支持这一点；我个人找不到如何利用该功能，如果它确实存在的话）。当我发现我的实现与 .NET 的排序字典相比，在可比操作下快了 20-30% 时，我感到有些惊讶。

使用代码

有两个接口，两个实现这些接口的类，以及一个测试工具/NUnit 测试程序集。**注意**：我在家里使用 Visual Studio Express 进行开发，因此有时必须创造性地调试问题。大部分工具只是增加了这种能力。通常，如果我们能够附加到单元测试本身，那么大部分工具将是不必要的。无论如何，它是一个有用的基准测试工具。

第一个数据结构是简单的“集合”：BTree<TKey>。该类具有以下可用功能：

  • 它实现了 ICollection<T> 接口。
  • 它在插入或删除项目时，根据构造时提供的键比较器，高效地将集合保持排序状态 - 插入和删除均为 O(log N)。
  • 它能够高效地提供基于任何边界的枚举，无论是升序还是降序 - O(log N) + O(K)（对于第一个元素之后的 K 个元素）。
  • 它能够（相对）高效地在集合中提供特定索引处的值 - O(log N)。
  • 支持强制唯一约束，或允许重复项。

下面有一个代码示例，演示了简单的用法，但我将介绍一些接口方法，并更详细地讨论实现细节和一些有趣的应用。

关于实现的一个需要注意的点：它使用计数 B+ 树结构。这意味着叶节点包含重建列表所需的所有信息，存储为双向链表。中间节点和根节点存储第一个键以及其子节点列表中的所有项目的总计数。

bool AllowDuplicates

我将此属性添加到了之前发布的原始代码中。集合和字典版本的排序集合的接口是只读的，但是，在 BTree<T> 实现中没有理由必须是只读的。我确实添加了一个（可能过于武断的）约束，即如果集合中有任何元素，则不能将其从 true 改为 false。如果存在特定需求，应该可以轻松地修改代码并放宽此约束；可能需要一个“HasDuplicates()”的计算来确保如果集合指示不允许重复项，那么它实际上不包含重复项。如果放宽此条件，并且当 AllowDuplicates 为 false 时集合中存在重复项，那么所有与重复值相关的操作将回退到不确定的行为。

我首先编写了 BTree<T> 类的行为，并保持其简单。我实际上不需要它具有任何歧义分辨率，所以没有。如果您添加重复项，它们将以任意顺序枚举。

BTreeDictionary<T> 实现包含三个偏置属性来解决歧义：InsertBias、LookupBias 和 RemoveBias。逻辑使用这些属性值的符号来确定在添加、查找或使用基于键的操作删除值时，是偏向第一个重复项还是最后一个重复项。这使得集合可以作为与每个键关联的值的队列（FIFO）或堆栈（LIFO）系列。

IEnumerable<> WhereGreaterOrEqual, WhereLessOrEqualBackwards

这两个方法是基于范围搜索的基石。它们能够高效地让您查看集合中的当前结构，并从特定的枢轴键值开始，向前或向后枚举集合中的项目。例如，要获取排序字典中键在 0.4 和 0.6 之间的所有标签，您可以使用以下方式：

BTreeDictionary<double, string> data = new BTreeDictionary<double, string>();
while( true )
{
  foreach( var item in ReadLatestData() )
    data.Add( item.Key, item.Value );

  // Search for values with the "error" tag, between the values of 0.4 and 0.8.
  var errorKeys =
  (
    from item in data.WhereGreaterOrEqual( 0.4 )
    where item.Value == "error"
    select item.Key
  ).TakeWhile( item => item < 0.8 );

  ProcessErrors( data, errorKeys.ToArray() );
}

FirstIndexGreaterThan()、LastIndexLessThan()、At()、RemoveAt()、ForwardFromIndex()、BackwardFromIndex()、SetValueAt()。

由于此实现存储了计数信息，因此在执行获取或返回感兴趣项的索引的操作时（而不是使用键值），它是（相对）高效的。BTree<> 类可以相当容易地适应，以提供一个无序列表，具有 O(log N) 的随机访问列表，包括在索引处进行插入和删除（相比之下，List 提供在末尾进行 O(1) 插入，或在随机点进行 O(N) 插入）。无论如何，基于索引的操作对于排序集合也很有用；例如，要获取 0.4 和 0.8 之间（包含）的项目总数，可以使用 data.FirstIndexGreaterThan(0.8) - data.LastIndexLessThan(0.4) 来获得 O(log N) 的范围大小值。

IsReadOnly

在 DLL 的 1.1 版本中，我添加的另一个功能是能够动态地将集合标记为只读。这在枚举期间可能非常有用。您可以将 IsReadOnly 设置为 true，进行枚举，然后将其设置回 false，以确保如果在枚举过程中有人尝试修改集合，它将引发异常。在修改集合后继续枚举集合可能会导致一些“乐趣”。它可能 90% 的时间都能正常工作，但偶尔会导致崩溃、跳过现有元素或返回之前已经返回过的元素。我没有在枚举器本身添加任何版本检查，但如果您需要这种级别的安全性，这应该很容易进行调整。

Dictionary 中的一些接口方法和类实现可能看起来缺失，直到您意识到字典上的 Keys 属性提供了该功能。当这些值可以很容易地通过字典上的 Keys 属性获得时，我没有添加（通常是冗余的）接口和实现成员。

下面的代码示例说明了一个简单问题的解决方案：假设您需要能够添加一个数字，随时请求中位数或 Kth 值的代码。使用 BTree<K> 集合，可以轻松实现此类代码：

class AnyKthNumber
{
    BTree<double> numbers = new BTree<double>();
    
    public void Add( double value )
    {
        numbers.Add( value );
    }

    public double GetKth( int index )
    {
        return numbers.At( index );
    }

    public double GetMedian()
    {
        if( 1 == ( numbers.Count & 1 ) )
        {
            // For odd counts, median is exactly the middle item.
            return this.GetKth( ( numbers.Count - 1 ) / 2 );
        }
        else
        {
            // For even counts, median is average of two middle values.
            int k = numbers.Count / 2;
            return 0.5 * ( this.GetKth( k - 1 ) + this.GetKth( k ) ); 
        }
    }
}

虽然您可能可以使用 List 或 SortedList 来完成，但如果同时不断添加新随机值并不断查询 Kth 或中位数，这种实现将存在严重的性能问题。

第二个数据结构 BTreeDictionary<TKey,TValue> 提供了以下功能：

  • 它实现了 IDictionary<K,V> 泛型接口。
  • 它高效地将所有键保持排序状态，具有与上述更简单的 BTree<K> 类型相同的性能特征，包括获取 Kth 键/值元素的能力。
  • 支持强制唯一键约束，或支持重复项。
    • 某些操作可能产生不确定的结果。我添加了一些属性来精确定义如何解决不确定性。

扩展上面的代码示例，如果您想为每个数字记录一些标签，并检索这些标签以及 Kth 元素或中位数，也可以通过简单的修改来实现。

关注点

正如我上面指出的，我惊讶地发现我的代码与 SortedDictionary<K,V> 集合类型相比，性能更好。对于 1,000,000 次添加，然后是 1,000,000 次删除（对随机、排序或无序数据），我在我的机器上获得的计时如下：

集合类型 随机数字 顺序数字 反向顺序数字
Dictionary<K,V> 0.5s 0.5s 0.5s
SortedDictionary<K,V> 5.7s 2.3s 2.9s
BTreeDictionary<K,V> 4.2s 2.4s 2.2s
BTree<K> 2.3s 1.8s 2.0s

我相信与 SortedDictionary 相比性能的提升很大程度上可以解释为 B 树策略具有更好的缓存局部性（平均每个节点包含 50-100 个项目，作为简单的数组），并且 GC 性能更好（它只在根节点和中间节点存储指向子节点的指针，因此与存储每个项目键值的左右子节点相比，内存压力更小）。有趣的是，对于我测试的 32 位整数键，当节点容量从 10 增加到 200 时，性能在约 120 的节点容量标记处达到峰值。我本来期望它在较低的数字处达到峰值，考虑到平均而言，它需要移动节点中的一半项目来为新键腾出空间。显然，移动额外的 20-30 个项目比较小节点中额外的分支和内存分散的开销要快。

一位评论者建议使用 SortedList。它在随机测试中几分钟后仍未返回，因此我没有包含它。另外，请注意，如果您不需要处理不断变化的数据，这些指标可以通过简单的排序列表以摊销的方式得到更好的结果。这些数据结构是针对在向集合中添加新项目或从中删除项目时能够增量执行操作而优化的。

历史

  • 2011-10-27 : 初始公开发布。
  • 2011-10-29 : 1.1 版本；重构了接口，增加了对重复键的支持，进行了少量代码调整。
© . All rights reserved.