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

Знание моих структур данных является ржавым, и, честно говоря, это никогда не было моим самым сильным моментом.

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

  • Должна быть в очереди очередь, деактивация и поиск определенного элемента по ключу.
  • каждый элемент будет структурой или классом с другим классом в качестве ключа, имеющим 5 различных свойств, похожих на категорию. Предположим что-то вроде: MasterCategoryId, ChildCategoryId, TimeId, PriorityId, GroupId.
  • это должна быть коллекция сортировок.
  • обычно коллекция будет храниться где угодно от 5k до 10k объектов, но для того, чтобы рассмотреть наихудший сценарий, мы тестируем наш прототип для хранения около миллиона объектов.
  • сейчас он не будет многопоточным.
  • около 90 или 95% элементов в коллекции (очередь) будет происходить, когда компонент будет создан, но компонент используется как дерево, в том смысле, что мы будем деактивировать последний элемент коллекции, выполните вычисления на нем, а затем он сообщит об этом результат своему родительскому элементу, который уже может быть или не быть в коллекции. Если это не так, метод очереди, используемый для поиска родителя, должен будет вставить элемент.
  • поскольку компонент похож на обработанную очередь, коллекция будет пуста после удаления всех объектов.

Думаю, это подводит итог. поэтому, очевидно, единого списка или упорядоченного списка не может быть и речи, из-за того, что каждый раз, когда мы добавляем или удаляем объекты из коллекции, он сортируется снова, и выполнение этого в одной коллекции с миллионом объектов происходит медленно.

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

Прямо сейчас мы создали структуру вроде

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

Вы получаете идею.

Это своего рода сладкое пятно группировки уровней, сохраняя каждую коллекцию относительно небольшой (около 300 предметов на словарь).

поэтому для первого уровня у нас будет отсортированныйdictionary, для которого ключи являются идентификаторами каждой главной категории, а значения будут отсортированы в соответствии с этим словом, ключ которого будет идентификатором дочерней категории... и т.д.

Сейчас мы тестировали 100, 1000, 10000, 100 000 и 1 000 000 элементов.

Для меньшего диапазона, до 100 тыс., решение выполняется быстро. он может стоять в очереди/деактивировать/находить менее секунды, даже до 300 тыс., что действительно выше 80-90% сценариев, которые мы будем обрабатывать.

Когда дело доходит до миллиона, он становится медленнее, занимая около 3-4 секунд, чтобы поставить в очередь все это и до 10 секунд, чтобы истощить очередь.

Итак, мои вопросы:

  • Есть ли более подходящий набор или подход для нашего конкретного сценария?
  • Я никогда раньше не работал с этим количеством предметов в коллекциях. Являются ли эти сроки разумными для таких высоких чисел, или нет? Я прошу, потому что я прочитал некоторые твиты людей, которые выполняют 200 000 операций в секунду на таких вещах, как MSMQ или NserviceBus (которые, как я знаю, не связаны с этим, я просто пытаюсь понять и сравнить мои результаты).
  • Объекты, которые я использую прямо сейчас в прототипе, представляют собой только макеты классов, просто составной ключ объекта и одно свойство. Могут ли повлиять на мои результаты, когда я буду использовать реальные классы или нет? Я предполагаю, что нет, поскольку вся инфраструктура будет делать, это добавить ссылку на объект, но просто хочу подтвердить, поскольку, как я уже сказал, структуры данных никогда не были моими самыми сильными знаниями.
  • В качестве отдельной темы, если бы я хотел подготовить для этого многопоточность, каковы некоторые соображения, которые я должен был бы предпринять?

Спасибо.

Ответы

Ответ 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

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