Aytaylik, biz to'plamni bir nechta kalitlar bo'yicha saralashimiz kerak. C# da biz buni OrderBy().OrderBy() yoki OrderBy().ThenBy() yordamida amalga oshirishimiz mumkin. Ammo bu qo'ng'iroqlar o'rtasidagi farq nima? Bu savolga javob berish uchun biz manba kodini o'rganishimiz kerak.

Maqola uchta bobdan iborat:

  • Fon. Maqolani o'qishdan oldin biroz isinishni yaxshi ko'radiganlar uchun. Bu yerda nima uchun men biroz tadqiqot qilishga qaror qilganimni bilib olasiz va OrderBy().OrderBy() va OrderBy().ThenBy() oʻrtasidagi farqni topasiz.
  • Umumiylikni taqqoslash. Bu erda biz ushbu saralash usullarining ishlashi va xotira sarfini solishtiramiz.
  • Xulq-atvordagi farqlar. Bu erda biz .NET manba kodiga kirib, nima uchun bu saralash usullari samaradorligi jihatidan farq qilishini bilib olamiz.

Fon

Hammasi quyidagi maqoladan boshlandi: “Unity, ASP.NET Core va boshqalarda shubhali tartiblashlar””. Maqolada OrderBy().OrderBy() qo'ng'iroqlari tartibi xatolarga olib kelishi mumkin bo'lgan holatlar tasvirlangan. Biroq, ma'lum bo'lishicha, ba'zida ishlab chiquvchilar ataylab OrderBy().ThenBy() emas, balki OrderBy().OrderBy() dan foydalanadilar.

Bir misolni ko'rib chiqing. Aytaylik, bizda Wrapper sinfi va quyidagi turdagi misollar massivi bor:

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 },
};

Biz ushbu massivni saralashni xohlaymiz: avval Birlamchi qiymati, keyin Ikkilamchi.

Agar biz saralashni quyidagicha amalga oshirsak, xato qilamiz:

var sorted = arr.OrderBy(p => p.Primary)
                .OrderBy(p => p.Secondary);
....

Mana natija:

Primary: 2 Secondary: 0
Primary: 0 Secondary: 1
Primary: 2 Secondary: 1
Primary: 0 Secondary: 2
Primary: 1 Secondary: 2
Primary: 0 Secondary: 3

Biz noto'g'ri natijaga erishamiz. To'plamni to'g'ri saralash uchun biz OrderBy().ThenBy() dan foydalanishimiz kerak:

var sorted = arr.OrderBy(p => p.Primary)
                .ThenBy(p => p.Secondary);
....

Mana natija:

Primary: 0 Secondary: 1
Primary: 0 Secondary: 2
Primary: 0 Secondary: 3
Primary: 1 Secondary: 2
Primary: 2 Secondary: 0
Primary: 2 Secondary: 1

Biroq, to'g'ri natijaga erishish uchun OrderBy().OrderBy() dan ham foydalanishimiz mumkin. Biz faqat qo'ng'iroqlarni almashtirishimiz kerak.

Biz shunday qilmasligimiz kerak:

var sorted = arr.OrderBy(p => p.Primary)
                .OrderBy(p => p.Secondary);

Va biz shunday qilishimiz kerak:

var sorted = arr.OrderBy(p => p.Secondary)
                .OrderBy(p => p.Primary);

Ma'lum bo'lishicha, to'g'ri natijaga erishish uchun ikkala variantdan ham foydalanishimiz mumkin:

// #1
var sorted1 = arr.OrderBy(p => p.Secondary)
                 .OrderBy(p => p.Primary);
// #2
var sorted2 = arr.OrderBy(p => p.Primary)
                 .ThenBy(p => p.Secondary);

Menimcha, ikkinchi variant ko'proq o'qilishi mumkin.

OrderBy().OrderBy() ni ko'rganingizda hayron bo'lasiz: "xato" yo'qmi? Shunday qilib, OrderBy().ThenBy() dan foydalanish yaxshiroq: kodni o'qish osonroq va ishlab chiquvchining niyati aniq.

