.net collection для быстрой фильтрации (отсортированная коллекция)

Question

При профилировании очень медленного метода я обнаружил, что задержка заключается в поиске и фильтрации коллекции.

Метод делает следующее (по порядку). По словам профилировщика, 80% времени уходит на этапы 1-3.

1. Чтение отсортированной коллекции из файла и десериализация с использованием Protobuf-net (v2)
2. Из отсортированной коллекции, фильтр на основе начального и конечного целого числа (имя .RangeFromTo())
3. Из той же отсортированной коллекции получить следующий элемент коллекции (имя.Right())
4. Выполните некоторое задание...

.RangeFromTo() фильтры для заданного диапазона, например:

[3,7,9,12].RangeFromTo(2,9) -> [3,7,9]
[3,7,9,12].RangeFromTo(2,8) -> [3,7]
[3,7,9,12].RangeFromTo(7,13) -> [7,9,12]
[3,7,9,12].RangeFromTo(13,14) -> [ ]

.Right() находит элемент в коллекции и дает вам следующий в списке. Если элемент не существует, он дает ближайший отсчет справа. Например:

[3,7,9,12].Right(0) -> 3
[3,7,9,12].Right(3) -> 7
[3,7,9,12].Right(4) -> 7
[3,7,9,12].Right(12) -> null

В настоящее время коллекция использует SortedArray от C5 ( https://github.com/sestoft/C5/). Есть ли более подходящая коллекция, которую я могу использовать?

Примечание. Шаг 1. занимает около 30% от общего времени. Если я вместо этого использую List, protobuf фактически занимает на 40% меньше времени десериализации! Я предполагаю, что при вставке в SortedArray коллекция не знает, что данные уже отсортированы, и выполняет целую кучу работы. Идеальная коллекция (если таковая существует) также должна быть в состоянии обойти это.

Изменить: Чтобы уточнить, список составляет около 1000-5000, и есть 90 000 различных коллекций! Рассматриваемый метод должен загрузить все коллекции в памяти, чтобы выполнить некоторую бизнес-задачу.

Редактировать 2: я добавил пример теста здесь:

https://github.com/cchanpromys/so_19188345

Это сравнивает SortedArray от С5 с SortedSet из.Net. Пока что результаты следующие:

C5 sorted array deserialize took 904
Sorted set deserialize took 1040
C5 sorted array .Right() took 5
Sorted set .Right() took 798    <--- Not sure what happened here...
C5 sorted array .RangeFromTo() took 217
Sorted set .RangeFromTo() took 140

Редактировать 3 Это превзошло все мои ожидания, но я получил собственную реализацию списка.

Проблема, с которой я столкнулся, заключается в том, что операция поиска в SortedArray (в общем случае) принимает O(Log(N)), а я хочу, чтобы это была операция O(1).

Кроме того, список отсортирован по природе, вы никогда не будете добавлять в середину списка.

В итоге я реализовал список, который имеет внутренний индексный массив, например:

Например:

indexer: [0,0,0,0,1,1,1,1,2,2]
list: [3,7,9]

Так .Right(3) было бы list[indexer[3]++],

Код можно найти здесь.

Трудно поверить, что этот тип списка еще не реализован где-то в Интернете. Если возможно, я бы хотел использовать библиотеку, чтобы мне не пришлось управлять своим списком.

Существует ли такая реализация в Интернете?

Answer 1

Если ваши массивы достаточно малы (возможно, менее 10-20 элементов), то есть хороший шанс, что простой линейный поиск достаточно хорош (что в некоторой степени показано List быстрее в ваших измерениях), и вы можете вырезать диапазоны с Where/TakeWhile:

  (new[]{3,7,9,12}).Where(i => i>= 2).TakeWhile(i => i <= 9)