10

我的数据结构知识太生疏了，老实说，这从来都不是我的强项。

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

  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 之类的东西上每秒执行 20 万次操作（我知道这与此无关，我只是想理解和比较我的结果）。
  3. 我现在在原型中使用的对象只是模拟类，只是复合对象键和单个属性。当我使用真正的课程时，我的结果会受到影响吗？我猜不是，因为所有框架都会添加对对象的引用，但只是想确认一下，因为就像我说的那样，数据结构从来都不是我最擅长的知识。
  4. 作为一个单独的主题，如果我想为多线程做准备，我需要考虑哪些因素？

谢谢。

4

1 回答 1

2

几点说明和一般性建议（对不起，我没有时间测试自己）：

我相信您的一般方法 - 嵌套（排序）字典 - 是合理的。令我满意的是，我经常使用类似的结构 - 不是出于性能原因，因为我的案例总是很小，而是为了清晰和灵活。

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

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

删除（和添加）的时间增加可能（主要）是由每次删除（或添加）项目时进行的重新处理引起的。

关于添加项目的性能：

如果您的案例使您能够以排序（升序）顺序为字典提供项目，您可能希望切换到 SortedLIST，而不是 SortedDICTIONARY，因为在列表中添加项目是 O(1) 而不是 O(log n ) 如果新项目将在排序集合结束时结束。

一个集合有一个初始的 CAPACITY - 为项目保留的空间。添加超出集合当前容量的项目会导致 (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

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

于 2012-09-10T07:48:07.623 回答