В первой части мы разобрали, как и во что компилятор превращает yield return и посмотрели, как строятся цепочки вызовов. Мы изучили методы LINQ без буферизации (Where, Select, ...) и методы с частичной буферизацией (Except, Intersect, ...)

Если вы не еще ознакомились с первой частью статьи, рекомендую вам это сделать, так как понимание того, о чем я рассказывал там, сильно поможет в понимании более сложных методов LINQ, про которые пойдет речь здесь

Сегодня мы перейдём к самым сложным для понимания методам с полной буферизацией: OrderBy, GroupBy и Join.

Введение

До этого момента мы думали что LINQ ленив, и поэтому длинные цепочки вызовов не бьют по памяти. Но заметим, что OrderBy не может отдать нам первый отсортированный элемент, если он не видел последний.

То есть, чтобы отсортировать данные мы физически обязаны прочитать их до конца. Тут то и разбивается вся магия ленивости и ключевого слова yield. Методы с полной буферизацией вынуждены материализовать (скопировать в память) всю входную последовательность, прежде чем вернуть хоть один элемент.

Кажется, что это сильно ударит по производительности. Однако разработчики .NET сделали эту материализацию максимально эффективной.

В этой статье мы заглянем под капот и подробно разберем методы OrderBy, GroupBy и Join. Мы напишем их упрощенные реализации и посмотрим как устроены эти самые механизмы оптимизации изнутри

OrderBy/ThenBy

Нам необходимо реализовать сортировку, которая сортирует последовательность по ключу. Причем такую, которая позволяет добавлять дополнительные уровни сортировки. Сигнатура самих этих методов довольно проста. Отличается она только тем, что возвращаемый тип в данном случае — это не IEnumerable<T>, а IOrderedEnumerable<T>. Посмотрим на него:

public interface IOrderedEnumerable<out TElement> : IEnumerable<TElement>
{
    IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey>(
        Func<TElement, TKey> keySelector,
        IComparer<TKey>? comparer,
        bool descending);
}

То есть это все тот же самый IEnumerable<T>, только с добавленным методом CreateOrderedEnumerable<TKey>(...).

Получается, из методов OrderBy/ThenBy нужно возвращать реализацию IOrderedEnumerable<T>, которая при обращении к ней будет:

Считывать всю последовательность в массив (без этого шага никак)
Проходить по всей цепочке и вычисляет ключи сортировки
Сортировать полученный массив, отдавая больший приоритет родительскому уровню
И наконец, отдавать полученный массив поэлементно

Но как же реализовать эти самые уровни сортировки? Давайте подумаем.

Первое, что приходит в голову — создать список селекторов:

List<Func<TSource, TKey>> _keySelectors;

Но тут же возникает проблема: тип ключа TKey на каждом уровне может быть разным! Например, в OrderBy мы сортируем по int, а в ThenBy — по string. Мы не можем положить их в один List<T>, потому что TKey — это строгий дженерик.

Как же разработчики .NET выкрутились из этой ситуации? Они разделили ответственность, используя паттерн, напоминающий связный список.

Они ввели абстрактный базовый класс OrderedEnumerable<TElement> (без указания типа ключа!). Он хранит ссылку на исходную последовательность и ссылку на родительский уровень сортировки.

public abstract class OrderedEnumerable<TElement> : IOrderedEnumerable<TElement>
{
    protected readonly IEnumerable<TElement> Source;
    protected readonly OrderedEnumerable<TElement>? Parent;

    protected OrderedEnumerable(
        IEnumerable<TElement> source,
        OrderedEnumerable<TElement>? parent)
    {
        Source = source;
        Parent = parent;
    }

    protected int[] SortedMap(TElement[] elements)
    {
        var count = elements.Length;
        ComputeKeys(elements, count);   

        var map = new int[count];
        for (var i = 0; i < count; i++) 
            map[i] = i;

        Array.Sort(map, (a, b) =>
        {
            var cmp = CompareKeys(a, b);
            return cmp != 0 ? cmp : a - b;
        });

        return map;
    }

    public IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey>(
        Func<TElement, TKey> keySelector,
        IComparer<TKey>? comparer,
        bool descending)
        => new OrderedEnumerable<TElement, TKey>(Source, keySelector, comparer, descending, this);

