在SortedList中的2个键之间获取所有键的最快方法是什么？ [英] What is the fastest way to get all the keys between 2 keys in a SortedList?

问题描述

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

Given a populated SortedList<DateTime, double>. I would like to get all the keys (or their index range, what should be a closed int interval (missed I something?)) for a given low and high DateTime interval.

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

Note: The low and high values are not necessary are actually in the SortedList.

如果有人更好地知道如何在没有SortedList的情况下进行此操作，那么我想在此范围更广这样做，我发现SortedList可能是合适的：

If anyone has better idea how to do this without a SortedList, here is a bit wider scope what I would like to do, and I found SortedList may be suitable:

• 我想用DateTime键缓存双打。


• 具有给定键的双精度访问性能优于添加键和移除键的性能


• 这是事实：我必须使给定的缓存无效键范围（删除键）再次不能保证在缓存中可以找到最小和最大范围。

推荐答案

我想知道为什么 SortedList< TKey，TValue> 不提供 BinarySearch 的原因。它已经按键排序了。它还使用方法本身（例如，在 IndexOf 中），但是使用的数组是私有字段。

I wondered why SortedList<TKey, TValue> doesn't provide a BinarySearch when it's already sorted by the keys. It also uses the method itself(f.e. in IndexOf), but the array used is a private field.

所以我尝试为此创建扩展方法，看看：

So i've tried to create an extension method for this, have a look:

public static class SortedListExtensions
{
    public static int BinarySearch<TKey, TValue>(this SortedList<TKey, TValue> sortedList, TKey keyToFind, IComparer<TKey> 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<TKey>.Default;
        int index = Array.BinarySearch<TKey>(keyArray, keyToFind, comparer);
        return index;
    }

    public static IEnumerable<TKey> GetKeyRangeBetween<TKey, TValue>(this SortedList<TKey, TValue> sortedList, TKey low, TKey high, IComparer<TKey> 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<DateTime, string>();
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);

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

Now you can use the extension method above to get the range of keys between a low- and high-key:

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

结果：

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

请注意，这是从头开始构建的，并未经过真正的测试，但无论如何它可能会给您一个想法。

Note that this is built from scratch and not really tested, but it could give you an idea anyway.

这篇关于在SortedList中的2个键之间获取所有键的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！