LINQ to Objects и улучшенный перфект с индексом? - PullRequest
Новая
       10

LINQ to Objects и улучшенный перфект с индексом?

8 голосов
/ 04 октября 2011

Я использую LINQ to Objects и задаюсь вопросом, можно ли повысить производительность моих запросов, используя имеющийся у меня индекс.Это лучше всего объяснить на примере.Представьте себе простой тип ... 

public class Person
{
    public int Age;
    public string FirstName;
    public string LastName;
}

И простой запрос, который я бы сделал против него ... 

List<Person> people = new List<Person>();

// 'people' populated with 50,000 instances...

var x = from t in people
        where t.Age > 18 && t.Age < 21
        select t;

Если я правильно понимаю LINQ to Objects, тогда реализация WhereМетод extension перечислит все 50 000 экземпляров в коллекции people, чтобы найти 100, которые действительно соответствуют.Так получилось, что у меня уже есть индекс коллекции людей, отсортированный по возрасту.Вот так ... 

SortedList<int, Person> ageSorted = new SortedList<int, Person>();

Ясно, что было бы разумно, если бы я мог получить Где использовать SortedList, чтобы ему больше не приходилось перечислять все 50000 экземпляров, вместо этого найти диапазон из 100 подходящих записей итак экономя время.

Можно ли расширить LINQ для объектов, чтобы разрешить мою ситуацию?Это уже возможно, но мне не хватает техники?

Ответы [ 4 ]

5 голосов
/ 04 октября 2011

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

Если у вас есть SortedList, вы можете использовать это с помощью SkipWhile / TakeWhileМетоды linq: 

 var x = x.SkipWhile(kv => kv.Key <= 18).TakeWhile(kv => kv.Key < 21)

EDIT

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

Если вам нужно выполнить эту операцию более одного раза для разных возрастных диапазонов, то вы также можете ускорить ее, сгруппировав по возрасту: 

var byAge = people.GroupBy(p => p.Age);

var x = from grp in byAge 
        where grp.Key > 18 && grp.Key < 21
        from person in grp
        select person;
5 голосов
/ 04 октября 2011

Уже есть проект, который, я считаю, делает именно это - i4o .Я не могу сказать, что использовал это сам, но это звучит так, как вы хотите ... вам, возможно, придется немного поработать над существующим кодом, но это, безусловно, стоит посмотреть.

Есличто не помогает, вы могли бы по крайней мере написать свои собственные методы расширения для SortedList<TKey, TValue>.Возможно, вы не сможете легко использовать ваше фактическое предложение where, но вы можете использовать свои собственные методы, принимающие минимальное и максимальное значения.Возможно, вы также захотите применить их к IList<T>, где вы утверждаете , что вы уже отсортировали значения соответствующим образом (согласно некоторому компаратору).

Дляпример (полностью непроверенный): 

public static IEnumerable<T> Between<T, TKey>(this IList<T> source,
                                              Func<T, TKey> projection,
                                              TKey minKeyInclusive,
                                              TKey maxKeyExclusive,
                                              IComparer<TKey> comparer)
{
    comparer = comparer ?? Comparer<TKey>.Default;

    // TODO: Find the index of the lower bound via a binary search :)
    // (It's too late for me to jot it down tonight :)
    int index = ...; // Find minimum index

    while (index < source.Count &&
           comparer.Compare(projection(source[index]), maxKeyExclusive) < 0)
    {
        yield return source[index];
        index++;
    }
}

(Если у вас есть List<T> вместо IList<T>, вы можете использовать List<T>.BinarySearch, хотя вам нужно будет построитьcustom IComparer<T>.)

Также обратите внимание на SortedSet<T> в .NET 4.

2 голосов
/ 04 октября 2011

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

    public static IEnumerable<Person> Where(this IEnumerable<Person> collection, Func<Person, bool> condition )
    {
        Console.WriteLine("My Custom 'Where' method called");
        return System.Linq.Enumerable.Where(collection, condition);
    }

... 

        var x = from t in people
                where t.Age > 18 && t.Age < 21
                select t; //Will print "My Custom 'Where' method called"

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

0 голосов
/ 04 октября 2011

В предварительно отсортированном контейнере эффективность достигается путем быстрого поиска первого элемента. Как только вы найдете первый элемент, просто линейно извлекайте следующие элементы, пока не найдете конец вашего диапазона.

Если ваш SortedList отсортирован по Person.Age, вы можете найти первый элемент диапазона, используя SortedList.IndexOfKey, который является алгоритмом двоичного поиска ; следовательно, этот метод является операцией O (log n).

( Я не думаю, что вы можете изменить свой код, чтобы Enumerable.Where внезапно стал более интеллектуальным и нашел начало диапазона с помощью бинарного поиска. )

--- РЕДАКТИРОВАТЬ ---

На самом деле, вам действительно нужно List.BinarySearch или Array.BinarySearch. SortedList.IndexOfKey не позволит вам получить индекс ближайшего совпадения, если точное совпадение не существует. Или вы можете просто выполнить бинарный поиск самостоятельно.

...