获取SortedList中两个键之间所有键的最快方法是什么？

给定填充的SortedList 。 对于给定的低和高DateTime间隔，我想获得所有键 （或它们的索引范围，应该是一个封闭的int间隔（错过了什么？））。

注意：不需要低值和高值实际上在SortedList中。

---

如果有人在没有SortedList的情况下更好地了解如何做到这一点，那么我想要做的范围有点宽，我发现SortedList可能是合适的：

• 我想用DateTime键缓存双精度数。
• 具有给定密钥的双精度访问性能优于添加密钥和删除密钥的性能
• 事情就是这样：我必须为给定的键范围“无效”缓存（删除键）同样不能保证在缓存中找到范围min和max。

Answer 1

我想知道为什么SortedList在它已经按键排序时不提供BinarySearch 。 它也使用方法本身（在IndexOf fe），但使用的数组是私有字段。

所以我试图为此创建一个扩展方法，看看：

 public static class SortedListExtensions { public static int BinarySearch(this SortedList sortedList, TKey keyToFind, IComparer comparer = null) { // need to create an array because SortedList.keys is a private array var keys = sortedList.Keys; TKey[] keyArray = new TKey[keys.Count]; for (int i = 0; i < keyArray.Length; i++) keyArray[i] = keys[i]; if(comparer == null) comparer = Comparer.Default; int index = Array.BinarySearch(keyArray, keyToFind, comparer); return index; } public static IEnumerable GetKeyRangeBetween(this SortedList sortedList, TKey low, TKey high, IComparer comparer = null) { int lowIndex = sortedList.BinarySearch(low, comparer); if (lowIndex < 0) { // list doesn't contain the key, find nearest behind // If not found, BinarySearch returns the complement of the index lowIndex = ~lowIndex; } int highIndex = sortedList.BinarySearch(high, comparer); if (highIndex < 0) { // list doesn't contain the key, find nearest before // If not found, BinarySearch returns the complement of the index highIndex = ~highIndex - 1; } var keys = sortedList.Keys; for (int i = lowIndex; i < highIndex; i++) { yield return keys[i]; } } } 

创建一个示例SortedList ：

 DateTime start = DateTime.Today.AddDays(-50); var sortedList = new SortedList(); for(int i = 0; i < 50; i+=2) { var dt = start.AddDays(i); sortedList.Add(dt, string.Format("Date #{0}: {1}", i, dt.ToShortDateString())); } DateTime low = start.AddDays(1); // is not in the SortedList which contains only every second day DateTime high = start.AddDays(10); 

现在，您可以使用上面的扩展方法来获取低密钥和高密钥之间的密钥范围：

 IEnumerable dateRange = sortedList.GetKeyRangeBetween(low, high).ToList(); 

结果：

 04/04/2014 04/06/2014 04/08/2014 04/10/2014 

请注意，这是从头开始构建的，并没有经过实际测试，但无论如何它都可以给你一个想法。

Answer 2

在列表排序后，您可以使用二进制搜索来定位间隔的端点。 最差情况表现为O（log n）。

Answer 3

您可以通过在Keys上运行两次自适应二进制搜索来解决问题，以找到绑定Keys集合中感兴趣范围的索引。

由于IList不提供二进制搜索工具，您需要自己编写。 幸运的是，还可以选择从如何在IList上执行二进制搜索中窃取现成的实现。

这是一个可以找到下限的改编版本：

 public static int LowerBound(this IList list, T value, IComparer comparer = null) { if (list == null) throw new ArgumentNullException("list"); comparer = comparer ?? Comparer.Default; int lower = 0, upper = list.Count - 1; while (lower <= upper) { int middle = lower + (upper - lower) / 2; int comparisonResult = comparer.Compare(value, list[middle]); // slightly adapted here if (comparisonResult <= 0) upper = middle - 1; else lower = middle + 1; } return lower; } 

要实现UpperBound ，只需更改即可

 if (comparisonResult <= 0) 

至

 if (comparisonResult < 0) 

这样做现在很简单：

 var low = set.Keys.LowerBound(value); var high = set.Keys.UpperBound(value); // These extra comparisons are required because the adapted binary search // does not tell us if it actually found the needle. They could be rolled // into the methods themselves, but this would require another out parameter. if (set.Keys[low] != value) ++low; if (set.Keys[high] != value) --high; if (low <= high) /* remove keys in the range [low, high] */