SortedBucketCollection：一个内存高效的 SortedList，接受具有相同键的多个项目

目录

介绍

使用SortedBucketCollection

创建一个SortedBucketCollection

将项添加到SortedBucketCollection

遍历SortedBucketCollection中的所有项

访问一个特定项

移除项

访问一天的所有项

SortedBucketCollection的实现

真的需要一个新的集合吗？

泛型参数是什么？

要实现哪些接口？

内部数据结构

需要哪些属性？

需要哪些方法？

如何实现IEnumerable

多线程安全

单元测试

SortedBucketCollection与SortedDirectory的性能

SortedBucketCollection的代码

最大优势

下载源代码 - 3.7 KB

我正在编写一个供自己使用的会计软件，并且需要每天存储一些财务交易。存储它们的一种简单方法是Dictionary，但这允许每天仅存储一笔交易，但是我需要每天存储几笔交易。这可以通过使用Dictionary来实现，它有一个很大的缺点，它会创建数千个List，因为我需要使用许多这样的集合，而不仅仅是一个。

我改写了SortedBucketCollection。我假设每个TKey1都有一个存储桶，每个存储桶可以包含几个具有唯一Tkey2的条目。但是，实际上并没有桶，只是一个链表，它不需要像List那样的任何内存空间。

对于我的财务应用程序，我这样使用它：SortedBucketCollection。TKey1是交易日期，Tkey2是交易编号。仅使用唯一的交易号作为键是不够的，当需要一天的交易时搜索或排序所有交易将太耗时。

本文涵盖了几个方面：

• 如何使用SortedBucketCollection
• SortedBucketCollection的设计和代码
• 编写自己的集合时要考虑的事项

以下是如何使用SortedBucketCollection的完整代码：

using System;

namespace SortedBucketCollectionDemo {

  public record FinanceTransaction
  (int No, DateTime Date, string Description, decimal Amount);

  class Program {
    static void Main(string[] args) {
      //Constructing a SortedBucketCollection
      var transactions = 
        new SortedBucketCollection
                                  (ft=>ft.Date, ft=>ft.No);
      var date1 = DateTime.Now.Date;

      //Adding an item to SortedBucketCollection
      transactions.Add(new FinanceTransaction(3, date1, "1.1", 1m));
      transactions.Add(new FinanceTransaction(1, date1, "1.2", 2m));
      transactions.Add(new FinanceTransaction(0, date1, "1.3", 3m));
      var date2 = date1.AddDays(-1);
      transactions.Add(new FinanceTransaction(1, date2, "2.1", 4m));
      transactions.Add(new FinanceTransaction(2, date2, "2.2", 5m));

      //Looping over all items in a SortedBucketCollection
      Console.WriteLine("foreach over all transactions");
      foreach (var transaction in transactions) {
        Console.WriteLine(transaction.ToString());
      }

      //Accessing one particular transaction
      var transaction12 = transactions[date1, 1];

      //Removing  a transaction
      transactions.Remove(transaction12!);

      //Accessing all items of one day
      Console.WriteLine();
      Console.WriteLine("foreach over transactions of one day");
      Console.WriteLine(date1);
      foreach (var transaction in transactions[date1]) {
        Console.WriteLine(transaction.ToString());
      }
    }
  }
}

SortedBucketCollection类的定义：

