LINQ в SortedList
Я - полный новичок LINQ, таким образом, я не знаю, является ли мой LINQ неправильным для того, что я должен сделать или если мои ожидания производительности являются слишком большими.
У меня есть SortedList объектов, включенных интервалом; 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 плохо? Я ожидаю слишком много? Я должен прокручивать свою собственную функцию двоичного поиска?
5 ответов
Самостоятельно написать двоичный поиск может быть непросто.
К счастью, Microsoft уже написала довольно надежный вариант: Array.BinarySearch. Фактически, это метод, который SortedList использует внутри. Проблема только в том, что он принимает аргумент T[], а не какой-нибудь IList (как SortedList).
Знаете, что? Есть замечательный инструмент под названием Reflector, который позволяет просматривать исходный код .NET...
Посмотрите: общий метод расширения BinarySearch на IList, взятый прямо из отраженного кода реализации Array.BinarySearch от 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 и получить отрицательное битовое дополнение нужного вам индекса в случае, если нужный ключ не найден (нижеприведенное взято практически прямо из ответа tzaman):
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;
UPDATE
Поскольку вы выбираете тип значения, FirstOrDefault не возвращает объект, допускающий значение NULL. Я изменил ваш запрос, чтобы вместо этого преобразовать выбранное значение в int? , позволяя проверять результирующее значение на null . Я бы поддержал это вместо использования ContainsKey , так как это вернет true , если ваш список содержит значение для 0 . Например, предположим, что у вас есть следующие значения
0 2 4 6 8
. Если бы вы передали что-либо, меньшее или равное 8, вы получили бы правильное значение. Однако, если вы должны передать 9, вы получите 0 ( default (int) ), что равно в списке, но не действительный результат.
Использование LINQ в SortedList не даст вам преимущества сортировки.
Для оптимальной производительности вы должны написать свой собственный двоичный поиск.
Почему бы не использовать 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
Как указывалось в комментариях, вызов , где , поскольку оно уже отсортировано ... ToList приведет к оценке всего списка, поэтому это полезно только в том случае, если вы выполняете несколько поисков без изменения базового SortedList , и сохраняете ключи перечисляются отдельно.
Хорошо, просто для большей наглядности - вот более краткая версия ответа Адама Робинсона:
return list.FirstOrDefault(kv => kv.Key >= i).Value;
Функция FirstOrDefault имеет перегрузку, которая принимает предикат , который выбирает первый элемент, удовлетворяющий условию - вы можете использовать это, чтобы напрямую получить нужный элемент, или null , если он не существует.