查找SortedDictionary中项目索引的最有效方法

我正在使用已排序的字典来维护项目列表，其中我经常需要监视顶级x项目的状态。每次我更新一个项目时，我想快速找出我所指的项目正在使用的索引。我知道我可以枚举整个列表并计算出我的位置，但是我在查找具有O（log n）或更好时间的东西，毕竟所有已排序的字典都位于RedBlack树上。每个节点应该能够跟踪它的孩子，这应该是一个快速计算。查找SortedDictionary中项目索引的最有效方法

来源

2010-09-07 Superman

你有没有考虑切换到'SortedList '？它可以通过索引进行'O（1）'检索。尽管如此，它在插入和删除方面确实有着不俗的表现。 – Ani 2010-09-07 23:49:24

由于这是一个树结构，因此没有索引的概念。只有具有左侧和右侧子链接的节点。 – 2010-09-07 23:51:09

我不明白这个问题 - 树中的项目没有索引。 – Lee 2010-09-07 23:53:02

您可以简单地改变你的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"));

内部使用Array.BinarySearch<TKey>()，所以这将是为O（log ñ），这是为O快（ñ）（如果你通过遍历它从前到后搜索）。

来源

2010-09-08 00:06:51 Timwi

如果你需要一个O（1）插入和除了O（log（n）search？ – 2012-03-29 13:09:46

@eranotzer：那么你将需要使用一个'字典'（你不能有O（1）插入，如果它应该总是排序），你需要手动排序它进行O（log n）搜索（例如，通过使用'dic.Keys.ToList（）'，接着'Sort'然后'IndexOf'） – Timwi 2012-03-30 13:11:14

可以构建树结构以通过索引访问项目或以lgN时间报告现有项目的索引，只需要非常少的额外时间来插入和删除。一种方法是跟踪每个节点的左右分支中有多少项（插入或删除时，更改子节点的计数时更改父节点的节点数）。但是，如果一个以树为基础的结构不提供这样的设施，我知道没有简单的方法来改造它。

来源

2010-09-08 00:10:28 supercat

这是我正在寻找的角度 - 但是我正在寻找一个已经拥有它的结构，或者一个简单的改造方法。 – Superman 2010-09-08 02:10:05

查找SortedDictionary中项目索引的最有效方法

回答

相关问题