Biroq, bu saralash usullari nafaqat tashqi ko'rinishida farqlanadi: ularning ishlashi va xotira iste'moli ham farq qiladi.

Ishlashni taqqoslash

Quyidagi kod bilan tajriba o'tkazamiz:

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();

Shunday qilib, asosiy fikrlarni umumlashtiramiz:

  • Wrapper - ikkita butun son xususiyatiga ega tuzilma. Biz ularni saralash uchun kalit sifatida ishlatamiz;
  • arr - biz saralashimiz kerak bo'lgan Wrapper misollari massivi. Sinovlar uchun uning yaratilgan usuli muhim emas. Biz saralash va yakuniy massivni olish samaradorligini o'lchaymiz;
  • saralashning ikkita usuli mavjud: birinchisi OrderBy().OrderBy(), ikkinchisi — OrderBy().ThenBy();
  • saralashni boshlash uchun ToArray() chaqiruvi ishlatiladi.

Sinovlarni o'tkazish uchun men yaratilgan test ma'lumotlarining ikkita to'plamini oldim (Wrapper turidagi misollar). Birinchi to'plamda Birlamchi va Ikkilamchi qiymatlarning tarqalishi kattaroq, ikkinchi to'plamda esa kamroq. Men Arr da Wrapper obyektlarini (10 dan 1 000 000 gacha) yozdim va ularni tartibladim.

Test loyihasi .NET 6 da ishlamoqda.

Ishlash

Ishlashni kuzatish uchun "BenchmarkDotNet" dan foydalandim.

Quyida tartiblash va massivni olish uchun qancha vaqt ketganini ko'rishingiz mumkin. Bizni mutlaq qiymatlar qiziqtirmaydi - saralash usullari orasidagi farq muhimroqdir.

№1 maʼlumotlar toʻplami:

№2 maʼlumotlar toʻplami:

Keling, bir vaqtning o'zida bir nechta saralashni amalga oshirsak, vaqt farqini ko'raylik. Buning uchun biz for tsiklidan foydalanamiz:

for (int i = 0; i < iterNum; ++i)
{
  // Perform sorting
}

Wrapper turidagi 1 000 000 ta misolni saralash uchun sarflangan vaqt (soniyalarda):

Xo'sh, 20 soniyadagi farqni ko'rib chiqishga arziydi.

Xotira iste'moli

Xotirada ham shunga o'xshash narsa bor - OrderBy().OrderBy() ko'proq iste'mol qiladi. Bu, ayniqsa, katta hajmdagi ma'lumotlar va bir nechta iteratsiyalarda seziladi.

Bu iteratsiyada yaratilgan ob'ektlar sonidagi farq:

Jadvaldan ko'rinib turibdiki, OrderBy().OrderBy() qo'ng'iroqlari yana ikkita massivni yaratadi. 100 ta saralashdan iborat testni o'tkazganimda, ajratilgan xotiraning 1 Gb farqiga ega bo'ldim.

Shuni ta'kidlash kerakki, tartiblangan to'plam qanchalik katta bo'lsa, "qo'shimcha" massivlar shunchalik katta bo'ladi. Natijada, iste'mol qilinadigan xotira miqdori ham ortadi.

Xulq-atvor farqlari

Va endi "kaput ostida" qarash vaqti keldi. Sizga eslatish uchun - biz saralashning ikkita usulini ko'rib chiqamiz:

// #1
_ = arr.OrderBy(p => p.Secondary)
       .OrderBy(p => p.Primary)
       .ToArray();
// #2
_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

Farqni tushunish uchun biz tahlil qilishimiz kerak:

  • deb ataladigan usullar;
  • metodlar chaqiriladigan ob'ektlarning holati;
  • ijro oqimi.

.NET 6 ning manba kodi GitHub da mavjud.

Yuqori darajadagi usullar

