Покращуємо 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<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.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.