LINQ в SortedList
Я новичок в 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 плох? Я ожидаю слишком многого? Должен ли я использовать свою собственную функцию двоичного поиска?
6 ответов
Написание бинарного поиска самостоятельно может быть трудным.
К счастью, Microsoft уже написала довольно надежный: 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 и получите отрицательное побитовое дополнение нужного индекса в случае, если нужный ключ не найден (ниже взят в основном прямо из ответа Цамана):
int index = list.Keys.BinarySearch(i);
if (index < 0)
index = ~index;
var item = index < list.Count ? list[list.Keys[index]] : null;
return item;
Во-первых, ваш запрос оценивается дважды (один раз для 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как бы вернется true если ваш список содержал значение для 0, Например, скажем, у вас есть следующие значения
0 2 4 6 8
Если вы передадите что-либо меньше или равное 8, то вы получите правильное значение. Однако, если вы пройдете через 9, вы получите 0 (default(int)), который находится в списке, но не является действительным результатом.
Использование LINQ на SortedList не даст вам такой выгоды.
Для оптимальной производительности вы должны написать свой собственный бинарный поиск.
Хорошо, просто чтобы сделать это немного более наглядным - вот более краткая версия ответа Адама Робинсона:
return list.FirstOrDefault(kv => kv.Key >= i).Value;
FirstOrDefault Функция имеет перегрузку, которая принимает предикат, который выбирает первый элемент, удовлетворяющий условию - вы можете использовать его для непосредственного получения нужного элемента, или null если его не существует
Почему бы не использовать 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 список вокруг отдельно.
Используя OrderedDictionary в PowerCollections, вы можете получить перечислитель, который начинается там, где должны быть искомые ключи... если его там нет, вы получите следующий ближайший узел и затем сможете перейти вперед / назад от него в O(log N).) время на навигационный вызов.
Это дает вам преимущество в том, что вам не нужно писать собственный поиск или даже управлять своими собственными поисками поверх SortedList.