Biz uchta yuqori darajadagi usullarni muhokama qilishimiz kerak: OrderBy, ThenBy va ToArray. Keling, ularning har birini ko'rib chiqaylik.

Buyurtma berish

OrderBy kengaytma usuli boʻlib, u OrderedEnumerable‹TElement, TKey› tipidagi misolni qaytaradi:

public static IOrderedEnumerable<TSource> 
OrderBy<TSource, TKey>(this IEnumerable<TSource> source, 
                       Func<TSource, TKey> keySelector)
  => new OrderedEnumerable<TSource, 
                           TKey>(source, 
                                 keySelector, 
                                 null, 
                                 false, 
                                 null);

ManaOrderedEnumerable‹TElement, TKey› konstruktori:

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

Bu yerda bizni asosiy konstruktor chaqiruvi — base(manba) qiziqtiradi. Asosiy turi OrderedEnumerable‹TElement›. Konstruktor quyidagicha ko'rinadi:

protected OrderedEnumerable(IEnumerable<TElement> source) 
  => _source = source;

Keling, muhokama qilgan narsalarimizni batafsil ko'rib chiqaylik: OrderBy chaqiruvi natijasida OrderedEnumerable‹TElement, TKey› misoli yaratiladi. Uning holati quyidagi maydonlar bilan belgilanadi:

  • _manba;
  • _ota-ona;
  • _keySelector;
  • _qiyoslovchi;
  • _pasaytiruvchi.

Keyin

ThenBy kengaytma usuli hisoblanadi:

public static IOrderedEnumerable<TSource> 
ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, 
                      Func<TSource, TKey> keySelector)
{
  ....
  return source.CreateOrderedEnumerable(keySelector, null, false);
}

Bizning holatda, source o'zgaruvchining turi OrderedEnumerable‹TElement, TKey›. Keling, chaqiriladigan CreateOrderedEnumerable usulining amalga oshirilishini ko'rib chiqaylik:

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

Biz OrderedEnumerable‹TElement, TKey› tipidagi konstruktor chaqirilganini ko'ramiz (bu haqda biz allaqachon OrderBy bo'limida muhokama qilganmiz). Qo'ng'iroqning argumentlari farqlanadi va natijada yaratilgan ob'ektning holati farqlanadi.

Keling, uni yangilab olaylik: ThenBy (masalan, OrderBy), bizning holatimizda OrderedEnumerable‹TElement, TKey› tipidagi misolni qaytaradi.

ToArray

ToArray kengaytma usuli hisoblanadi:

public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source)
{
  ....
  return source is IIListProvider<TSource> arrayProvider
    ? arrayProvider.ToArray()
    : EnumerableHelpers.ToArray(source);
}

Ikkala holatda ham manba OrderedEnumerable‹TElement, TKey› tipidagi misollardir. Bu tip IIlistProvider‹TSource› interfeysini amalga oshiradi. Shuning uchun, bajarish arrayProvider.ToArray() chaqiruvi orqali amalga oshiriladi. Aslida, OrderedEnumerable‹TElement›.ToArray usuli chaqiriladi:

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_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;
}

Va bu erda asosiy farqlar paydo bo'ladi. Biz chuqurroq sho'ng'ishni davom ettirishdan oldin, biz ishlayotgan ob'ektlarning holatini tekshirishimiz kerak.

OrderedEnumerable obyektlarining holatlari

Keling, manba misollariga qaytaylik:

// #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[]

Biz juftlikda joylashgan to'rtta ob'ektni solishtirishimiz kerak:

  • #1.1 va #2.1 ikkala misoldagi birinchi OrderBy chaqiruvlari bilan yaratilgan obyektlar;
  • #1.2 va #2.2 - birinchi misolda ikkinchi OrderBy chaqiruvi va ikkinchi misolda ThenBy chaqiruvi orqali yaratilgan obyektlar.

Natijada biz ob'ektlarning holatini taqqoslash uchun 2 ta jadval olamiz.