    internal abstract void ComputeKeys(TElement[] elements, int count);
    internal abstract int CompareKeys(int index1, int index2);
    
    public abstract IEnumerator<TElement> GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Базовый класс ничего не знает о типе ключа. Эту ответственность мы делегируем конкретному наследнику — OrderedEnumerable<TElement, TKey>.

Благодаря этому трюку каждый новый уровень (ThenBy) может иметь свой собственный тип ключа, оставаясь при этом в одной типобезопасной цепочке через общего нетипизированного предка.

Базовый класс определяет два абстрактных метода: ComputeKeys и CompareKeys — они будут реализованы наследниками. Также базовый класс содержит общий алгоритм сортировки индексов (SortedMap), который использует эти самые методы. Мы сортируем индексы, а не сами элементы, потому что это:

эффективно по памяти, так как мы не копируем тяжелые объекты,
гарантирует стабильность сортировки (при равенстве индексы сохраняют исходный порядок),
упрощает каскадное сравнение (каждый уровень работает со своим массивом ключей, обращаясь к родительскому при необходимости)

В конкретном наследнике мы будем хранить селектор ключа, компаратор и направление, а также массив вычисленных ключей. В его методах ComputeKeys и CompareKeys кроется самая красивая часть. Они работают по принципу рекурсии:

ComputeKeys: Сначала вызывает родительский метод, чтобы все вышестоящие уровни заполнили свои массивы ключей, а затем вычисляет свои собственные ключи для каждого элемента буфера.
CompareKeys: Сначала запрашивает результат сравнения у родителя. И только если родитель вернул 0 (то есть элементы равны по всем предыдущим уровням), сравнивает свои ключи с учётом направления.

public sealed class OrderedEnumerable<TElement, TKey> : OrderedEnumerable<TElement>
{
    private readonly Func<TElement, TKey> _keySelector;
    private readonly IComparer<TKey> _comparer;
    private readonly bool _descending;
    private TKey[] _keys = [];

    public OrderedEnumerable(
        IEnumerable<TElement> source,
        Func<TElement, TKey> keySelector,
        IComparer<TKey>? comparer,
        bool descending,
        OrderedEnumerable<TElement>? parent)
        : base(source, parent)
    {
        _keySelector = keySelector;
        _comparer = comparer ?? Comparer<TKey>.Default;
        _descending = descending;
    }

    internal override void ComputeKeys(TElement[] elements, int count)
    {
        Parent?.ComputeKeys(elements, count);
        
        _keys = new TKey[count];
        for (var i = 0; i < count; ++i)
            _keys[i] = _keySelector(elements[i]);
    }

    internal override int CompareKeys(int index1, int index2)
    {
        if (Parent != null)
        {
            var cmp = Parent.CompareKeys(index1, index2);
            if (cmp != 0) return cmp;
        }
        
        var compare = _comparer.Compare(_keys[index1], _keys[index2]);
        return _descending ? -compare : compare;
    }

    public override IEnumerator<TElement> GetEnumerator()
    {
        var buffer = Source.ToArray();
        if (buffer.Length == 0) yield break;
        
        var map = SortedMap(buffer);
        
        foreach (var index in map)
            yield return buffer[index];
    }
}

Когда вызывается GetEnumerator, последний уровень в цепочке берёт исходную последовательность, копирует её в массив (та самая полная буферизация), а затем сортирует массив индексов, используя каскадное сравнение. После сортировки итератор просто проходит по отсортированным индексам и отдаёт элементы из буфера в нужном порядке.

Таким образом, абстрактный класс выступает связующим звеном: он обеспечивает общий механизм, не навязывая тип ключа. Мы можем строить цепочки с произвольным количеством уровней, сохраняя типобезопасность и производительность.

Реализуем теперь сами методы:

public static partial class EnumerableExtensions
{
    public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
        this IEnumerable<TSource> source,
        Func<TSource, TKey> keySelector,
        IComparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(source);
        ArgumentNullException.ThrowIfNull(keySelector);

