# Сортировки в C\#: OrderBy\.OrderBy или OrderBy\.ThenBy? Разбираемся, что эффективнее и почему Предположим, есть задача: нужно отсортировать коллекцию по нескольким ключам\. В C\# это можно сделать с помощью вызовов OrderBy\(\)\.OrderBy\(\) или OrderBy\(\)\.ThenBy\(\)\. Но в чём разница между этими вызовами? Чтобы ответить на этот вопрос, придётся покопаться в исходниках\. ![0991_OrderBy_ThenBy_ru/image1.png](https://import.viva64.com/docx/blog/0991_OrderBy_ThenBy_ru/image1.png) Статья состоит из трёх основных разделов: * **Предыстория**\. Для тех, кто любит затравки\. История о том, откуда вообще возникла идея провести исследование и изучить, в чём разница между _OrderBy\(\)\.OrderBy\(\)_ и _OrderBy\(\)\.ThenBy\(\)_\. * **Сравнение эффективности**\. Изучаем отличия типов сортировок с точки зрения производительности и потребления памяти\. * **Отличия в поведении**\. Погружаемся в исходники \.NET и разбираемся, из\-за чего возникают отличия в эффективности работы рассматриваемых способов сортировки\. ## Предыстория Всё началось со статьи "[Подозрительные сортировки в Unity, ASP\.NET Core и не только](https://pvs-studio.ru/ru/blog/posts/csharp/0928/)"\. В ней рассматривались случаи, когда последовательность вызовов _OrderBy\(\)\.OrderBy\(\)_ могла приводить к ошибкам\. Однако оказалось, что порой разработчики намеренно сортируют с помощью _OrderBy\(\)\.OrderBy\(\)_, а не _OrderBy\(\)\.ThenBy\(\)_\. Рассмотрим пример\. Допустим, есть класс _Wrapper_ и массив экземпляров этого типа: ```cpp class Wrapper { public int Primary { get; init; } public int Secondary { get; init; } } var arr = new Wrapper[] { new() { Primary = 1, Secondary = 2 }, new() { Primary = 0, Secondary = 1 }, new() { Primary = 2, Secondary = 1 }, new() { Primary = 2, Secondary = 0 }, new() { Primary = 0, Secondary = 2 }, new() { Primary = 0, Secondary = 3 }, }; ``` Мы хотим отсортировать этот массив: сначала по значению _Primary_, затем – по _Secondary_\. По ошибке сортировку можно выполнить так: ```cpp var sorted = arr.OrderBy(p => p.Primary) .OrderBy(p => p.Secondary); .... ``` Результат: ```cpp Primary: 2 Secondary: 0 Primary: 0 Secondary: 1 Primary: 2 Secondary: 1 Primary: 0 Secondary: 2 Primary: 1 Secondary: 2 Primary: 0 Secondary: 3 ``` Из\-за ошибки мы получили не тот результат, который был нужен\. Правильно отсортировать коллекцию можно через последовательность вызовов _OrderBy\(\)\.ThenBy\(\)_: ```cpp var sorted = arr.OrderBy(p => p.Primary) .ThenBy(p => p.Secondary); .... ``` Результат: ```cpp Primary: 0 Secondary: 1 Primary: 0 Secondary: 2 Primary: 0 Secondary: 3 Primary: 1 Secondary: 2 Primary: 2 Secondary: 0 Primary: 2 Secondary: 1 ``` Однако получить правильный результат можно и через последовательность вызовов _OrderBy\(\)\.OrderBy\(\)_, нужно только поменять вызовы местами\. Так неправильно: ```cpp var sorted = arr.OrderBy(p => p.Primary) .OrderBy(p => p.Secondary); ``` Так правильно: ```cpp var sorted = arr.OrderBy(p => p.Secondary) .OrderBy(p => p.Primary); ``` Выходит, чтобы получить нужный результат, можно использовать оба способа: ```cpp // #1 var sorted1 = arr.OrderBy(p => p.Secondary) .OrderBy(p => p.Primary); // #2 var sorted2 = arr.OrderBy(p => p.Primary) .ThenBy(p => p.Secondary); ``` Как по мне, второй вариант читается лучше\. Когда встречаешь вызов _OrderBy\(\)\.OrderBy\(\)_, задаёшься вопросом: нет ли в нём [ошибки](https://pvs-studio.ru/ru/blog/examples/v3078/)? С _OrderBy\(\)\.ThenBy\(\)_ иначе: код читается легче, замысел разработчика понятен\. Однако эти способы сортировки отличаются не только внешне: у них разная скорость работы и потребление памяти\. ## Сравнение эффективности Для экспериментов возьмём такой код: ```cpp struct Wrapper { public int Primary { get; init; } public int Secondary { get; init; } } Wrapper[] arr = ....; // #1 _ = arr.OrderBy(p => p.Secondary) .OrderBy(p => p.Primary) .ToArray(); // #2 _ = arr.OrderBy(p => p.Primary) .ThenBy(p => p.Secondary) .ToArray(); ``` Зафиксируем основные моменты: * _Wrapper_ – структура с двумя целочисленными свойствами\. Они будут использоваться в качестве ключей для сортировок; * _arr_ – массив экземпляров _Wrapper_, который нужно отсортировать\. Как он получается – для тестов неважно\. Измерять будем только скорость сортировки и получения итогового массива; * два способа сортировки: первый – через вызовы _OrderBy\(\)\.OrderBy\(\)_, второй – _OrderBy\(\)\.ThenBy\(\)_; * вызов _ToArray\(\)_ нужен, чтобы инициировать выполнение сортировки\. Для тестов я взял два набора сгенерированных тестовых данных \(экземпляры типа _Wrapper_\)\. В первом наборе разброс значений _Primary_ и _Secondary_ больше, во втором – меньше\. В _arr_ записывал от 10 до 1 000 000 объектов _Wrapper_ и сортировал их\. Тестовый проект работает на \.NET 6\. ### Производительность Время работы измерял с помощью [BenchmarkDotNet](https://benchmarkdotnet.org/)\. Ниже привожу результаты времени выполнения сортировки и получения массива\. Абсолютные значения не так интересны – важна разница между способами сортировок\. Набор данных \#1: |arr\\\.Length|10|100|1 000|10 000|100 000|1 000 000| |---|---|---|---|---|---|---| |OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|619 ns|9 us|170 us|2 ms|25\\\.8 ms|315 ms| |OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|285 ns|4\\\.5 us|100 us|1\\\.4 ms|20\\\.4 ms|271 ms| |\_Соотношение\_|\_2\\\.17\_|\_2\_|\_1\\\.7\_|\_1\\\.43\_|\_1\\\.26\_|\_1\\\.16\_| Набор данных \#2: |arr\\\.Length|10|100|1 000|10 000|100 000|1 000 000| |---|---|---|---|---|---|---| |OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|553\\\.3 ns|8\\\.7 us|154 us|2\\\.1 ms|29\\\.5 ms|364 ms| |OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|316\\\.4 ns|4\\\.2 us|80 us|1\\\.1 ms|16\\\.9 ms|240 ms| |\_Соотношение\_|\_1\\\.75\_|\_2\\\.07\_|\_1\\\.93\_|\_1\\\.91\_|\_1\\\.75\_|\_1\\\.52\_| Можно пойти дальше и посмотреть разницу во времени, если выполнять не одну операцию сортировки, а несколько\. Для этого воспользуемся циклом _for_: ```cpp for (int i = 0; i < iterNum; ++i) { // Perform sorting } ``` Время сортировки \(в секундах\) 1 000 000 экземпляров типа _Wrapper_: |Количество итераций|1|10|100| |---|---|---|---| |OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|0\\\.819|6\\\.52|65\\\.15| |OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|0\\\.571|5\\\.21|42\\\.94| |\_Соотношение\_|\_1\\\.43\_|\_1\\\.25\_|\_1\\\.30\_| Согласитесь, разница в 20 секунд – повод призадуматься\. ### Использование памяти С памятью похожая история – _OrderBy\(\)\.OrderBy\(\)_ потребляет больше\. Сильнее заметно на больших объёмах данных и нескольких итерациях\. Разница в количестве создаваемых объектов на одной итерации: |Тип|OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)| |---|---|---| |Int32\\\[\\\]|4|3| |Comparison|2|1| |Wrapper\\\[\\\]|3|2| Из таблицы видно, что вызовы _OrderBy\(\)\.OrderBy\(\)_ генерируют на два массива больше\. На тесте, где было 100 операций сортировки, это привело к разнице в 1Гб выделенной памяти\. Важно отметить, что чем больше размер сортируемой коллекции, тем больше размер "лишних" массивов\. Как следствие, увеличивается и размер потребляемой памяти\. ## Отличия в поведении Пришло время заглянуть "под капот"\. Напомню, что мы рассматриваем два способа сортировки: ```cpp // #1 _ = arr.OrderBy(p => p.Secondary) .OrderBy(p => p.Primary) .ToArray(); // #2 _ = arr.OrderBy(p => p.Primary) .ThenBy(p => p.Secondary) .ToArray(); ``` Чтобы понять разницу, нужно проанализировать: * методы, которые вызываются; * состояние объектов, для которых вызываются методы; * ход потока исполнения\. Исходники \.NET 6 возьмём с [GitHub](https://github.com/dotnet/runtime)\. ### Методы верхнего уровня Нам нужно разобрать три метода верхнего уровня: _OrderBy_, _ThenBy_ и _ToArray_\. Рассмотрим каждый из них\. **OrderBy** _OrderBy_ – метод расширения, который возвращает экземпляр типа _OrderedEnumerable_: ```cpp public static IOrderedEnumerable OrderBy(this IEnumerable source, Func keySelector) => new OrderedEnumerable(source, keySelector, null, false, null); ``` Опускаемся в конструктор _OrderedEnumerable_: ```cpp internal OrderedEnumerable( IEnumerable source, Func keySelector, IComparer? comparer, bool descending, OrderedEnumerable? parent ) : base(source) { .... _parent = parent; _keySelector = keySelector; _comparer = comparer ?? Comparer.Default; _descending = descending; } ``` Здесь интересен вызов конструктора базового типа – _base\(source\)_\. Базовый тип – _OrderedEnumerable_\. Конструктор выглядит так: ```cpp protected OrderedEnumerable(IEnumerable source) => _source = source; ``` Зафиксируем: в результате вызова _OrderBy_ создаётся экземпляр _OrderedEnumerable_\. Его состояние определяется полями: * \_source; * \_parent; * \_keySelector; * \_comparer; * \_descending\. **ThenBy** _ThenBy_ \- метод расширения: ```cpp public static IOrderedEnumerable ThenBy(this IOrderedEnumerable source, Func keySelector) { .... return source.CreateOrderedEnumerable(keySelector, null, false); } ``` В нашем случае тип переменной _source_ – _OrderedEnumerable_\. Посмотрим на реализацию метода _CreateOrderedEnumerable_: ```cpp IOrderedEnumerable IOrderedEnumerable .CreateOrderedEnumerable(Func keySelector, IComparer? comparer, bool descending) => new OrderedEnumerable(_source, keySelector, comparer, @descending, this); ``` Видно, что вызывается уже знакомый нам конструктор типа _OrderedEnumerable_ \(мы рассмотрели его в разделе про _OrderBy_\)\. Отличаются аргументы вызова, и, как следствие, состояние созданного объекта\. Зафиксируем: _ThenBy_, как и _OrderBy_, в нашем случае возвращает экземпляр типа _OrderedEnumerable_\. **ToArray** _ToArray_ – метод расширения: ```cpp public static TSource[] ToArray(this IEnumerable source) { .... return source is IIListProvider arrayProvider ? arrayProvider.ToArray() : EnumerableHelpers.ToArray(source); } ``` В обоих рассматриваемых случаях сортировки _source_ – экземпляры типа _OrderedEnumerable_\. Этот тип реализует интерфейс _IIlistProvider_, значит исполнение пойдёт через вызов _arrayProvider\.ToArray\(\)_\. По факту будет вызван метод _OrderedEnumerable\.ToArray_: ```cpp public TElement[] ToArray() { Buffer buffer = new Buffer(_source); int count = buffer._count; if (count == 0) { return buffer._items; } TElement[] array = new TElement[count]; int[] map = SortedMap(buffer); for (int i = 0; i != array.Length; i++) { array[i] = buffer._items[map[i]]; } return array; } ``` И здесь начнутся ключевые различия\. Прежде чем мы продолжим погружение, нужно узнать состояние объектов, с которыми мы будем работать\. ### Состояния объектов OrderedEnumerable Возвращаемся к исходным примерам: ```cpp // #1 _ = arr.OrderBy(p => p.Secondary) // Wrapper[] -> #1.1 .OrderBy(p => p.Primary) // #1.1 -> #1.2 .ToArray(); // #1.2 -> Wrapper[] // #2 _ = arr.OrderBy(p => p.Primary) // Wrapper[] -> #2.1 .ThenBy(p => p.Secondary) // #2.1 -> #2.2 .ToArray(); // #2.2 -> Wrapper[] ``` Нужно сравнить попарно четыре объекта: * \#1\.1 и \#2\.1 – объекты, порождённые первыми вызовами _OrderBy_ в обоих примерах; * \#1\.2 и \#2\.2 – объекты, порождённые вторым вызовом _OrderBy_ в первом примере и _ThenBy_ во втором\. В результате получаем 2 таблицы для сравнения состояний объектов\. Состояния объектов, порождённых первыми вызовами _OrderBy_: |Поле|Object \\\#1\\\.1|Object \\\#2\\\.1| |---|---|---| |\\\_source|arr|arr| |\\\_comparer|Comparer\\\.Default|Comparer\\\.Default| |\\\_descending|false|false| |\\\_keySelector|p \\\=\\\> p\\\.Secondary|p \\\=\\\> p\\\.Primary| |\\\_parent|null|null| Эта пара одинакова\. Исключение – селекторы\. Состояния объектов, порождённых вторым вызовом _OrderBy_ \(\#1\.2\) и _ThenBy_ \(\#2\.2\): |Поле|Object \\\#1\\\.2|Object \\\#2\\\.2| |---|---|---| |\\\_source|\*\*Object \\\#1\\\.1\*\*|\*\*arr\*\*| |\\\_comparer|Comparer\\\.Default|Comparer\\\.Default| |\\\_descending|false|false| |\\\_keySelector|p \\\=\\\> p\\\.Primary|p \\\=\\\> p\\\.Secondary| |\\\_parent|\*\*null\*\*|\*\*Object \\\#2\\\.1\*\*| Селекторы тоже различаются, это ожидаемо\. Что более интересно – отличаются поля _\_source_ и _\_parent_\. Состояние объекта выглядит более правильным в случае с вызовом _ThenBy_ \(\#2\.2\): ссылка на исходную коллекцию сохраняется, при этом есть "родитель" – результат предыдущей сортировки\. ### Поток исполнения Теперь разберём, как состояние объектов влияет на поток исполнения\. Вернёмся к методу _ToArray_: ```cpp public TElement[] ToArray() { Buffer buffer = new Buffer(_source); int count = buffer._count; if (count == 0) { return buffer._items; } TElement[] array = new TElement[count]; int[] map = SortedMap(buffer); for (int i = 0; i != array.Length; i++) { array[i] = buffer._items[map[i]]; } return array; } ``` Помним, что поле _\_source_ отличается у объектов, полученных разными вызовами: * _OrderBy\(\)\.OrderBy\(\)_: ссылается на экземпляр _OrderedEnumerable_; * _OrderBy\(\)\.ThenBy\(\)_: ссылается на экземпляр _Wrapper\[\]_\. Посмотрим на определение типа _Buffer_: ```cpp internal readonly struct Buffer { internal readonly TElement[] _items; internal readonly int _count; internal Buffer(IEnumerable source) { if (source is IIListProvider iterator) { TElement[] array = iterator.ToArray(); _items = array; _count = array.Length; } else { _items = EnumerableHelpers.ToArray(source, out _count); } } } ``` Здесь начинается расхождение в поведении: * для вызовов _OrderBy\(\)\.OrderBy\(\)_ исполнение идёт по then\-ветви, так как _OrderedEnumerable_ реализует интерфейс _IIListProvider_; * для вызовов _OrderBy\(\)\.ThenBy\(\)_ исполнение идёт по else\-ветви, так как массивы \(_Wrapper\[\]_ в нашем случае\) этот интерфейс не реализуют\. В первом случае мы возвращаемся в метод _ToArray_, который был приведён выше\. Из него опять попадаем в конструктор _Buffer_, но исполнение уже пойдёт по else\-ветке, т\.к\. _\_source_ у объекта \#1\.1 – _Wrapper\[\]_\. _EnumerableHelpers\.ToArray_ просто создаёт копию массива: ```cpp internal static T[] ToArray(IEnumerable source, out int length) { if (source is ICollection ic) { int count = ic.Count; if (count != 0) { T[] arr = new T[count]; ic.CopyTo(arr, 0); length = count; return arr; } } else .... .... } ``` Исполнение идёт по then\-ветке\. Остальной код я опустил, т\.к\. в нашем случае он неважен\. Более наглядно разницу видно по стекам вызовов\. Обратите внимание на выделенные "лишние" вызовы: |Call stack для OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|Call stack для OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)| |---|---| ||| |EnumerableHelpers\\\.ToArray|EnumerableHelpers\\\.ToArray| |\*\*Buffer\\\.ctor\*\*|Buffer\\\.ctor| |\*\*OrderedEnumerable\\\.ToArray\*\*|OrderedEnumerable\\\.ToArray| |Buffer\\\.ctor|Enumerable\\\.ToArray| |OrderedEnumerable\\\.ToArray|Main| |Enumerable\\\.ToArray|| |Main|| Отсюда, кстати, и отличие в количестве создаваемых объектов\. Выше мы рассматривали таблицу с ними: |Тип|OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)| |---|---|---| |Int32\\\[\\\]|4|3| |Comparison|2|1| |Wrapper\\\[\\\]|3|2| Наиболее интересными здесь выглядят массивы: _Int32\[\]_ и _Wrapper\[\]_\. Они возникают из\-за того, что поток исполнения лишний раз проходит через метод _OrderedEnumerable\.ToArray_: ```cpp public TElement[] ToArray() { .... TElement[] array = new TElement[count]; int[] map = SortedMap(buffer); .... } ``` Ещё раз отмечу, что размеры массивов _array_ и _map_ зависят от размера сортируемой коллекции: чем она больше, тем больше будет оверхед из\-за лишнего вызова _OrderedEnumerable\.ToArray_\. Та же история с производительностью\. Ещё раз посмотрим на код метода _OrderedEnumerable\.ToArray_: ```cpp public TElement[] ToArray() { Buffer buffer = new Buffer(_source); int count = buffer._count; if (count == 0) { return buffer._items; } TElement[] array = new TElement[count]; int[] map = SortedMap(buffer); for (int i = 0; i != array.Length; i++) { array[i] = buffer._items[map[i]]; } return array; } ``` Нас интересует массив _map_\. Он описывает отношения между позициями элементов в массивах: * индекс – позиция элемента в результирующем массиве; * значение по индексу – позиция в исходном массиве\. Допустим, _map\[5\] \=\= 62_\. Это значит, что в исходном массиве элемент находится на 62 позиции, а в результирующем будет на 5\. Чтобы получить такую "карту отношений", используется метод _SortedMap:_ ```cpp private int[] SortedMap(Buffer buffer) => GetEnumerableSorter().Sort(buffer._items, buffer._count); ``` Метод _GetEnumerableSorter_: ```cpp private EnumerableSorter GetEnumerableSorter() => GetEnumerableSorter(null); ``` Опускаемся в перегрузку метода: ```cpp internal override EnumerableSorter GetEnumerableSorter(EnumerableSorter? next) { .... EnumerableSorter sorter = new EnumerableSorter(_keySelector, comparer, _descending, next); if (_parent != null) { sorter = _parent.GetEnumerableSorter(sorter); } return sorter; } ``` Здесь всплывает ещё одно различие между способами сортировки, которые мы рассматриваем: * _OrderBy\(\)\.OrderBy\(\)_: _\_parent_ у объекта \#1\.2 – _null_\. В результате создаётся один экземпляр _EnumerableSorter_\. * _OrderBy\(\)\.ThenBy\(\)_: _\_parent_ у объекта \#2\.2 указывает на объект \#2\.1\. Это значит, что будут созданы два экземпляра _EnumerableSorter_, связанные друг с другом\. Это происходит за счёт повторного вызова метода – _\_parent\.GetEnumerableSorter\(sorter\)_\. Вызываемый конструктор _EnumerableSorter_: ```cpp internal EnumerableSorter( Func keySelector, IComparer comparer, bool descending, EnumerableSorter? next) { _keySelector = keySelector; _comparer = comparer; _descending = descending; _next = next; } ``` Всё, что делает конструктор – инициализирует поля объекта\. Есть ещё одно поле, которое не используется в конструкторе – _\_keys_\. Оно будет проинициализировано позже, в методе _ComputeKeys_\. Рассмотрим, за что отвечают поля\. Для этого обратимся к одному из рассматриваемых способов сортировки: ```cpp _ = arr.OrderBy(p => p.Primary) .ThenBy(p => p.Secondary) .ToArray(); ``` Для сортировки с помощью _OrderBy_ будет создан экземпляр _EnumerableSorter_\. Его поля: * _\_keySelector_: делегат, отвечающий за маппинг исходного объекта на ключ\. В нашем случае: _Wrapper_ \-\> _int_\. Делегат: _p \=\> p\.Primary_; * _\_comparer_: компаратор, используемый для сравнения ключей\. _Comparer\.Default_, если не задан явно; * _\_descenging_: флаг того, что коллекция сортируется по убыванию; * _\_next_: ссылка на объект _EnumerableSorter_, отвечающий за следующий критерий сортировки\. В примере выше – ссылка на объект, который создан для сортировки по критерию из _ThenBy_\. После того, как экземпляр _EnumerableSorter_ был создан и инициализирован, у него вызывается метод _Sort_: ```cpp private int[] SortedMap(Buffer buffer) => GetEnumerableSorter().Sort(buffer._items, buffer._count); ``` Тело метода _Sort_: ```cpp internal int[] Sort(TElement[] elements, int count) { int[] map = ComputeMap(elements, count); QuickSort(map, 0, count - 1); return map; } ``` Метод _ComputeMap_: ```cpp private int[] ComputeMap(TElement[] elements, int count) { ComputeKeys(elements, count); int[] map = new int[count]; for (int i = 0; i < map.Length; i++) { map[i] = i; } return map; } ``` Посмотрим на метод _ComputeKeys_: ```cpp internal override void ComputeKeys(TElement[] elements, int count) { _keys = new TKey[count]; for (int i = 0; i < count; i++) { _keys[i] = _keySelector(elements[i]); } _next?.ComputeKeys(elements, count); } ``` В этом методе инициализируется массив _\_keys_ экземпляра _EnumerableSorter_\. Вызов _\_next?\.ComputeKeys\(elements, count\)_ позволяет проинициализировать всю цепочку связанных объектов _EnumerableSorter_\. Для чего нужно поле _\_keys_? Этот массив хранит результаты вызова селектора на каждом элементе оригинального массива\. Получается массив ключей, по которым и будет выполняться сортировка\. Пример: ```cpp var arr = new Wrapper[] { new() { Primary = 3, Secondary = 2 }, new() { Primary = 3, Secondary = 1 }, new() { Primary = 1, Secondary = 0 } }; _ = arr.OrderBy(p => p.Primary) .ThenBy(p => p.Secondary) .ToArray(); ``` В этом примере будут созданы два связанных между собой экземпляра _EnumerableSorter_\. |Поле|EnumerableSorter \\\#1|EnumerableSorter \\\#2| |---|---|---| |\\\_keySelector|p \\\=\\\> p\\\.Primary|p \\\=\\\> p\\\.Secondary| |\\\_keys|\\\[3, 3, 1\\\]|\\\[2, 1, 0\\\]| Таким образом, _\_keys_ хранит ключи сортировки для каждого элемента исходного массива\. Возвращаемся в метод _ComputeMap_: ```cpp private int[] ComputeMap(TElement[] elements, int count) { ComputeKeys(elements, count); int[] map = new int[count]; for (int i = 0; i < map.Length; i++) { map[i] = i; } return map; } ``` После вызова метода _ComputeKeys_ создаётся и инициализируется массив _map_\. Это тот самый массив, который описывает отношения между позициями в исходном и результирующем массивах\. В этом методе он пока описывает отношения как i \-\> i, то есть позиции в исходном и результирующем массивах совпадают\. Возвращаемся ещё выше – в метод _Sort_: ```cpp internal int[] Sort(TElement[] elements, int count) { int[] map = ComputeMap(elements, count); QuickSort(map, 0, count - 1); return map; } ``` Нас интересует метод _QuickSort_, в результате которого массив _map_ примет нужный вид\. Именно после этой операции мы получим правильные отношения между позициями элементов в исходном массиве и в результирующем\. Тело метода _QuickSort_: ```cpp protected override void QuickSort(int[] keys, int lo, int hi) => new Span(keys, lo, hi - lo + 1).Sort(CompareAnyKeys); ``` В детали _Span_ и его метода _Sort_ погружаться не будем\. Остановимся на том, что он выполняет сортировку массива с учётом делегата _Comparison_: ```cpp public delegate int Comparison(T x, T y); ``` Классический делегат для сравнения\. Принимает два элемента, сравнивает их и возвращает значение: * < 0, если _x_ меньше _y_; * 0, если _x_ равен _y_; * \> 0, если _x_ больше _y_\. В нашем случае для сравнения используется метод _CompareAnyKeys_: ```cpp internal override int CompareAnyKeys(int index1, int index2) { Debug.Assert(_keys != null); int c = _comparer.Compare(_keys[index1], _keys[index2]); if (c == 0) { if (_next == null) { return index1 - index2; // ensure stability of sort } return _next.CompareAnyKeys(index1, index2); } // .... return (_descending != (c > 0)) ? 1 : -1; } ``` Разберём его по кусочкам: ```cpp int c = _comparer.Compare(_keys[index1], _keys[index2]); if (c == 0) .... return (_descending != (c > 0)) ? 1 : -1; ``` Два элемента сравниваются через компаратор, записанный в _\_comparer_\. Так как мы явно никакого компаратора не задавали, используется _Comparer\.Default_, в нашем случае – _Comparer\.Default_\. Если элементы не равны, условие _c \=\= 0_ не выполняется, и поток исполнения идёт в _return_\. Поле _\_descending_ хранит информацию о том, как проходит сортировка: по убыванию или возрастанию\. Если нужно, за счёт него корректируется возвращаемое методом значение\. А что, если элементы равны? ```cpp if (c == 0) { if (_next == null) { return index1 - index2; // ensure stability of sort } return _next.CompareAnyKeys(index1, index2); } ``` Здесь вступают в игру цепочки экземпляров _EnumerableSorter_, связанных друг с другом\. Если сравниваемые ключи равны, выполняется проверка – а нет ли других критериев сортировки? Если есть \(_\_next \!\= null_\), сравнение уже происходит по ним\. В результате получается, что за один вызов метода _Sort_ учитываются все критерии сортировки\. Что происходит в случае с _OrderBy\(\)\.OrderBy\(\)_? Для этого вернёмся назад, к созданию экземпляра _EnumerableSorter_: ```cpp internal override EnumerableSorter GetEnumerableSorter(EnumerableSorter? next) { .... EnumerableSorter sorter = new EnumerableSorter(_keySelector, comparer, _descending, next); if (_parent != null) { sorter = _parent.GetEnumerableSorter(sorter); } return sorter; } ``` Значение _\_parent_ у объекта, полученного в результате второго вызова метода _OrderBy,_ – _null_\. Значит, создаётся один экземпляр _EnumerableSorter_\. Он ни с чем не связан, значение _\_next_ – _null_\. Получается, все описанные выше действия нужно провести два раза\. Как это сказывается на производительности, мы уже разобрали\. Чтобы напомнить, продублирую одну из таблиц, приведённых выше\. Время сортировки \(в секундах\) 1 000 000 экземпляров типа _Wrapper_: |Количество итераций|1|10|100| |---|---|---|---| |OrderBy\\\(\\\)\\\.OrderBy\\\(\\\)|0\\\.819|6\\\.52|65\\\.15| |OrderBy\\\(\\\)\\\.ThenBy\\\(\\\)|0\\\.571|5\\\.21|42\\\.94| ## Разница в двух словах Методы _OrderBy_ и _ThenBy_ создают экземпляры _OrderedEnumerable_, которые используются для выполнения сортировки\. Помогают выполнять сортировку экземпляры типа _EnumerableSorter_\. Именно они влияют на алгоритм, используют заданные селекторы и компаратор\. Основное различие между вызовами _OrderBy\(\)\.OrderBy\(\)_ и _OrderBy\(\)\.ThenBy\(\)_ – связи между объектами\. **OrderBy\(\)\.OrderBy\(\)**\. Связей нет ни между _OrderedEnumerable_, ни между _EnumerableSorter_\. Из\-за этого создаются "лишние" объекты, проводится две сортировки, а не одна\. Расходуется больше памяти, код работает медленнее\. **OrderBy\(\)\.ThenBy\(\)**\.** **И экземпляры _OrderedEnumerable_, и _EnumerableSorter_ связаны\. Из\-за этого выполняется одна операция сортировки сразу по нескольким критериям\. Лишние объекты не создаются\. Памяти потребляется меньше, код работает быстрее\. ## Выводы Код, в котором _OrderBy\(\)\.ThenBy\(\)_ используется вместо _OrderBy\(\)\.OrderBy\(\)_: * лучше читается; * меньше подвержен ошибкам; * работает быстрее; * расходует меньше памяти\. Как обычно, приглашаю подписаться на [Twitter](https://twitter.com/_SergVasiliev_), если интересны подобные публикации\.