public class SortedBucketCollection: 
  ICollection, IReadOnlySortedBucketCollection
  where TKey1 : notnull, IComparable
  where TKey2 : notnull, IComparable
  where TValue : class {

SortedBucketCollection支持两个键。第一个用于将TValue类型的存储项分组在一起。第二个键用于唯一标识该组（存储桶）中的项目。

SortedBucketCollection支持ICollection并可用作任何其他集合。不幸的是，无法实现IList，它允许根据项目在列表中的位置访问项目。SortedBucketCollection无法有效地实现这一点。

SortedBucketCollection的构造函数如下所示：

public SortedBucketCollection(Func getKey1, Func getKey2) {}

它有两个参数，代表getKey1和getKey2。我不喜欢SortedList和SortedList中键和项都需要传递，因为大多数时候，键已经是项的一个属性。为了改进这一点，我添加了这两个允许查找Key1和Key2在项目中的委托。

使用构造函数：

var transactions = 
  new SortedBucketCollection (ft=>ft.Date, ft=>ft.No)

在演示中，FinanceTransaction有一个日期和一个交易编号，它们用作两个必需的键。

public record FinanceTransaction(int No, DateTime Date, string Description, decimal Amount);

添加项变得非常简单：

transactions.Add(new FinanceTransaction(uniqueNo++, date, "Some remarks", 10.00m));

不需要将键作为单独的参数给出。SortedBucketCollection已经知道如何找到键了。它采用第一个键、一个日期并检查是否已经有任何具有相同日期的项。如果没有，它只会在该日期下添加新项。如果已经有一个，SortedBucketCollection则检查新项应该在现有项之前还是之后。在Add()完成后，将这两项存储在正确排序的链表中。

注意：SortedBucketCollection只需要增加单个SortedDirectory的存储容量，这种情况很少发生。使用这种Dictionary方法，数以千计的列表必须不断增加它们的容量（即，将内部数组复制到更大的数组中）。

与任何其他集合一样，这里没有什么特别之处，SortedBucketCollection支持IEnumerable(TValue)：

foreach (var transaction in transactions) {
  Console.WriteLine(transaction.ToString());
}

输出如下：

FinanceTransaction { No = 1, Date = 07.11.2021 00:00:00, Description = 2.1, Amount = 4 }
FinanceTransaction { No = 2, Date = 07.11.2021 00:00:00, Description = 2.2, Amount = 5 }
FinanceTransaction { No = 0, Date = 08.11.2021 00:00:00, Description = 1.3, Amount = 3 }
FinanceTransaction { No = 1, Date = 08.11.2021 00:00:00, Description = 1.2, Amount = 2 }
FinanceTransaction { No = 3, Date = 08.11.2021 00:00:00, Description = 1.1, Amount = 1 }

var transaction = transactions[new DateTime(2021, 11, 07), 1];

transactions.Remove(transaction);

在Dictionary中，人们将使用键来删除该项目。SortedBucketCollection可以根据给定的项找出键。

var date1Transaction1 = transactions[date1];

这是SortedBucketCollection真正闪耀的地方。可以将所有交易存储在一个List中，并使用Linq查找具有特定日期的所有交易，然后根据transaction.No对它们进行排序 。这将是一个相当耗时的操作。在编写我的财务应用程序时，我发现我需要经常访问每天的交易，这就是我写SortedBucketCollection的原因。

很少有人需要写自己的集合，这意味着这是一项没有多少人具备的技能。在本章中，我将展示编写集合时必须考虑的所有重要方面。当然，这需要写很多细节。如果你觉得这很无聊，请停止阅读这里。

DotNet和Github已经提供了大量的集合。如果有一个可以满足您的需求，请检查Stackoverflow。

在SortedBucketCollection的例子中，我发现了两个建议：

1. 使用SortedList。这样做的问题是它需要太多的内存。就我而言，我的应用程序中的100个财务账户中的每一个都有自己的SortedBucketCollection，我希望能够覆盖1000天。使用这种方法，我需要超过 100'000个SortedList，这是太多的开销。
2. Linq提供了Lookup集合，它可以在一个键下存储许多值。不幸的是，它是只读的。要创建一个Lookup集合，必须在构造函数中传递一个IEnumerable作为参数，这就是Lookup将包含的所有数据。之后无法添加或删除项目。

.NET中的大多数集合只有1个键，但我想要2个键，一个用于将值组合在一起，另一个用于标识该组中的一个特定项。如果需要删除单个项，则需要这样做。

public class SortedBucketCollection: 
  ICollection, IReadOnlySortedBucketCollection
  where TKey1 : notnull, IComparable
  where TKey2 : notnull, IComparable
  where TValue : class {

键用于排序，因此它们需要实现IComparable并且不能是null。

我更喜欢TValue成为一个类，而不是一个避免不必要地复制其内容的struct。

我本来想实现类似IDictionary的东西，但这不是一个真正的选择，因为我需要两个键。IList怎么样？也不可能，因为它允许transactions[date]=xyz;我不想允许这样的事情。所以我能找到的最好的接口是基于IEnumerable的ICollection。

您可能已经注意到，我编写了一个新的接口IReadOnlySortedBucketCollection，其中包含只能从SortedBucketCollection中读取数据的属性和方法。在我的应用程序中，我想非常清楚只有持有集合的类才能更改其内容，其他类只能读取。我的Account类可以访问其他类的集合，如下所示：

public IReadOnlySortedBucketCollection Ledgers => ledgers;
readonly SortedBucketCollection ledgers;

所有数据都存储在一个集合SortedDirectory中，其中包含BucketItems：

private class BucketItem {
  public readonly TValue Item;
  public BucketItem? Next;

  public BucketItem(TValue item, BucketItem? next) {
    Item = item;
    Next = next;
  }
}

BucketItem有一个TValue类型的Item，它是实际存储的数据，并且有一个链接到下一个具有相同Key1但不同Key2的BucketItem。请注意，实际上没有Bucket对象。

readonly SortedDictionary buckets;

buckets为每个唯一的TKey1值保存一个BucketItem，如果有几个项目具有相同的TKey1值，则该buckets是链表的头。

IList需要Count。它告诉存储了多少项而不枚举所有项。该IsReadOnly接口也需要，我将其始终设置为false。我添加了Key1Count，它告诉我们使用了多少种不同Key1的东西。

SortedBucketCollection提供两个索引：

1. public IEnumerable this[TKey1 key1]允许访问所有具有Key1==key1.的项。请注意，它返回一个可枚举的，而不是一个列表，以避免花费时间和内存来创建一个。
2. 如果该组合键存在，则public TValue? this[TKey1 key1, TKey2 key2]返回1项。

如果你的集合实现了一个接口，VS会为你添加所有需要的方法。就我而言，它们是：

ICollection要求：

public void Add(TValue item) {'''} 

public bool Remove(TValue item) {

public void Clear() {

public bool Contains(TValue item) {...}

public void CopyTo(TValue[] array, int arrayIndex) {...}

有时，接口要求有某种我们可能不想用于我们的集合的方法。我们不能把它扔掉，但我们可以抛出new NotSupportedException();正如我对CopyTo()所做的。

IEnumerable要求：

public IEnumerator GetEnumerator() {...}

我添加的灵感来自IDictionary：

public bool Contains(TKey1 key1) {...}

public bool Contains(TKey1 key1, TKey2 key2) {..}

IEnumerable定义如下：

public interface IEnumerable: IEnumerable {
   IEnumerator GetEnumerator();
}

public interface IEnumerator: IEnumerator, IDisposable {
  T Current { get; }
}

public interface IEnumerator {
  object Current { get; }
  bool MoveNext();
  void Reset();
 }

在.NET的早期，IEnumerable集合的实现很复杂，需要编写一个额外的类，例如SortedBucketCollectionEnumerator，其实现IEnumerator然后将由GetEnumerator()返回值。

随着C#关键字的引入yield，事情变得更容易了，但仍然相当混乱，因为人们只能使用yield来创建方法返回IEnumerator。我们大多数人可能从未这样做过，因此不熟悉yield。

下面是如何编写一个GetEnumerator()实现的代码：

public IEnumerator GetEnumerator() {
  var versionCopy = version;

  foreach (var keyValuePairBucketItem in buckets) {
    var bucketItem = keyValuePairBucketItem.Value;
    yield return bucketItem.Item;

    if (versionCopy!=version) {
      throw new InvalidOperationException();
    }

    while (bucketItem.Next is not null) {
      bucketItem = bucketItem.Next;
      yield return bucketItem.Item;

      if (versionCopy!=version) {
        throw new InvalidOperationException();
      }
    }
  }
}

请注意，它GetEnumerator()返回一个IEnumerator，但没有在代码中创建！

编译器将GetEnumerator()的主体翻译成一个新的隐藏类，我们来命名它为SortedBucketCollectionEnumerator。它实现IEnumerator。

基本上，我的GetEnumerator()包含两个循环：

foreach (var keyValuePairBucketItem in buckets) {
  var bucketItem = keyValuePairBucketItem.Value;
  while (bucketItem.Next is not null) {
  }
}

一个集合通常只需要一个循环，枚举所有键。由于SortedBucketCollection使用两个键，因此需要先循环遍历每个TKey1，然后在该循​​环中遍历存储桶中的每个TKey2。

对于找到的每个键，都会编写以下语句：

yield return item;

SortedBucketCollection.GetEnumerator()像这样被消费：

foreach (var transaction in transactions) {
  Console.WriteLine(transaction);
}

C#编译器将其翻译成如下内容：

using(var sortedBucketCollectionEnumerator = transactions.GetEnumerator()) {
  while (sortedBucketCollectionEnumerator.MoveNext())   {
    Console.WriteLine(sortedBucketCollectionEnumerator.Current);   
  } 
}

当sortedBucketCollectionEnumerator.MoveNext()第一次被调用时，它会运行基于SortedBucketCollection.GetEnumerator()主体生成的代码，直到找到第一个yield语句，然后停止并返回该项。当sortedBucketCollectionEnumerator.MoveNext()再次被调用时，它会在语句之后继续下一行yield并再次运行直到下一个yield，停在那里并返回该项。重复此操作，直到找不到更多yield语句，然后foreach完成。

.NET集合通常不是多线程安全的，这意味着两个线程不能同时操作集合。但是它们通常会检测一个线程是否正在枚举集合，而另一个或同一个线程是否同时更改集合的内容。这是通过version字段完成的。每次添加或删除项目时，version都会递增。正如您在GetEnumerator()中看到的，在开始时保存当前version，在每次yield之后，有一个测试来确保version仍然具有相同的值。

对于您编写的大多数代码，您还应该编写单元测试。在VS中，将一个MSTest Test Project添加到您的解决方案中。请谷歌如何在VS中编写单元测试，只需记住调用每个方法并在每次调用后检查所有属性是否具有预期值。

编码和测试完成后，应该进行一些性能测试。如何做到这一点，请参阅：benchmarkdotnet.org

在这个例子中，SortedBucketCollection与SorteDirectory