        return new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, false, null);
    }
    
    public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(
        this IEnumerable<TSource> source,
        Func<TSource, TKey> keySelector,
        IComparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(source);
        ArgumentNullException.ThrowIfNull(keySelector);

        return new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, true, null);
    }
    
    public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey>(
        this IOrderedEnumerable<TSource> source,
        Func<TSource, TKey> keySelector,
        IComparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(source, nameof(source));
        ArgumentNullException.ThrowIfNull(keySelector, nameof(keySelector));
        
        return source.CreateOrderedEnumerable(keySelector, comparer, false);
    }

    public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey>(
        this IOrderedEnumerable<TSource> source,
        Func<TSource, TKey> keySelector,
        IComparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(source, nameof(source));
        ArgumentNullException.ThrowIfNull(keySelector, nameof(keySelector));
        
        return source.CreateOrderedEnumerable(keySelector, comparer, true);
    }  
}

Обратите внимание на ThenBy: ему вообще не нужно знать, как устроена сортировка. Он просто вызывает CreateOrderedEnumerable у источника, передавая себя в качестве родителя parent. Вся магия инкапсулирована внутри классов OrderedEnumerable.

GroupBy

Метод GroupBy также относится к методам с полной буферизацией. Мы разбиваем исходные данные на группы по ключу. Мы не можем отдать первую группу, пока не убедимся, что в самом конце входной последовательности нет элемента с таким же ключом.

Давайте подумаем, как хранить эти самые группы в памяти, пока мы их собираем?

В голову приходит вариант со словарем:

var dict = new Dictionary<TKey, List<TElement>>();

Этот вариант рабочий, но не прижился в недрах.NET, так как:

Для каждой новой группы создается отдельный объект List<TElement>, у которого есть свой оверхед (внутренний массив, счетчик). Плюс сам Dictionary хранит некоторую метаинформацию. Когда уникальных ключей тысячи, эти микро‑аллокации складываются в огромное давление на сборщик мусора.
LINQ имеет строгий контракт: порядок возвращаемых групп должен строго соответствовать порядку первого появления уникальных ключей в исходной последовательности. Стандартный Dictionary не гарантирует порядок при итерации. Более того, при внутреннем Resize (расширении) он может полностью перемешать элементы.

Разработчики.NET поняли: готовые коллекции не подходят. Им пришлось написать специальную хеш‑таблицу с нуля, которая одновременно решает проблему памяти и жестко фиксирует порядок вставки.

Знакомьтесь: Lookup<TKey, TElement> и Grouping<TKey, TElement>

Grouping

Класс Grouping представляет собой одну группу (все элементы с одинаковым ключом). Но если вы заглянете в его исходники, то удивитесь: это не просто обертка над массивом. Один объект Grouping выполняет сразу три роли:

public class Grouping<TKey, TElement> : IGrouping<TKey, TElement>
{
    internal TKey _key = default!;
    internal int _hashCode;

    // 1. Динамический массив (аналог List<T>, но без лишнего оверхеда)
    // Хранит сами элементы группы
    private TElement[] _elements = new TElement[1]; 
    private int _count;

    // 2. Связный список для разрешения коллизий хеш-таблицы
    internal Grouping<TKey, TElement>? _hashNext;

    // 3. Связный список для сохранения порядка вставки групп!
    internal Grouping<TKey, TElement>? _next;
    // ...
}

Обратите внимание на поле _next. Именно оно связывает все объекты Grouping в циклический односвязный список. Это гениальный ход: он позволяет обходить все группы строго в том порядке, в котором они были созданы (то есть в порядке первого появления ключа), совершенно не завися от того, как они распределены по бакетам в хеш-таблице.

Класс Grouping реализовывает интерфейс IGrouping<TKey, TElement>. Посмотрим на него:

public interface IGrouping<out TKey, out TElement> : IEnumerable<TElement>, IEnumerable
{
    TKey Key { get; }
}

То есть, это тот же самый IEnumerable, только с добавлением поля Key. В самом классе Grouping этому ключу присваивается значение по умолчанию, но, как мы увидим позже, это поле заполняется немного в другом месте из-за оптимизаций.

Заметим, что IEnumerable<> добавляет в класс Grouping метод GetEnumerator() и позволяет итерироваться по массиву элементов _elements:

