- PVSM.RU - https://www.pvsm.ru -
Как известно, при использовании интерфейса IEnumerable<> там, где подразумевается коллекция, могут случаться проблемы (см. например Проблемы использования IEnumerable [1] и LINQ против LSP [2]). К счастью, в .NET v4.5 в 2012-м году (немного поздновато, но лучше поздно, чем никогда), появились интерфейсы IReadOnlyCollection<>, IReadOnlyList<>, IReadOnlyDictionary<> (далее буду их обобщённо называть IReadOnly-интерфейсы). В отличие от IEnumerable<>, IReadOnly-интерфейсы дают возможность достаточно и без лишних требований обозначать функциональность коллекции, что и позволяет их рекомендовать для использования вместо IEnumerable<> везде, где подразумевается чтение коллекции. Но тут встречается одно затруднение. Одним из важных компонентов, потребляющим и создающим коллекции, является LINQ [3] и, особенно, его часть «LINQ к объектам». К сожалению, IReadOnly-интерфейсы появились на 5 лет позже чем LINQ, и в нём не используются. Все входные и выходные коллекции LINQ-операций имеют базовый тип IEnumerable<>, исходя из ограниченных возможностей которого, многие операции подразумевают лишние затраты: полный последовательный перебор или даже создание промежуточных копий входных коллекций. Более того, возвращая из операций тот же IEnumerable<>, LINQ требует при дальнейшем использовании результата опять использовать полный перебор и создание промежуточных копий. В связи с этим, у меня давно зрела мысль «подружить» LINQ с IReadOnly-интерфейсами.
Найденные на просторах Интернета разработки на эту тему не удовлетворили меня. Например, библиотека Linq to Collections [4] предлагает эффективную замену лишь некоторых LINQ-операций только для интерфейса IReadOnlyList<>, слабо оптимизирована, и зачем то принудительно добавляет множество неоднозначных методов расширения для базовых типов. В ещё одном найденном проекте на эту тему, CountableSharp [5], предлагается небольшое число оптимизированных LINQ-операций только для интерфейса IReadOnlyCollection<>, в которых возвращается декоратор [6], делегирующий все обращения к базовому System.Linq.Enumerable и только свойство Count вычисляется заранее, не требуя полного перебора коллекции.
Далее я предлагаю к использованию мою библиотеку Collections.LINQ, оптимизирующую «LINQ к объектам» путём предоставления эффективной реализации большинства операций для коллекций, реализующих IReadOnly-интерфейсы.
Первым делом позволю себе небольшое отступление, позволяющее лучше понять и использовать проделанную мной работу. Как многие из вас, наверное, заметили, в ряду IReadOnly-интерфейсов явно не хватает интерфейса для множеств. Поэтому создадим его сами [7] в таком очевидном виде:
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<> [8] | |
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<> [9] (дополнительно к тому, что доступно для коллекций IReadOnlyCollection<>) | |
Contains() | сразу возвращает результат используя метод Contains() |
Distinct() | возвращает исходное IReadOnlyFiniteSet<>-множество |
Except(), Intersect(), Union() | возвращают IReadOnlyFiniteSet<>, в зависимости от свойства Count одно из исходных, пустое либо декоратор, при создании полностью перебирающий меньшее из входных множеств |
DefaultIfEmpty() | возвращает IReadOnlyFiniteSet<>, в зависимости от свойства Count исходное либо одно-элементное |
Reverse() | возвращает IReadOnlyFiniteSet<>, в зависимости от свойства Count исходное либо декоратор, создающий полную копию множества |
для списков типа IReadOnlyList<> [10] (дополнительно к тому, что доступно для коллекций 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-интерфейсами:
Чтобы удостовериться, что я ничего не упустил и сделал более эффективно, чем библиотечный System.Linq.Enumerable, я постоянно подглядывал в его исходники [13].
Использовать библиотеку 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 [14]. По просьбе читателей также создан nuget-пакет с библиотекой [15].
Автор: novar
Источник [16]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/69982
Ссылки в тексте:
[1] Проблемы использования IEnumerable: http://habrahabr.ru/post/193774/
[2] LINQ против LSP: http://habrahabr.ru/post/191770/
[3] LINQ: https://ru.wikipedia.org/wiki/Language_Integrated_Query"
[4] Linq to Collections: http://twistedoakstudios.com/blog/Post1585_linq-to-collections-beyond-ienumerablet
[5] CountableSharp: https://github.com/azyobuzin/CountableSharp
[6] декоратор: https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BA%D0%BE%D1%80%D0%B0%D1%82%D0%BE%D1%80_%28%D1%88%D0%B0%D0%B1%D0%BB%D0%BE%D0%BD_%D0%BF%D1%80%D0%BE%D0%B5%D0%BA%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F%29
[7] создадим его сами: https://github.com/novar0/CollectionLinq/blob/master/IReadOnlyFiniteSet.cs
[8] для коллекций типа IReadOnlyCollection<>: https://github.com/novar0/CollectionLinq/blob/master/CollectionLinq/Collection.cs
[9] для множеств типа IReadOnlyFiniteSet<>: https://github.com/novar0/CollectionLinq/blob/master/CollectionLinq/FiniteSet.cs
[10] для списков типа IReadOnlyList<>: https://github.com/novar0/CollectionLinq/blob/master/CollectionLinq/List.cs
[11] реализована: https://github.com/novar0/CollectionLinq/blob/master/CollectionLinq/StructuralEquatable.cs
[12] SymmetricExcept(): https://github.com/novar0/CollectionLinq/blob/master/CollectionLinq/FiniteSet.cs#L211
[13] исходники: http://referencesource.microsoft.com/System.Core/System/Linq/Enumerable.cs.html
[14] публичном проекте на github: https://github.com/novar0/CollectionLinq
[15] nuget-пакет с библиотекой: https://www.nuget.org/packages/CollectionLinq
[16] Источник: http://habrahabr.ru/post/237389/
Нажмите здесь для печати.