Bu yerda birinchi OrderBy qo‘ng‘iroqlari orqali yaratilgan obyektlarning holati:

Bu juftlik bir xil. Faqat selektorlar farq qiladi.

Bu yerda OrderBy (#1.2) va ThenBy (#2.2) ning ikkinchi chaqiruvi orqali yaratilgan obyektlarning holati:

Bu erda selektorlar ham farq qiladi - va bu kutilmoqda. _source va _parent maydonlari farq qilishi qiziq. ThenBy (#2.2) chaqiruvida ob'ektning holati to'g'riroq ko'rinadi: manba to'plamiga havola saqlanadi va "ota-ona" mavjud - oldingi saralash natijasi.

Amalga oshirish oqimi

Endi biz ob'ektlarning holati bajarilish oqimiga qanday ta'sir qilishini aniqlashimiz kerak.

ToArray usuliga qaytaylik:

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_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;
}

Yodda tutingki, turli qo'ng'iroqlar orqali qabul qilingan ob'ektlar turli xil _source maydonlariga ega:

  • OrderBy().OrderBy() buOrderedEnumerable‹TElement, TKey› misoliga ishora qiladi;
  • OrderBy().ThenBy() Wrapper[] misoliga ishora qiladi.

Buffer‹TElement› turini aniqlashni ko'rib chiqamiz:

internal readonly struct Buffer<TElement>
{
  internal readonly TElement[] _items;
  internal readonly int _count;
  internal Buffer(IEnumerable<TElement> source)
  {
    if (source is IIListProvider<TElement> iterator)
    {
      TElement[] array = iterator.ToArray();
      _items = array;
      _count = array.Length;
    }
    else
    {
      _items = EnumerableHelpers.ToArray(source, out _count);
    }
  }
}

Bu erda xatti-harakatlar farqlana boshlaydi:

  • OrderBy().OrderBy() qo'ng'iroqlari uchun ijro keyingi bo'limdan keyin amalga oshiriladi, chunki OrderedEnumerable IIListProvider‹TElement› interfeysini amalga oshiradi;
  • OrderBy().ThenBy() uchun bajarilish else bo'limidan keyin chaqiriladi, chunki massivlar (bizning holimizdabuWrapper[]) bajaradi. ushbu interfeysni amalga oshirmang.

Birinchi holda, biz yuqorida keltirilgan ToArray usuliga qaytmoqdamiz. Keyin yana Bufer konstruktoriga kiramiz, lekin bajarilish else boʻlimidan soʻng amalga oshiriladi, chunki №1.1 obyektning _sourcei Wrapper[]dir. em>.

EnumerableHelpers.ToArray shunchaki massiv nusxasini yaratadi:

internal static T[] ToArray<T>(IEnumerable<T> source, 
                               out int length)
{
  if (source is ICollection<T> ic)
  {
    int count = ic.Count;
    if (count != 0)
    {        
      T[] arr = new T[count];
      ic.CopyTo(arr, 0);
      length = count;
      return arr;
    }
  }
  else
    ....
  ....
}

Amalga oshirish o'sha paytdagi filialdan keyin amalga oshiriladi. Men kodning qolgan qismini o'tkazib yubordim, chunki bizning holatlarimizda bu ahamiyatsiz.

Farqi qo'ng'iroqlar to'plamida aniqroq. Qalin "qo'shimcha" qo'ng'iroqlarga e'tibor bering:

Aytgancha, bu yaratilgan ob'ektlar sonidagi farqni ham tushuntiradi. Mana biz ilgari muhokama qilgan jadval:

Bu yerdagi eng qiziqarli massivlar: Int32[] va Wrapper[]. Ular bajarilish oqimi keraksiz ravishda OrderedEnumerable‹TElement›.ToArray usuli orqali yana bir bor o‘tganligi sababli yuzaga keladi:

public TElement[] ToArray()
{
  ....
  TElement[] array = new TElement[count];
  int[] map = SortedMap(buffer);
  ....
}

Eslatib oʻtamiz, massiv va map massivlarining oʻlchamlari saralangan toʻplam hajmiga bogʻliq: u qanchalik katta boʻlsa, yuqori xarajatlar shunchalik katta boʻladi — chunki keraksiz OrderedEnumerable‹TElement›.ToArray chaqiruvi.

Xuddi shu narsa ishlash bilan bog'liq. OrderedEnumerable‹TElement›.ToArray usuli kodini yana bir bor ko‘rib chiqamiz:

public TElement[] ToArray()
{
  Buffer<TElement> buffer = new Buffer<TElement>(_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;
}

Bizni xarita massivi qiziqtiradi. U massivlardagi elementlarning pozitsiyalari o'rtasidagi munosabatni tavsiflaydi:

  • indeks - natijada olingan massivdagi elementning o'rni;
  • indeks qiymati manba massividagi pozitsiyadir.

Aytaylik, xarita[5] == 62. Bu shuni anglatadiki, element manba massivida 62-o'rinni va olingan massivda 5-o'rinni egallaydi.

“Munosabatlar xaritasi” deb ataladigan narsani olish uchun SortedMap usuli qo'llaniladi:

private int[] SortedMap(Buffer<TElement> buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);

Mana GetEnumerableSorter usuli:

private EnumerableSorter<TElement> GetEnumerableSorter() 
  => GetEnumerableSorter(null);

Keling, usulning haddan tashqari yuklanishini ko'rib chiqaylik:

internal override EnumerableSorter<TElement> 
GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
  ....
  EnumerableSorter<TElement> sorter = 
    new EnumerableSorter<TElement, TKey>(_keySelector, 
                                         comparer, 
                                         _descending, 
                                         next);
  if (_parent != null)
  {
    sorter = _parent.GetEnumerableSorter(sorter);
  }
  return sorter;
}

Bu erda biz muhokama qilayotgan saralash usullari o'rtasidagi yana bir farq paydo bo'ladi:

  • OrderBy().OrderBy(): №1.2 obyektning _parent belgisi null. Natijada EnumerableSorter ning bitta nusxasi yaratiladi.
  • OrderBy().ThenBy(): №2.2 ob'ektning _parent belgisi #2.1 ob'ektga ishora qiladi. Bu bir-biriga bog'liq ikkita EnumerableSorter misol yaratilishini anglatadi. Buning sababi _parent.GetEnumerableSorter(sorter) usuli yana bir marta chaqirilgan.

Mana EnumerableSorter konstruktori:

internal EnumerableSorter(
  Func<TElement, TKey> keySelector, 
  IComparer<TKey> comparer, 
  bool descending, 
  EnumerableSorter<TElement>? next)
{
  _keySelector = keySelector;
  _comparer = comparer;
  _descending = descending;
  _next = next;
}

Konstruktor faqat ob'ekt maydonlarini ishga tushiradi. Konstruktorda ishlatilmaydigan yana bir maydon mavjud — _keys. U keyinroq ComputeKeys usulida ishga tushiriladi.

Keling, maydonlar nima uchun javobgar ekanligini ko'rib chiqaylik. Buning uchun keling, saralash usullaridan birini muhokama qilaylik:

_ = arr.OrderBy(p => p.Primary)
       .ThenBy(p => p.Secondary)
       .ToArray();

OrderBy orqali saralashni amalga oshirish uchun EnumerableSorter namunasi yaratiladi. Unda quyidagi maydonlar mavjud:

  • _keySelector: manba ob'ektini kalitga solishtirish uchun mas'ul delegat. Bizning holatlarimizda bu Wrapper -› int. Delegat: p =› p.Primary;
  • _comparer: kalitlarni solishtirish uchun ishlatiladigan taqqoslash. Comparer‹T›.Default, agar aniq ko'rsatilmagan bo'lsa;
  • _descenging: to'plamning kamayish tartibida tartiblanganligini bildiruvchi belgi;
  • _next: quyidagi tartiblash mezonlari uchun javob beradigan EnumerableSorter obyektiga havola. Yuqoridagi misolda ThenBy mezoni bo'yicha saralash uchun yaratilgan ob'ektga havola mavjud.

EnumerableSorter misoli yaratilgan va ishga tushirilgandan so'ng, buning uchun Sort usuli chaqiriladi:

private int[] SortedMap(Buffer<TElement> buffer) 
  => GetEnumerableSorter().Sort(buffer._items, buffer._count);

Mana Sort usulining asosiy qismi:

internal int[] Sort(TElement[] elements, int count)
{
  int[] map = ComputeMap(elements, count);
  QuickSort(map, 0, count - 1);
  return map;
}

Mana ComputeMap usuli:

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;
}

