LINQ into SortedList

Question

我是一个完整的LINQ新手,所以我不知道我的LINQ是否不正确我需要做什么或者我的性能期望是否太高.

我有一个对象的SortedList,用int键入; SortedList与SortedDictionary相对,因为我将使用预先排序的数据填充集合.我的任务是找到确切的密钥,或者,如果没有确切的密钥,则找到具有下一个更高值的密钥.如果列表的搜索太高(例如,最高键为100,但搜索105),则返回null.

// The structure of this class is unimportant.  Just using
// it as an illustration.
public class CX
{
    public int KEY;
    public DateTime DT;
}

static CX getItem(int i, SortedList<int, CX> list)
{
    var items =
    (from kv in list
     where kv.Key >= i
     select kv.Key);

    if (items.Any())
    {
        return list[items.Min()];
    }

    return null;
}

给定50,000条记录的列表,调用getItem 500次需要大约一秒半.拨打50,000次电话需要2分钟.这种表现似乎很差.我的LINQ坏了吗？我期待太多了吗？我应该滚动自己的二元搜索功能吗？

Answer 1

首先,您的查询被评估两次(一次为一次Any,一次为Min).其次,Min要求它遍历整个列表,即使它排序的事实意味着第一个项目将是最小的.你应该能够改变这个:

if (items.Any())
{
    return list[items.Min()];
}

对此:

var default = 
    (from kv in list
     where kv.Key >= i
     select (int?)kv.Key).FirstOrDefault();

if(default != null) return list[default.Value];

return null;

UPDATE

因为您正在选择值类型,FirstOrDefault所以不会返回可为空的对象.我已经更改了您的查询以将所选值强制转换为,int?而是允许检查结果值null.我会主张使用ContainsKey,因为true如果您的列表包含值,则会返回0.例如,假设您具有以下值

0 2 4 6 8

如果你传入任何小于或等于8的东西,那么你将得到正确的值.但是,如果你在9传递,你会得到0( default(int)),这是在列表中,但不是一个合法的结果.

Answer 2

自己编写二进制搜索可能很困难.

幸运的是,微软已经写了一个相当强大的:Array.BinarySearch<T>.事实上,这是SortedList<TKey, TValue>.IndexOfKey内部使用的方法.唯一的问题是,它需要一个T[]参数,而不是任何IList<T>(像SortedList<TKey, TValue>.Keys).

你知道吗？有一个名为Reflector的好工具可以让你看看.NET源代码......

检查出来:一个通用的BinarySearch扩展方法IList<T>,直接来自Microsoft Array.BinarySearch<T>实现的反映代码.

public static int BinarySearch<T>(this IList<T> list, int index, int length, T value, IComparer<T> comparer) {
    if (list == null)
        throw new ArgumentNullException("list");
    else if (index < 0 || length < 0)
        throw new ArgumentOutOfRangeException((index < 0) ? "index" : "length");
    else if (list.Count - index < length)
        throw new ArgumentException();

    int lower = index;
    int upper = (index + length) - 1;

    while (lower <= upper) {
        int adjustedIndex = lower + ((upper - lower) >> 1);
        int comparison = comparer.Compare(list[adjustedIndex], value);
        if (comparison == 0)
            return adjustedIndex;
        else if (comparison < 0)
            lower = adjustedIndex + 1;
        else
            upper = adjustedIndex - 1;
    }

    return ~lower;
}

public static int BinarySearch<T>(this IList<T> list, T value, IComparer<T> comparer) {
    return list.BinarySearch(0, list.Count, value, comparer);
}

public static int BinarySearch<T>(this IList<T> list, T value) where T : IComparable<T> {
    return list.BinarySearch(value, Comparer<T>.Default);
}

如果list.Keys.BinarySearch找不到所需的键,这将允许您调用并获得所需索引的负按位补码(以下内容基本上直接取自tzaman的答案):

int index = list.Keys.BinarySearch(i);
if (index < 0)
    index = ~index;
var item = index < list.Count ? list[list.Keys[index]] : null;
return item;