Улучшаем LINQ для работы с IReadOnly-коллекциями

в 6:26, , рубрики: .net, linq, коллекции, Программирование

Как известно, при использовании интерфейса IEnumerable<> там, где подразумевается коллекция, могут случаться проблемы (см. например Проблемы использования IEnumerable и LINQ против LSP). К счастью, в .NET v4.5 в 2012-м году (немного поздновато, но лучше поздно, чем никогда), появились интерфейсы IReadOnlyCollection<>, IReadOnlyList<>, IReadOnlyDictionary<> (далее буду их обобщённо называть IReadOnly-интерфейсы). В отличие от IEnumerable<>, IReadOnly-интерфейсы дают возможность достаточно и без лишних требований обозначать функциональность коллекции, что и позволяет их рекомендовать для использования вместо IEnumerable<> везде, где подразумевается чтение коллекции. Но тут встречается одно затруднение. Одним из важных компонентов, потребляющим и создающим коллекции, является LINQ и, особенно, его часть «LINQ к объектам». К сожалению, IReadOnly-интерфейсы появились на 5 лет позже чем LINQ, и в нём не используются. Все входные и выходные коллекции LINQ-операций имеют базовый тип IEnumerable<>, исходя из ограниченных возможностей которого, многие операции подразумевают лишние затраты: полный последовательный перебор или даже создание промежуточных копий входных коллекций. Более того, возвращая из операций тот же IEnumerable<>, LINQ требует при дальнейшем использовании результата опять использовать полный перебор и создание промежуточных копий. В связи с этим, у меня давно зрела мысль «подружить» LINQ с IReadOnly-интерфейсами.

Найденные на просторах Интернета разработки на эту тему не удовлетворили меня. Например, библиотека Linq to Collections предлагает эффективную замену лишь некоторых LINQ-операций только для интерфейса IReadOnlyList<>, слабо оптимизирована, и зачем то принудительно добавляет множество неоднозначных методов расширения для базовых типов. В ещё одном найденном проекте на эту тему, CountableSharp, предлагается небольшое число оптимизированных LINQ-операций только для интерфейса IReadOnlyCollection<>, в которых возвращается декоратор, делегирующий все обращения к базовому System.Linq.Enumerable и только свойство Count вычисляется заранее, не требуя полного перебора коллекции.

Далее я предлагаю к использованию мою библиотеку Collections.LINQ, оптимизирующую «LINQ к объектам» путём предоставления эффективной реализации большинства операций для коллекций, реализующих IReadOnly-интерфейсы.

Первым делом позволю себе небольшое отступление, позволяющее лучше понять и использовать проделанную мной работу. Как многие из вас, наверное, заметили, в ряду IReadOnly-интерфейсов явно не хватает интерфейса для множеств. Поэтому создадим его сами в таком очевидном виде:

public interface IReadOnlyFiniteSet<T> : IReadOnlyCollection<T>
{
	bool Contains (T item);
}

Единственное, что тут неоднозначно — это конечность множества, связанная с наследованием IReadOnlyCollection<>. Как вариант, можно было создать промежуточный интерфейс бесконечного множества IReadOnlySet<>, наследованный от IEnumerable<>. Однако, практической необходимости в нём нет, поскольку бесконечные множества представляют лишь академический интерес и трудно себе представить, где им можно найти применение. Все существующие в базовой библиотеке классов множества уже реализуют методы, необходимые для IReadOnlyFiniteSet<>, поэтому проблем с его реализацией не возникнет. Далее я буду говорить об оптимизации LINQ-операций в том числе и для интерфейса IReadOnlyFiniteSet<>, надеясь что его когда-нибудь сделают частью базовой библиотеки.

Итак, рассмотрим, какие операции реализованы в Collections.LINQ и как именно они повышают эффективность «LINQ к объектам».

Начнём с указания тех операций, где оптимизация не требуется. Агрегирующие методы Aggregate(), Average(), Min(), Max(), Sum() не нуждаются в какой либо оптимизации потому, что для них необходимым и достаточным интерфейсом является IEnumerable<>, а возвращают они значение, а не коллекцию. По той же причине не нуждаются в оптимизации перегрузки методов All(), Any(), Count(), LongCount(), First(), FirstOrDefault(), Last(), LastOrDefault(), Single(), SingleOrDefault(), принимающие параметром предикат-фильтр. Наличие предиката диктует необходимость полного перебора, для которого достаточно IEnumerable<>. Очевидно, что также не требуют оптимизации и методы ToArray(), ToList(), ToDictionary(), ToLookup() потому, что семантически подразумевают полный перебор и создание копии. Только создание массива в методе ToArray() можно немного оптимизировать зная заранее количество элементов в коллекции.

Методы создания коллекций Empty(), Range() и Repeat() требуют одной очевидной оптимизации: они должны возвращать не базовый IEnumerable<>, а конкретный IReadOnly-интерфейс.