Keling, ComputeKeys usulini ko'rib chiqaylik:

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);
}

Bu usulda EnumerableSorter misolining _keys massivi ishga tushiriladi. _next?.ComputeKeys(element, count) chaqiruvi tegishli EnumerableSorter obyektlarining butun zanjirini ishga tushirish imkonini beradi.

Nima uchun bizga _keys maydoni kerak? Massiv manba massivining har bir elementida selektorni chaqirish natijalarini saqlaydi. Shunday qilib, biz saralashni amalga oshirish uchun ishlatiladigan bir qator kalitlarni olamiz.

Mana bir misol:

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();

Ushbu misolda ikkita bog'liq EnumerableSorter misol yaratiladi.

Shunday qilib, _keys manba massivining har bir elementi uchun saralash kalitlarini saqlaydi.

ComputeMap usuliga qaytaylik:

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 usulini chaqirgandan so'ng, map massivi yaratiladi va ishga tushiriladi. Bu manbadagi pozitsiyalar va natijaviy massivlar o'rtasidagi munosabatni tavsiflovchi massiv. Bu usulda u hali ham i -› i munosabatini tasvirlaydi. Bu shuni anglatadiki, manba massividagi pozitsiyalar olingan massivdagi pozitsiyalar bilan mos keladi.

Keling, Tartiblash usuliga qaytaylik:

