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

发布于 2024-09-18 11:41:06 字数 178 浏览 9 评论 0原文

我正在使用排序字典来维护项目列表，我经常需要监视其中前 x 个项目的状态。每次更新项目时，我都希望有一种快速的方法来确定我所指的项目正在使用什么索引。我知道我可以枚举整个列表并计算出我的位置，但我正在寻找 O(log n) 时间或更好的东西，毕竟排序的字典位于 RedBlack 树上。每个节点应该能够跟踪其子节点，并且这应该是一个快速计算。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

离线来电— 2024-09-25 11:41:07

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

回复收藏 0 原文

奢欲 2024-09-25 11:41:06

您只需将 SortedDictionary 更改为 SortedList，然后使用 IndexOfKey(key)：

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

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

IndexOfKey 内部使用 Array.BinarySearch()，因此它将是 O(log n)，这比 O( n）（如果您通过迭代从前到后搜索，就会出现这种情况）。

You can simply change your SortedDictionary<TKey, TValue> into a SortedList<TKey, TValue> and then use IndexOfKey(key):

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

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

IndexOfKey internally uses Array.BinarySearch<TKey>(), so it will be O(log n), which is faster than O(n) (which it would be if you searched from front to back by iterating through it).

回复收藏 0 原文

~没有更多了~