LINQ в SortedList

Question

Я полный новичок в LINQ, поэтому я не знаю, неверен ли мой LINQ для того, что мне нужно делать, или мои ожидания в отношении производительности слишком высоки.

У меня есть SortedListобъектов с ключом int;SortedList, а не SortedDictionary, потому что я буду заполнять коллекцию предварительно отсортированными данными.Моя задача - найти либо точный ключ, либо, если точного ключа нет, тот, который имеет более высокое значение.Если поиск слишком велик для списка (например, максимальный ключ равен 100, но ищите 105), верните ноль.

// 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

Написание двоичного поиска самостоятельно может быть трудным.

К счастью, Microsoft уже написала довольно надежный: Array.BinarySearch<T>. Фактически это метод, который SortedList<TKey, TValue>.IndexOfKey использует внутренне . Единственная проблема в том, что он принимает аргумент T[] вместо любого IList<T> (например, SortedList<TKey, TValue>.Keys).

Вы знаете что, хотя? Есть этот замечательный инструмент под названием Reflector , который позволяет вам просматривать исходный код .NET ...

Проверьте это: универсальный BinarySearch метод расширения для IList<T>, взятый прямо из отраженного кода реализации Array.BinarySearch<T> от Microsoft.

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 и получить отрицательное побитовое дополнение нужного вам индекса в случае, если нужный ключ не найден (ниже взята в основном прямо из ответа Цамана):

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

Answer 3

Использование LINQ для SortedList не даст вам такого преимущества.

Для оптимальной производительности вы должны написать собственный двоичный поиск.

Answer 4

ОК, просто чтобы сделать это немного более наглядным - вот более краткая версия ответа Адама Робинсона:

return list.FirstOrDefault(kv => kv.Key >= i).Value; 

Функция FirstOrDefault имеет перегрузку, которая принимает предикат, который выбирает первыйэлемент, удовлетворяющий условию - вы можете использовать его для непосредственного получения нужного элемента или null, если он не существует.

Answer 5

Почему бы не использовать BinarySearch, встроенный в класс List?

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

Если цель поиска отсутствует в списке, BinarySearch возвращает побитовое дополнение следующего более высокого элемента; мы можем использовать это, чтобы напрямую получить то, что вы хотите, дополнив результат, если он отрицательный. Если оно станет равным Count, ваш поисковый ключ окажется больше, чем что-либо в списке.

Это должно быть намного быстрее, чем выполнение LINQ where, поскольку оно уже отсортировано ... Как отмечалось в комментариях, вызов ToList вызовет оценку всего списка, так что это выгодно, только если вы выполняете многократный поиск без изменения базового SortedList и сохраняете список keys отдельно.

Answer 6

Используя OrderedDictionary в PowerCollections, вы можете получить перечислитель, который начинается там, где должны быть искомые ключи ... если его там нет, вы получите следующий ближайший узел и затем сможете перемещаться вперед / назад от него в O (log N) время на навигационный вызов.

Преимуществом этого является то, что вам не нужно писать собственный поиск или даже управлять своими поисками поверх SortedList.