Производительность коллекции .Net для особого случая использования ⇐ C#

[Anonymous]

Я ищу хорошую отправную точку для своего варианта использования.
Мой вариант использования несколько особенный, поэтому простой тест производительности со всеми доступными коллекциями не поможет.
Производительность решает все. Потребление памяти может быть настолько высоким, насколько необходимо, меня это не волнует.
Примечание: я уже пробовал несколько вещей с экземплярами SortedDictionary. Но мне интересно, подойдут ли какие-нибудь другие коллекции лучше. Я также сам реализую решение, если существует более совершенный алгоритм для обработки этих вещей, поэтому нет необходимости придерживаться существующих реализаций.
Сценарий использования таков.Существует некоторая структура данных в виде {BigInterger key1, Guid key2, BigInteger Quantity. Guid не является случайным, а генерируется так, что каждый новый Guid имеет более высокое значение, чем предыдущий.
Примечание: я начал с SortedDictionary, используя ключ key1 в качестве ключа и удерживая другой SortedDictionary использует ключ2 в качестве ключа, но я пришел к выводу, что, возможно, лучше использовать более плоскую структуру данных только с одним SortedDictionary, использующим ключ1+ключ2.
Требования< /p>

• Вставки могут быть случайными, однако большинство вставок будут происходить в топ-100 элементов, отсортированных по ключу. Вставки всегда представляют собой отдельные элементы.
• При удалении элементов всегда сначала удаляются n верхних элементов. Таким образом, с точки зрения удаления коллекция похожа на стек. Удалить всегда удаляет от 1 до n элементов.
• Поиск не является случайным, но возвращает все n верхних элементов с ключами, меньшими или равными ключу поиска.
• Поиск следует также фильтровать по количеству. Таким образом, поиск будет принимать параметр количества. Товары возвращаются до тех пор, пока количество всех возвращаемых товаров не превышает искомое количество. Кроме того, все возвращенные элементы будут удалены из коллекции.
• Операция вставки/удаления всегда выполняется после операции поиска. Возможные цепочки операций: (поиск [15%], поиск->вставка [15%], поиск->удаление [15%], поиск->удаление->вставка [55%]). Вероятности - это предположения, нет реального способа заранее предсказать, что будет происходить чаще.
• Коллекция будет обрабатывать от 1 до 100 миллионов элементов. Может быть, даже больше.

Примечание: я также думал об использовании связанного списка. возможно, они подходят для этого лучше, чем SortedDictionary.
Каков будет ваш подход к этому?
Примечание: Текущее состояние: сравнение производительности между SortedDictionary' и SortedDictionary
Результаты на данный момент



Решение
Количество элементов
Вставки/секунда




SortedDictionary со встроенным SortedDictionary
1
1
847


SortedDictionary со встроенным SortedDictionary
1M
2000000

SortedDictionary со встроенным SortedDictionary
10M< /td>
87719


SortedDictionary со встроенным SortedDictionary
100M
4677


ImmutableSortedDictionary со встроенным ImmutableSortedDictionary1
410


ImmutableSortedDictionary со встроенным ImmutableSortedDictionary
1M
666666


ImmutableSortedDictionary со встроенным ImmutableSortedDictionary
10M
20491


ImmutableSortedDictionary со встроенным ImmutableSortedDictionary
100M
1406
< /tr>

SortedDictionary скомбинированным ключом
1
1288


SortedDictionary скомбинированным ключом
1M
769230


SortedDictionary скомбинированным ключом
10M
44444


SortedDictionary скомбинированным ключом
100M
2557


ImmutableSortedDictionary скомбинированным ключом
1
2105


ImmutableSortedDictionary скомбинированным ключом1M
370370


ImmutableSortedDictionary скомбинированным ключом
10M
14204


ImmutableSortedDictionary скомбинированным ключом
100M
1047




Подробнее здесь: https://stackoverflow.com/questions/787 ... l-use-case