LINQ到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次大约需要1.5秒。调用它50,000次需要超过2分钟。这个性能看起来很差。我的LINQ是不是坏了？我是不是期望太高了？我应该使用我自己的二进制搜索函数吗？

Answer 1

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

幸运的是，微软已经编写了一个相当健壮的：Array.BinarySearch<T>。This is, in fact, the method that SortedList.IndexOfKey uses internally。唯一的问题是，它需要一个T[]参数，而不是任何IList<T> (如SortedList<TKey, TValue>.Keys)。

你知道吗？有一个很棒的工具叫做Reflector，它可以让你查看.NET源代码……

看看：IList<T>上的一个通用BinarySearch扩展方法，直接取自微软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;

Answer 2

首先，查询被评估了两次(一次针对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;

更新

因为您选择的是值类型，所以FirstOrDefault不会返回可以为空的对象。我更改了您的查询，改为将所选值转换为int?，从而允许检查null的结果值。我主张这样做而不是使用ContainsKey，因为如果您的列表包含0的值，那么它将返回true。例如，假设您有以下值

0 2 4 6 8

如果您要传入任何小于或等于8的值，那么您将获得正确的值。然而，如果你传入9，你会得到0 (default(int))，它在列表中，但不是一个有效的结果。

Answer 3

在SortedList上使用LINQ不会给你带来排序的好处。

为了获得最佳性能，您应该编写自己的二进制搜索。