public IEnumerator<TElement> GetEnumerator()
{
    for (var i = 0; i < _count; ++i)
        yield return _elements[i];
}

Также есть метод Add(), с помощью которого можно добавить элемент в группу.

Lookup

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

private readonly IEqualityComparer<TKey> _comparer;// 0. Сравниватель ключей
private Grouping<TKey, TElement>?[] _buckets;      // 1. Массив бакетов (сама хеш-таблица)
private Grouping<TKey, TElement>? _lastGrouping;   // 2. Хвост циклического списка
private int _count;                                // 3. Счетчик (но не элементов, а групп!)

Массив buckets — это классическая хеш‑таблица. Но так как могут случаться коллизии , то в одну ячейку массива может попасть несколько разных групп. Именно для решения этой проблемы и нужно поле hashNext в классе Grouping.

Каждая ячейка _buckets[i] хранит ссылку на первый Grouping, который в нее попал. Если в ту же ячейку попадает вторая группа (коллизия), она записывается в поле _hashNext первой группы. Получается обычный односвязный список.

Вся эта магия происходит в методе GetGrouping, который достает группу по ключу и, если группы с таким ключом нет, создает новую.

public Grouping<TKey, TElement>? GetGrouping(TKey key, bool create)
{
    var hashCode = ...;   // Вычисление хэша
    var bucketIndex = hashCode % _buckets.Length;

    // 1. Ищем группу в хеш-таблице (разрешаем коллизии через _hashNext)
    for (var group = _buckets[bucketIndex]; group != null; group = group._hashNext)
    {
        if (group._hashCode == hashCode && _comparer.Equals(group._key, key))
            return group; // Группа уже есть, просто вернем её
    }

    if (!create) return null;

    // Если массива не хватает для создания новой группы, увеличиваем массив
    if (_count == _buckets.Length)
        Resize();
    bucketIndex = hashCode % _buckets.Length;

    // 2. Группы нет. Создаем новую!
    // Обратите внимание, что значение поля _key мы указываем именно отсюда!
    // Мы не используем конструктор с параметрами для максимальной производительности
    var newGroup = new Grouping<TKey, TElement> { _key = key, _hashCode = hashCode };
    
    // Вставляем в хеш-таблицу (в начало списка коллизий текущего бакета)
    newGroup._hashNext = _buckets[bucketIndex];
    _buckets[bucketIndex] = newGroup;

    // 3. Вставляем в циклический список, чтобы сохранить порядок!
    if (_lastGrouping is null)
    {
        // Если это самая первая группа, она замыкается сама на себя
        newGroup._next = newGroup; 
    }
    else
    {
        // Вставляем новую группу в конец циклического списка
        newGroup._next = _lastGrouping._next;
        _lastGrouping._next = newGroup;
    }
    _lastGrouping = newGroup; // Сдвигаем указатель "хвоста"

    return newGroup;
}

Отдельное внимание обратим на пугающий метод Resize(). Он вызывается, когда количество уникальных групп count достигает длины массива _buckets, и занимается тем, что увеличивает этот самый массив, сохраняя порядок групп.

private void Resize()
{
    // Создаем новый массив бакетов большего размера
    var newBuckets = new Grouping<TKey, TElement>?[checked(_count * 2 + 1)];
    var group = _lastGrouping!;
    
    // Проходим по всем группам
    do
    {
        group = group._next!; // Используем циклический список для обхода!
        
        // Пересчитываем новый индекс бакета
        var bucketIndex = group._hashCode % newBuckets.Length;
        
        // Перестраиваем тольько цепочки коллизий (_hashNext)
        group._hashNext = newBuckets[bucketIndex];
        newBuckets[bucketIndex] = group;
        
    } while (group != _lastGrouping); // Пока не пройдем полный круг
    
    _buckets = newBuckets;
}

Обратите внимание на две критически важные вещи:

Для обхода всех групп при ресайзе используется циклический список next, а не старый массив buckets. Это гениально, потому что старый массив сейчас бесполезен, а циклический список содержит все группы без исключений.
При ресайзе мы перестраиваем только_hashNext. Поля _next вообще не трогаются!