internal int[] Sort(TElement[] elements, int count)
{
  int[] map = ComputeMap(elements, count);
  QuickSort(map, 0, count - 1);
  return map;
}

Bizni QuickSort usuli qiziqtiradi, u map massivini kerakli koʻrinishga keltiradi. Ushbu operatsiyadan so'ng biz manba massividagi va natijada joylashgan elementlarning pozitsiyalari o'rtasidagi to'g'ri munosabatni olamiz.

Mana QuickSort usulining asosiy qismi:

protected override void QuickSort(int[] keys, int lo, int hi) 
  => new Span<int>(keys, lo, hi - lo + 1).Sort(CompareAnyKeys);

Biz Span va uning Tartiblash usuli tafsilotlariga kirmaymiz. Keling, massivni Taqqoslash delegatini hisobga olgan holda tartiblashiga e'tibor qarataylik:

public delegate int Comparison<in T>(T x, T y);

Bu taqqoslash uchun klassik delegat. U ikkita elementni oladi, ularni taqqoslaydi va qiymatni qaytaradi:

  • ‹ 0, agar x y dan kichik bo‘lsa;
  • 0, agar x y ga teng bo‘lsa;
  • › 0, agar x y dan katta bo‘lsa.

Bizning holatda, taqqoslash uchun CompareAnyKeys usuli qo'llaniladi:

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;
}

Shunday qilib, bizda nima borligini ko'rib chiqaylik:

int c = _comparer.Compare(_keys[index1], _keys[index2]);
if (c == 0)
  ....
return (_descending != (c > 0)) ? 1 : -1;

Ikki element _comparer da yozilgan komparator orqali taqqoslanadi. Biz hech qanday taqqoslashni aniq o'rnatmaganimiz sababli, Comparer‹T›.Default ishlatiladi (bizning holatda — Comparer‹Int32›.Default).

