Улучшаем LINQ для работы с IReadOnly-коллекциями
Как известно, при использовании интерфейса 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
Начнём с указания тех операций, где оптимизация не требуется. Агрегирующие методы 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.
