.NET 3.5中处理100万以上有序集合的推荐数据结构

Question

我的数据结构知识已经很陈旧了，说实话这从来不是我最擅长的领域。

现在我们要开发一个类似于队列的组件，具有以下要求：

1. 必须能够排队、出队并通过关键字查找特定项。
2. 每个项都将是一个由另一个类作为关键字的结构或类，具有 5 个不同的属性，类别类似。假设类似于：MasterCategoryId、ChildCategoryId、TimeId、PriorityId、GroupId。
3. 它必须是一个排序集合。
4. 通常情况下，该集合将包含从 5k 到 10k 个对象，但为了考虑最坏情况，我们正测试当前原型以容纳大约一百万个对象。
5. 目前它不支持多线程。
6. 大约有 90 或 95% 的项目（队列）将在创建组件时发生，但组件被用作树，也就是说，我们将从集合中出队最后一个项目，对其进行计算，然后将其结果报告给其父级，该父级可能已经存在于集合中，也可能不存在。如果不存在，则用于查找父级的队列方法将必须插入该项。
7. 由于该组件类似于处理队列，因此在出队所有内容后，集合将为空。

我想这总结了一下。所以，显然一个单一的列表或有序列表是不可行的，因为每次我们向集合中添加或删除对象时都会对其进行排序，而在包含一百万个对象的单个集合中执行此操作很慢。

我们过去测试了几种方法，例如链表，它们在排队方面证明很快，但在查找项目方面很慢（因为我们确实有这种情况）。

现在我们想到了一种结构，类似于

SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, ..

你明白了。

这种分组级别的处理方式是一种较为理想的方法，每个集合大小相对较小(每个字典约为300个项目)。

因此，对于第一层级别，我们将使用SortedDictionary，其键是每个主要类别的ID，而值将是一个SortedDictionary，其键是子类别的ID...以此类推。

目前，我们已经测试了100、1,000、10,000、100,000和1,000,000项。

对于较小的范围，最高可达100k，解决方案速度非常快。即使对于最多达到300k的情况，它也可以在不到一秒的时间内进行排队/出队/查找，这实际上已经超出了我们将要处理的80-90%的场景。

当处理一百万时，速度会变慢，排队整个过程需要大约3-4秒钟，排队全部完成需要长达10秒的时间。

所以，我的问题是：

1. 是否有更适合我们特定情况的集合或方法？ 2. 我以前从未在集合中处理此数量的项目。这些时间对于如此高的数字是否合理？我之所以问是因为我读过一些人的推文，他们在像MSMQ或NserviceBus这样的东西上进行了200k次/秒的操作(我知道这与此无关，只是想了解和比较我的结果)。 3. 我在原型中使用的对象只是模拟类，仅有组合对象键和单个属性。当我使用真实类时，我的结果会受到影响吗？我猜想不会，因为框架所要做的就是添加对该对象的引用，但我只是想确认一下，因为像我说的那样，数据结构从来都不是我的强项。 4. 如果我想要为这个多线程准备，我需要考虑哪些问题？

谢谢。

- GR7

---

把英语翻译成中文。只返回翻译后的文字：+1 表示翻译准确详细。 - Jigar Pandya

当第一个笨蛋喊出“使用C++”时，我已经准备好打开一瓶塞拉尼瓦啤酒了。 - Winfield Trail

也许可以考虑一下这个链接：http://msdn.microsoft.com/library/ms379572.aspx。它是关于二叉搜索树的，包含了示例和大量的数据结构信息。 - ralf.w.

也许你可以包含你正在使用的测试代码？ - kfuglsang

也许是@kfuglsang，也许吧。我宁愿不这样做，因为即使它只是一个原型，没有任何业务信息或字段名称，但它仍然与工作有关，我不确定这样做是否合适。 - GR7

Answer 1

一些注释和通用建议（很抱歉我没有时间自己测试）：

