C# эффективная структура данных для хранения объектов, отсортированных по ключу с дубликатами ключей, чтобы соответствовать заданным требованиям

Question

Я ищу наиболее эффективный способ хранения коллекции объектов, отсортированных Comparator, с использованием атрибута объекта на языке программирования C#.

Существуют объекты с одинаковым значением для атрибута, поэтому возникают дублирующие ключи в коллекции.

Классы сложности для вставки и удаления элементов в или из отсортированной структуры данных не должны превышать O (log (N)) (отмечено в Big O нотации ), поскольку атрибут используется для сортировка будет меняться очень часто, и список должен обновляться с каждым изменением, чтобы оставаться согласованным.

Классы сложности для получения всех элементов в структуре данных в виде списка в отсортированном порядке не должны превышать O (1).

Возможные значения: C# templates SortedSets , Сортированные словари или Сортированные списки . Все они терпят неудачу при вставке или удалении из отсортированной структуры данных, если присутствуют повторяющиеся ключи.

Обходным путем может быть использование составных SortedDictionaries, как показано ниже, и агрегирование объектов с одинаковым ключом в качестве отдельных коллекций, и сортировка их по другой уникальный ключ (например, ID):

SortedDictionary<long, SortedDictionary<long, RankedObject>> sPresortedByRank = 
new SortedDictionary<long, SortedDictionary<long, RankedObject>>(new ByRankAscSortedDictionary());

long rank = 52
sPresortedByRank[rank] = new SortedDictionary<long, RankedObject>(new ByIdAscSortedDictionary);

Вставка и удаление элементов из структуры данных будет работать в O (log (N)), что хорошо. Для получения всех элементов из списка данных в виде списка требуется дорогой Queryable.SelectMany , который увеличивает сложность этой операции до O (N ^ 2), что недопустимо.

В настоящее время наилучшей попыткой является используйте примитив List , вставляйте и удаляйте, используя BinarySearch , чтобы идентифицировать индексы для внесения и удаления. Для вставки это дает мне сложность O в худшем случае (log (N)). Для удаления среднего случая сложность O (log (n)), поскольку дублирующие ключи будут редкими, но O (N) в худшем случае (все объекты с одинаковым ключом). Получить все элементы отсортированного списка будет O (1).

Может ли кто-нибудь представить себе лучший способ управления сбором объектов в отсортированной структуре данных, который соответствует моим потребностям, или в настоящее время является наилучшей попыткой в ​​целом.

Помощь и обоснованные мнения приветствуются. Печенье для хороших ответов, конечно.

Answer 1

@ Ильяр Турдушевс очень полезный совет:

Рассматриваете ли вы использование библиотеки C5? Он содержит коллекцию TreeBag, которая удовлетворяет всем вашим требованиям. Кстати, для примитива List сложность вставки и удаления элементов не O (log (N)). O (log (N)) - это только сложность поиска в индексе, где элемент должен быть вставлен / удален. Но сама вставка / удаление использует Array.Copy для сдвига элементов для вставки / удаления элемента. Следовательно, сложность будет O (M), где M <= N. </p>

Answer 2

Я думаю, что самое простое решение, которое отвечает вашим требованиям, это добавить t ie разрыв в ваш компаратор, чтобы гарантировать, что не будет дубликатов и определенного общего порядка для всех объектов. Тогда вы можете просто использовать SortedSet.

Если вы можете иметь идентификатор, например, в каждом объекте, то вместо сортировки по «рангу» вы можете отсортировать по (рангу, идентификатору), чтобы создать компаратор общий порядок.

Чтобы найти все элементы с указанным c рангом, вы должны использовать SortedSet.GetViewBeteen() с диапазоном (rank, min_id) и (rank, max_id).