Структура данных в .NET, которая хранит элементы как отсортированные, уникальные и запрашиваемые по диапазону (и не SortedSet)

Question

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

Я ищу структуру данных в .NET (до v4.0) который хранит элементы как отсортированные и уникальные (например, с помощью компаратора или уникального ключа).Он должен поддерживать добавление / удаление не более, чем логарифмическую сложность, а также выполнять бинарный поиск с такой же сложностью.

System.Collections.Generic.SortedSet казалось тем, что я хотел, но его метод GetViewBetween() возвращает включающий список элементов, как SortedSet.

Я пропускаю две вещи:

1. Вызов ToList() или перечисление SortedSet слишком дорого, так как список длинный.Мне нужно, чтобы метод возвращал List<T>, а не SortedSet<T>.
2. Вызов его с инклюзивным / эксклюзивным диапазоном дат, на мой выбор - невозможно, и мне это тоже нужно.

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

Спасибо.

Answer 1

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

Для поддержки поиска по дате вы можете захотеть иметь B-дерево (одна реализация, обратите внимание, у меня нет ').t протестировал его: http://blog.daisley -harrison.com / blog / post / NET-Generic-BTree-Library-and-Source-Code.aspx ) с указанием даты.Убедитесь, что он поддерживает дубликаты ключей, поскольку они могут быть не уникальными.Он может содержать либо копию данных, либо просто ключ, связанный с этой отметкой времени.

Все эти структуры имеют log (n) или, что еще лучше, сложность для поиска.Перечисление элементов между двумя датами должно быть довольно эффективным, с наилучшей производительностью при использовании комбинации B-Tree / Dictionary.

Answer 2

После небольшого чтения может показаться, что вам нужен SortedList или SortedDictionary. SortedList, по-видимому, использует меньше памяти и технически представляет собой двоичное дерево, где SortedDictionary быстрее с несортированными данными. Кроме того, они очень близкие родственники.

Вот хороший вопрос / ответ о различиях: SortedList против SortedDictionary и Sort ()