.NET 3.5 中超過 100 萬個有序集合的推薦資料結構

我的資料結構知識太生疏了，老實說，這從來都不是我的強項。

現在我們要建構一個類似隊列的組件，它具有以下要求：

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. 作為一個單獨的主題，如果我想為多執行緒做準備，我需要考慮哪些因素？

謝謝。

幾點說明和一般性建議（對不起，我沒有時間測試自己）：

我相信您的一般方法 - 嵌套（排序）字典 - 是合理的。令我滿意的是，我經常使用類似的結構 - 不是出於性能原因，因為我的案例總是很小，而是為了清晰和靈活。

在您的情況下，它還解決了性能問題之一，因為排序（在插入和刪除時）需要時間，而較小的（子）字典顯然排序更快。

是的，將類實例作為值（或鍵）僅使用引用，因此在這方面，您的類的大小或結構並不重要。

刪除（和添加）的時間增加可能（主要）是由每次刪除（或添加）項目時進行的重新處理引起的。

關於添加項目的性能：

如果您的案例使您能夠以排序（升序）順序為字典提供項目，您可能希望切換到 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

您為包裝類的成本以及內部用於跟踪“真實”項目與被認為已刪除的項目的輔助字典“支付”性能方面的費用。但是，您可以在刪除項目時保存重複排序。當然，這取決於實際情況是否會有所幫助（或有害……）。再說一次，我自己沒有測試過。

引用自：https://stackoverflow.com/questions/12345847