Самый эффективный способ найти индекс элемента в SortedDictionary

Я использую отсортированный словарь для ведения списка элементов, из которых мне регулярно нужно отслеживать состояние первых x элементов. Каждый раз, когда я обновляю элемент, мне нужен быстрый способ выяснить, какой индекс использует элемент, на который я ссылаюсь. Я понимаю, что могу перечислить весь список и подсчитать свою позицию, но я ищу что-то с временем O (log n) или лучше, ведь отсортированный словарь находится на дереве RedBlack. Каждый узел должен иметь возможность отслеживать своих дочерних элементов, и это должно быть быстрым вычислением.


c# sorteddictionary
person Superman    schedule 07.09.2010    source источник
comment
Думали ли вы о переходе на SortedList<T>? Он может выполнять O(1) поиск по индексу. Однако у него ужасная производительность при вставке и удалении.   -  person Ani    schedule 08.09.2010
comment
Поскольку это древовидная структура, понятие индекса отсутствует. Просто узлы с левой и правой дочерней ссылкой.   -  person Chris Taylor    schedule 08.09.2010
comment
Я не понимаю этот вопрос - элементы в деревьях не имеют индекса.   -  person Lee    schedule 08.09.2010
comment
@ Ли, в этом весь вопрос. он спрашивает: ПОСКОЛЬКУ дерево не содержит индекса, как SortedDictionary (на основе дерева) .Net можно использовать в запросе диапазона O (log (n)) поскольку для того, чтобы добраться до индекса, вам не нужно проходить весь SortedDictionary и проверка из вашего диапазона вперед, вы затем приводите к поиску O (n), который как бы противоречит поисковой части SortedDictionary .   -  person eran otzap    schedule 29.03.2012

Ответы (2)


arrow_upward
7
arrow_downward

Вы можете просто изменить SortedDictionary<TKey, TValue> на SortedList<TKey, TValue>, а затем использовать IndexOfKey(key):

var s = new SortedList<string, string>
    { { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } };

// Outputs 1
Console.WriteLine(s.IndexOfKey("b"));

IndexOfKey внутренне использует Array.BinarySearch<TKey>(), поэтому это будет O(log n), что быстрее, чем O(n) (что было бы, если бы вы выполняли поиск спереди назад с помощью перебирая его).

person Timwi    schedule 08.09.2010
comment
что, если вам нужна вставка O (1) и удаление в дополнение к поиску O (log (n)? - person eran otzap; 29.03.2012
comment
@eranotzer: тогда вам нужно будет использовать Dictionary<K,V> (у вас не может быть вставки O (1), если она должна всегда сортироваться), и вам нужно будет вручную отсортировать ее, чтобы выполнить поиск O (log n) (например, с помощью используя dic.Keys.ToList(), затем Sort и затем IndexOf). - person Timwi; 30.03.2012
comment
@Timwi не O(log n) выполнять поиск, если вы используете .ToList(), вы делаете это O(n)... и если вы делаете .Sort(), средняя производительность будет O(n log n) или, в худшем случае, O(n^2)... К сожалению, вы никогда не сможете вставить O(1) в BST, если это не первый элемент. - person FiringSquadWitness; 18.03.2019

arrow_upward
1
arrow_downward

Древовидная структура может быть построена для доступа к элементам по индексу или сообщения об индексе существующего элемента за lgN времени, требуя очень небольшого дополнительного времени для вставки и удаления. Один из способов сделать это — отслеживать, сколько элементов находится в левой и правой ветвях каждого узла (при вставке или удалении измените количество узлов родительских узлов при изменении количества дочерних узлов). Однако если древовидная структура не предлагает такой возможности, я не знаю простого способа модифицировать ее.

person supercat    schedule 08.09.2010
comment
Это тот угол, который я искал, но я ищу структуру, в которой он уже есть, или простой способ модернизации. - person Superman; 08.09.2010