c# - SortedList.Last 与谓词的性能

Question

我想在 SortedList 中找到低于某个值的最后一项的值。由于 SortedList 是用能够进行二进制搜索的东西实现的，所以这在 O(log(n)) 中是可能的。

这段代码的性能是什么：

data.Last(x => x.Key < 100);

我只能找到 Enumerable.Last 的文档（http://msdn.microsoft.com/en-us/library/bb549138(v=vs.90).aspx），我想确保它不使用泛型基于枚举器的实现。

Answer 1

ASortedList执行与任何IEnumerable<T>for.Last方法相同，都是 O(n)；

Answer 2

我会用另一个问题来回答你的问题。对于任何任意谓词，如何SortedList利用其固有的排序比 O(n) 做得更好？

除非您对谓词做出假设，否则您基本上必须使用标准枚举器方法