Именно поэтому Lookup гарантированно сохраняет порядок групп. Даже когда хеш‑таблица внутри него полностью перекраивается и расширяется, циклический список, отвечающий за порядок, остается нетронутым.

Стоит упомянуть, что мы должны уметь итерироваться по Lookup. Это значит, что класс Lookup должен реализовывать интерфейс IEnumerable<>, и вот как он его реализует:

public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator()
{
    if (_lastGrouping == null) yield break;
    
    // Стартуем с "головы" (элемент сразу после хвоста)
    var group = _lastGrouping;
    do
    {
        group = group._next!;
        yield return group;
    } while (group != _lastGrouping); // Идем, пока не вернемся к хвосту
}

Мы просто идем по циклическому списку. Никаких массивов, никаких словарей. Чистый O(N) обход с нулевыми дополнительными аллокациями.

Ну и напоследок, в классе Lookup есть фабричный метод Lookup.Create. Именно здесь происходит тот самый «момент истины», где LINQ жадно поглощает исходные данные. Здесь происходит полная материализация последовательности.

public static Lookup<TKey, TElement> Create<TSource>(...)
{
    var lookup = new Lookup<TKey, TElement>(comparer);
    
    // Жадное поглощение всей последовательности!
    foreach (var item in source) 
    {
        var key = keySelector(item);
        var group = lookup.GetGrouping(key, create: true);
        group?.Add(elementSelector(item));
    }
    
    return lookup;
}

Мы проходимся по всему source и делаем всю тяжелую работу:

Из элемента source достаем ключ
Достаем из lookup нужную группу по ключу. Если такой нет, то создаем ее.
Добавляем выбранный элемент в эту группу

Теперь, когда мы понимаем, какой титанический труд скрывается за кулисами, давайте посмотрим на сам метод‑расширение GroupBy:

public static partial class EnumerableExtensions
{
    public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(
        this IEnumerable<TSource> source,
        Func<TSource, TKey> keySelector,
        IEqualityComparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(source, nameof(source));
        ArgumentNullException.ThrowIfNull(keySelector, nameof(keySelector));

        return GroupByIterator(source, keySelector, x => x, comparer);
    }
    
    public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(
        this IEnumerable<TSource> source,
        Func<TSource, TKey> keySelector,
        Func<TSource, TElement> elementSelector,
        IEqualityComparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(source, nameof(source));
        ArgumentNullException.ThrowIfNull(keySelector, nameof(keySelector));
        ArgumentNullException.ThrowIfNull(elementSelector, nameof(elementSelector));

        eturn GroupByIterator(source, keySelector, elementSelector, comparer);
    }

    private static IEnumerable<IGrouping<TKey, TElement>> GroupByIterator<TSource, TKey, TElement>(
        IEnumerable<TSource> source,
        Func<TSource, TKey> keySelector,
        Func<TSource, TElement> elementSelector,
        IEqualityComparer<TKey>? comparer = null)
    {
        var lookup = Models.Lookup<TKey, TElement>.Create(
            source,
            keySelector,
            elementSelector,
            comparer);
        
        foreach (var group in lookup)
            yield return group;
    }
}

В данном случае yield используется исключительно для отложенного старта. Он не дает GroupBy начать работу, пока вы не спросите у него первый элемент. Но как только вы спросите — он мгновенно материализует в памяти всю последовательность целиком.

Join

Если писать метод Join в лоб, то получится примерно следующее:

// Наивная реализация (O(N * M))
foreach (var outerItem in outer)
    foreach (var innerItem in inner)
        if (outerKeySelector(outerItem).Equals(innerKeySelector(innerItem)))
            yield return resultSelector(outerItem, innerItem);

Данный код работает, но очень медленно. Если в коллекциях по 10 000 элементов, то придется сделать 100 000 000 сравнения.

В реляционных базах данных для таких задач используется алгоритм Hash Join. Его суть проста: мы берем одну таблицу, строим по ней хеш‑таблицу (чтобы искать за O(1)), а затем просто проходимся по второй таблице и ищем совпадения в хеш‑таблице. Сложность падает до O(N+M).

Но перед разработчиками LINQ встал архитектурный вопрос: какую из двух коллекций превращать в хеш‑таблицу, а по какой идти потоком?