Agar elementlar teng bo'lmasa, c == 0 sharti bajarilmaydi va bajarish oqimi qaytishga o'tadi. _pasayish maydoni elementlarning qanday tartiblanganligi haqidagi ma'lumotlarni - kamayish yoki o'sish tartibida saqlaydi. Agar kerak bo'lsa, maydon usul bilan qaytarilgan qiymatni tuzatish uchun ishlatiladi.

Ammo elementlar teng bo'lsa-chi?

if (c == 0)
{
  if (_next == null)
  {
    return index1 - index2; // ensure stability of sort
  }
  return _next.CompareAnyKeys(index1, index2);
}

Bu erda bir-biriga bog'liq EnumerableSorter misollarining zanjirlari keladi. Agar solishtirilgan kalitlar teng bo'lsa, boshqa saralash mezonlari mavjudligini tekshirish uchun tekshiruv o'tkaziladi. Agar mavjud bo'lsa (_keyingi != null), taqqoslash ular orqali amalga oshiriladi.

Ma'lum bo'lishicha, barcha tartiblash mezonlari Sort usulining bir chaqiruvida ko'rib chiqiladi.

Agar biz OrderBy().OrderBy() dan foydalansak nima bo'ladi? Buni bilish uchun EnumerableSorter misolini yaratishga qaytaylik:

internal override EnumerableSorter<TElement> 
GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
  ....
  EnumerableSorter<TElement> sorter = 
    new EnumerableSorter<TElement, TKey>(_keySelector, 
                                         comparer, 
                                         _descending, 
                                         next);
  if (_parent != null)
  {
    sorter = _parent.GetEnumerableSorter(sorter);
  }
  return sorter;
}

Ikkinchi OrderBy chaqiruvi natijasida olingan obyektning _parent qiymati null. Bu bitta EnumerableSorter misol yaratilganligini anglatadi. U biror narsaga aloqador emas, _next qiymati null.

Ma'lum bo'lishicha, biz yuqorida tavsiflangan barcha amallarni ikki marta bajarishimiz kerak. Bu ishlashga qanday ta'sir qilishini biz allaqachon muhokama qildik. Eslatib o'tamiz, yuqorida keltirilgan jadvallardan birini takrorlayman.

Wrapper turidagi 1 000 000 ta misolni saralash uchun sarflangan vaqt (soniyalarda):

Bir so'z bilan aytganda, farq

OrderBy va ThenBy usullari saralashni amalga oshirish uchun ishlatiladigan OrderedEnumerable misollarini yaratadi. EnumerableSorter tipidagi misollar tartiblashni amalga oshirishga yordam beradi. Ular algoritmga ta'sir qiladi, belgilangan selektor va komparatordan foydalanadi.

OrderBy().OrderBy() va OrderBy().ThenBy() qo'ng'iroqlari o'rtasidagi asosiy farq ob'ektlar orasidagi munosabatlardir.

OrderBy().OrderBy(). OrderedEnumerable yoki EnumerableSorter oʻrtasida hech qanday aloqa yoʻq. Natijada, "qo'shimcha" ob'ektlar yaratiladi - bitta saralash o'rniga ikkitasini olamiz. Xotira iste'moli o'sib bormoqda va kod sekinroq ishlaydi.

OrderBy().ThenBy(). OrderedEnumerable va EnumerableSorter misollari oʻzaro bogʻliq. Shu sababli, bir saralash operatsiyasi bir vaqtning o'zida bir nechta mezon bo'yicha amalga oshiriladi. Qo'shimcha ob'ektlar yaratilmaydi. Xotira sarfi kamayadi va kod tezroq ishlaydi.

Xulosa

OrderBy().OrderBy() oʻrniga OrderBy().ThenBy() ishlatadigan kod:

  • o'qish yaxshiroq;
  • xatolarga kamroq moyil;
  • tezroq ishlaydi;
  • xotirani kamroq sarflaydi.

Agar siz bunday nashrlarga qiziqsangiz, meni "Twitter" da kuzatib boring.