Теперь о главной оптимизации. В операциях, возвращающих коллекцию, результат создаётся в виде декоратора, который делегирует обращения к членам напрямую к входным коллекциям, без предварительных переборов и создания копий элементов. Чтобы такая оптимизация работала при последовательном применении нескольких операций, важно также, чтобы возвращаемые коллекции также были IReadOnly-типом. В «LINQ к объектам» уже реализована подобная внутренняя оптимизация: многие методы первым делом проверяют реализацию некоторых интерфейсов входной коллекцией, и используют их для более эффективного выполнения действий. Но, конечно же, IReadOnly-интерфейсы (не существовавшие на момент появления LINQ) не используются, а возвращаемая коллекция всегда имеет лишь базовый тип IEnumerable<>. В моей библиотеке оптимизация в виде непосредственного декорирования применяется в следующих LINQ-операциях.

для коллекций типа IReadOnlyCollection<>
Any(), Count(), LongCount() сразу возвращают результат используя свойство Count
DefaultIfEmpty() возвращает IReadOnlyCollection<>, в зависимости от свойства Count исходную либо одно-элементную
Select(), Zip() возвращают IReadOnlyCollection<>-декоратор
Skip(), Take() возвращают IReadOnlyCollection<>, в зависимости от свойства Count исходную, пустую либо декоратор
Concat() возвращает IReadOnlyCollection<>, в зависимости от свойств Count одну из исходных либо декоратор
Reverse() возвращает IReadOnlyCollection<>, в зависимости от свойства Count исходную либо декоратор, создающий при запросе перечисления полную копию коллекции
OrderBy(), OrderByDescending(), ThenBy(), ThenByDescending() возвращают IReadOnlyCollection<>, в зависимости от свойства Count исходную либо декоратор, создающий при запросе перечисления полную копию коллекции и сортированный индекс
для множеств типа IReadOnlyFiniteSet<> (дополнительно к тому, что доступно для коллекций IReadOnlyCollection<>)
Contains() сразу возвращает результат используя метод Contains()
Distinct() возвращает исходное IReadOnlyFiniteSet<>-множество
Except(), Intersect(), Union() возвращают IReadOnlyFiniteSet<>, в зависимости от свойства Count одно из исходных, пустое либо декоратор, при создании полностью перебирающий меньшее из входных множеств
DefaultIfEmpty() возвращает IReadOnlyFiniteSet<>, в зависимости от свойства Count исходное либо одно-элементное
Reverse() возвращает IReadOnlyFiniteSet<>, в зависимости от свойства Count исходное либо декоратор, создающий полную копию множества
для списков типа IReadOnlyList<> (дополнительно к тому, что доступно для коллекций IReadOnlyCollection<>)
ElementAt(), ElementAtOrDefault(), First(), FirstOrDefault(), Last(), LastOrDefault() сразу возвращают результат используя методы IReadOnlyList<>
DefaultIfEmpty() возвращает IReadOnlyList<>, в зависимости от свойства Count исходный либо одно-элементный
Skip(), Take(), Select(), Concat(), Zip(), Reverse() возвращают IReadOnlyList<>-декоратор
OrderBy(), OrderByDescending(), ThenBy(), ThenByDescending() возвращают IReadOnlyList<>, в зависимости от свойства Count исходный либо декоратор, создающий сортированный индекс для делегирования получения элементов по номеру позиции и перечисления

К сожалению, некоторым LINQ-операциям функциональность IReadOnly-коллекций не может добавить эффективности. Это те операции, результатом которых является коллекция, полученная применением фильтрации значений элементов входных коллекций. Тут уже никак не обойтись без полного перебора и копирования. Не оптимизированными остаются операции фильтрации SkipWhile(), TakeWhile(), Where(), а также методы условной группировки и соединения Join(), GroupJoin(), GroupBy(), SelectMany().

Дополнительно упомяну несколько оптимизаций в моей Collections.Linq, не связанных с IReadOnly-интерфейсами:

  • LINQ-операция SequenceEqual() реализована в виде прямого делегирования к методу Equals() интерфейса IStructuralEquatable для коллекций, реализующих этот интерфейс (появившийся на 3 года позже LINQ).
  • Значительно сокращено количество перегрузок методов за счёт повсеместного использования опциональных параметров (появившихся на год позже LINQ).
  • Добавлена явно недостающая операция над множествами — симметрическая разность в виде метода SymmetricExcept().

Чтобы удостовериться, что я ничего не упустил и сделал более эффективно, чем библиотечный System.Linq.Enumerable, я постоянно подглядывал в его исходники.

Использовать библиотеку Collections.LINQ несложно: достаточно в ваш код за строкой

using System.Linq;

добавить строку

using BusinessClassLibrary.Collections.Linq;

Неважно, как вы используете «LINQ к объектам», в виде синтаксиса запросов или в текучем (fluent) виде. После подключения моей библиотеки, ваш LINQ код будет автоматически использовать наиболее оптимальные методы при условии, что на вход подаются коллекции, реализующие IReadOnly-интерфейсы. Единственное исключение — методы создания коллекций класса System.Linq.Enumerable, которые не являются методами расширения: Enumerable.Empty(), Enumerable.Range() и Enumerable.Repeat().
Эти методы нужно будет вручную заменить на FiniteSet.Empty()/List.Empty(), FiniteSet.Range()/List.Range() и List.Repeat() соответственно.

Вся библиотека представлена в публичном проекте на github. По просьбе читателей также создан nuget-пакет с библиотекой.

Автор: novar

Источник

* - обязательные к заполнению поля