LINQ всегда делает один и тот же выбор. Вторая коллекция (inner) полностью буферизуется в Lookup, а по первой (outer) мы идем лениво.

Такой выбор был сделан, потому что outer (внешняя коллекция) — это обычно наш «основной» поток данных. Если мы его полностью загрузим в память, мы потеряем главное преимущество LINQ — возможность обрабатывать бесконечные или огромные потоки данных. Превращая в Lookup только inner, мы жертвуем памятью под одну коллекцию, но сохраняем способность лениво стримить outer.

Давайте посмотрим, как это выглядит в коде:

private static IEnumerable<TResult> JoinIterator<TOuter, TInner, TKey, TResult>(...)
{
    // 1. Получаем перечислитель для outer
    using var outerEnumerator = outer.GetEnumerator();
    
    // 2. Оптимизация №1: Если outer пуст, мы даже не трогаем inner!
    if (!outerEnumerator.MoveNext())
        yield break;

    // 3. Превращаем inner в хеш-таблицу (Lookup)
    var lookup = Models.Lookup<TKey, TInner>.CreateForJoin(inner, innerKeySelector, comparer);
    
    // 4. Оптимизация №2: Если inner оказался пуст, смысла продолжать нет
    if (lookup.Count == 0)
        yield break;

    // 5. Проходим по outer потоком
    do
    {
        var outerItem = outerEnumerator.Current;
      
        // 6. Ищем совпадения в Lookup (create: false - ничего не создаем!)
        var group = lookup.GetGrouping(outerKeySelector(outerItem), create: false);
        if (group is null) continue;

        // Если группа нашлась, отдаем все пары
        foreach (var innerItem in group)
            yield return resultSelector(outerItem, innerItem);
    }
    while (outerEnumerator.MoveNext());
}

CreateForJoin — это удобная обертка над Create с селектором x => x, так как в Join элементы inner хранятся как есть, без дополнительных проекций.

При поиске ключа из outer мы вызываем GetGrouping(..., create: false). Если бы флаг был true, для каждого элемента outer, не нашедшего пару, мы бы аллоцировали новую пустую группу, устроив утечку памяти.

Ну и сам метод будет выглядеть вот так:

public static partial class EnumerableExtensions
{
    public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult>(
        this IEnumerable<TOuter> outer,
        IEnumerable<TInner> inner,
        Func<TOuter, TKey> outerKeySelector,
        Func<TInner, TKey> innerKeySelector,
        Func<TOuter, TInner, TResult> resultSelector,
        IEqualityComparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(outer, nameof(outer));
        ArgumentNullException.ThrowIfNull(inner, nameof(inner));
        ArgumentNullException.ThrowIfNull(outerKeySelector, nameof(outerKeySelector));
        ArgumentNullException.ThrowIfNull(innerKeySelector, nameof(innerKeySelector));
        ArgumentNullException.ThrowIfNull(resultSelector, nameof(resultSelector));

        return JoinIterator(outer, inner, outerKeySelector, innerKeySelector, resultSelector, comparer);
    }
}

Заключение

Во второй части статьи мы разобрали основные методы LINQ с полной буферизацией и увидели, какая большая и сложная работа с памятью стоит за ними.

Мы разобрали методы OrderBy, GroupBy и Join и поняли, почему они вынуждены нарушать заветы ленивости:

OrderBy — использует абстрактный класс и каскадное сравнение, чтобы сортировать индексы, а не сами объекты. Это экономит память и гарантирует стабильность.
GroupBy — разворачивает в памяти специализированный Lookup с циклическим связным списком. Это позволяет сохранить порядок первого появления ключей и избежать лишних аллокаций.
Join — применяет асимметричный Hash Join. Он полностью буферизует inner коллекцию в Lookup, но зато позволяет лениво проходить по outer, сохраняя возможность работать с огромными или даже бесконечными потоками данных.

Понимание этих механизмов — это не просто академическое упражнение, а инструмент, который может спасти вас от реальных проблем.

Репозиторий с полной реализацией всех методов, о которых шла речь: [ссылка]

Ленивый LINQ: разбираем yield и ленивые вычисления по кирпичикам. Часть 2