Как известно, при использовании интерфейса 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
