在.NET 3.5中推荐的100万+有序集合的数据结构

Question

我的数据结构知识很生疏,说实话,这绝不是我最强的观点.

现在我们要构建一个类似队列的组件,它具有以下要求:

1. 必须能够按键排队,出列和查找特定项目.
2. 每个项目将是一个结构或类,其他类作为键,具有5个不同的属性,类别.假设类似于:MasterCategoryId,ChildCategoryId,TimeId,PriorityId,GroupId.
3. 它必须是一个sorte集合.
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. 作为一个单独的主题,如果我想要为多线程做准备,我需要考虑哪些因素？

谢谢.

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

您在性能方面“支付”包装类的开销以及内部使用的辅助字典的开销，该辅助字典用于跟踪“真实”项目与那些被视为已删除的项目。但是，您可以节省删除项目时的重复排序。当然，这取决于实际情况是否有帮助（或有害......）。再说一次，我自己还没有测试过。