我认为您的一般方法 - 嵌套（排序）字典 - 是正确的。 我经常使用类似的结构，满意度高 - 不是出于性能原因，因为我的情况总是很小，而是出于清晰度和灵活性。

在您的情况下，它还解决了性能问题之一，因为排序（插入和删除时）需要时间，而较小的（子）字典显然排序更快。

是的，将类实例用作值（或键）仅使用引用，因此在这方面，您的类具有什么大小或结构并不重要。

删除（和添加）所需的时间增加可能是由每次删除（或添加）项时执行的重新排序引起的（主要是）。

关于添加项的性能：

如果您的情况使您能够按升序排序方式向字典提供项目，则可以考虑切换到SortedLIST而不是SortedDICTIONARY，因为在列表中添加项是O（1），而不是O（log n），如果新项将最终出现在已排序集合的末尾。

集合具有初始容量 - 保留项目的空间。将项目添加到集合中超出当前容量会导致（a）增加集合的容量值；（b）重新分配新容量的空间；（c）将值从原始（小）存储复制到新存储中。因此，如果您对集合的大小有一些想法：请使用适当的容量初始化集合。这在SortedDictionary中还不可能，但是sortedLIST支持该功能。

关于删除项的性能：

您可能要考虑使用一种方法，该方法使用自定义类包装排序的集合，使其不“真正”删除项目（从而避免重新排序），直到整个集合为空为止。

总之，请尝试以下内容（使用vb语法；我相信您可以将其转换为C＃，C +或任何您希望使用的语言）。

Public Class MySortedCollection(Of myKeyType, myValueType)

  Public Sub New(Optional myCapacity As Integer = 0)

    If myCapacity <= 0 Then
      MyValues = New SortedList(Of myKeyType, myValueType)
      ValidItems = New Dictionary(Of myKeyType, Boolean)
    Else
      MyValues = New SortedList(Of myKeyType, myValueType)(myCapacity)
      ValidItems = New Dictionary(Of myKeyType, Boolean)(myCapacity)
    End If

    LiveItemsCount = 0
  End Sub

  Private MyValues As SortedList(Of myKeyType, myValueType)

  Private ValidItems As Dictionary(Of myKeyType, Boolean)

  Private LiveItemsCount As Integer

  Public ReadOnly Property Count As Integer
    Get
      Return LiveItemsCount
    End Get
  End Property

  Public Sub Clear()
    MyValues.Clear()
    ValidItems.Clear()
    LiveItemsCount = 0
  End Sub

  Public Sub Add(key As myKeyType, value As myValueType)
    MyValues.Add(key, value)
    ValidItems.Add(key, True)
    LiveItemsCount += 1
  End Sub

  Public Function Remove(key As myKeyType) As Integer
    If ValidItems(key) Then
      ValidItems(key) = False
      LiveItemsCount -= 1
      If LiveItemsCount = 0 Then
        MyValues.Clear()
        ValidItems.Clear()
      End If
    End If
    Return LiveItemsCount
  End Function

  Public Function TryGetValue(key As myKeyType, ByRef value As myValueType) As Boolean
    If MyValues.TryGetValue(key, value) Then
      If ValidItems(key) Then
        Return True
      Else
        value = Nothing
      End If
    End If
    Return False
  End Function

  Public Function TryGetAndDelete(key As myKeyType, ByRef value As myValueType) As Boolean
    If Me.TryGetValue(key, value) Then
      ValidItems(key) = False
      LiveItemsCount -= 1
      If LiveItemsCount = 0 Then
        MyValues.Clear()
        ValidItems.Clear()
      End If
      Return True
    End If
    Return False
  End Function

  // add more collection-wrapping methods as needed

End Class

你在性能上付出了包装类的开销，以及用于跟踪“真实”项目和被视为已删除项目的辅助字典。当删除一个项目时，你可以省去重复排序的时间。当然，这取决于实际情况是否有帮助（或伤害...）。再次强调，我自己没有测试过。

- Bert te Velde