Рекомендуемая структура данных для 1 миллиона + упорядоченная коллекция в .NET 3.5

Ответ 1

Несколько замечаний и общих предложений (извините, что у меня нет времени проверять себя):

Я считаю, что ваш общий подход - вложенные (отсортированные) словари - звучат. Я очень часто использую подобные структуры, к моему удовлетворению - не по соображениям производительности, потому что мои дела всегда небольшие, но для ясности и гибкости.

В вашем случае он также затрагивает одну из проблем производительности, потому что сортировка (при вставке и удалении) требует времени, а меньшие (суб) словари явно сортируются быстрее.

Да, наличие экземпляров класса в качестве значений (или ключей) использует только ссылку, поэтому в этом отношении не имеет значения, какой размер или структура имеет ваш класс.

Возрастающее время для удаления (и добавления) предположительно вызвано (в первую очередь) прибеганием, которое выполняется каждый раз, когда вы удаляете (или добавляете) элемент.

Что касается производительности добавления элементов:

Если ваш случай позволяет вам комбинировать словари с элементами в отсортированном (восходящем) порядке, вы можете захотеть переключиться на SortedLIST, а не в SortedDICTIONARY, потому что в добавлении списка элементы O (1), а не O (log n), если новые элементы будут завершены в конце отсортированной коллекции.

У коллекции есть начальная CAPACITY - зарезервированное пространство для элементов. Добавление предметов, выходящих за рамки текущей способности сбора, приводит к: (а) увеличению емкости коллекции; (б) перераспределение пространства для (всего) нового потенциала; (c) копирование значений из исходного (небольшого) хранилища в новое. Поэтому, если у вас есть представление о том, насколько велики ваши коллекции: инициализируйте коллекцию с соответствующей емкостью. Это еще не возможно с помощью sortedDictionary, но sortedLIST поддерживает эту функцию.

Что касается эффективности удаления элементов:

Возможно, вам захочется рассмотреть подход, который использует персонализированный класс для сортировки сортированной коллекции, так что он не "действительно" удаляет элементы (тем самым избегая прибегания), пока вся коллекция не будет пуста.

В общем, попробуйте что-то в следующих строках (используя синтаксис vb, я уверен, что вы можете перевести его на С#, 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

Вы "платите" за производительность за накладные расходы класса упаковки, а также за вспомогательный словарь, который используется внутри, чтобы отслеживать "реальные" элементы по сравнению с теми, которые считаются удаленными. Однако вы сохраняете повторную сортировку при удалении элемента. Конечно, это зависит от того, будет ли это помогать (или вредить...). И снова я сам не тестировал его.