Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Сортировка в .NET

Anna | 18.06.2014 | нет комментариев
Задача сортировки — это классическая задача, которую должен знать всякий программист. Именно следственно эта статья посвящена данной теме — реализации сортировки на платформе .NET. Я хочу рассказать о том, как устроена сортировка массивов в .NET, побеседовать о ее особенностях, реализации, а также провести малое сопоставление с Java.

Выходит, начнем с того, что первые версии .NET применяют алгорифм стремительной сортировки по умолчанию. Следственно маленький экскурс в стремительную сортировку:

Превосходства:

  1. Один из самых быстродействующих (на практике) из алгорифмов внутренней сортировки всеобщего назначения;
  2. Примитивен в реализации;
  3. Требует лишь O(logn) дополнительной памяти для своей работы (не усовершенствованный рекурсивный алгорифм в худшем случае O(n) памяти);
  4. Отлично гармонирует с механизмами кэширования и виртуальной памяти.

Недочеты:

  1. Крепко деградирует по скорости до O(n2) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого дозволено избежать, выбирая опорный элемент нечаянно, а не фиксированным образом;
  2. Наивная реализация алгорифма может привести к ошибке переполнения стека, так как ей может понадобиться сделать O(n) вложенных рекурсивных вызовов. В усовершенствованных реализациях, в которых рекурсивный вызов происходит только для сортировки меньшей из 2-х частей массива, глубина рекурсии гарантированно не превысит O(logn);
  3. Неустойчив — если требуется стабильность, доводится расширять ключ.

Наивная реализация алгорифма стремительной сортировки может выглядеть приблизительно так:

Наивный QuickSort

public void QuickSort(int left, int right)
 {
  int l = left;
  int r = right;
  int avg = array[(l   r) / 2)];
   do
    {
      while (array[l] < avg)
         l;
      while (array[r] > avg)
       --r;
      if (l <= r)
       {
         if (l < r)
           {
             int temp = array[l];
             array[l] = array[r];
             array[r] = temp;
           }
           l;
         --r;
        }
     }
    while (l <= r);
  if (left < r)
    QuickSort(left, r);
  if (l < right)
    QuickSort(l, right);
}

Вышеописанный алгорифм сортировки имеет следующие недочеты:

  1. От того что опорный элемент выбирается как середина массива, то допустим случай, когда это будет неизменно максимум, в итоге чего массив будет разбиваться на две части длинною n — 1 и 1 и скорость алгорифма деградирует до O(n2);
  2. При вышеописанных условиях глубина рекурсии достигает O(n), в итоге чего при крупных n может случиться переполнение программного стека;
  3. Алгорифм неустойчив, то есть он меняет элементы с идентичными значениями. На примере сортировки чисел это ни как не сказывается, но если мы сортируем массив объектов по какому-либо свойству то это значительно, так как в итоге нескольких вызовов способа Sort будем получать массив элементы которого отличаются порядком.

Переходим к рассмотрению реализации в .NET.

.NET 1.0

Выходит, разглядим, что происходит в .NET 1.0. Забегая, вперед скажу, что ничего классного мы тут не увидим, исключительно для пользовательских важных типов… (из-за отсутствия обобщений в частности)

public static void Sort(Array array)
 {
   Array.Sort(array, (Array) null, array.GetLowerBound(0), array.Length, (IComparer) null);
 }
public static void Sort(Array keys, Array items, int index, int length, IComparer comparer)
 { 
  if (length > 1) {
    if (comparer == Comparer.Default || comparer == null) {
      if(TrySZSort(array, null, index, index   length - 1)) {
        return;
      }
    }
  object[] keys1 = keys as object[];
  object[] items1 = (object[]) null;
  if (keys1 != null)
    items1 = items as object[];
  if (keys1 != null && (items == null || items1 != null))
    new Array.SorterObjectArray(keys1, items1, comparer).QuickSort(index, index   length - 1);
  else
    new Array.SorterGenericArray(keys, items, comparer).QuickSort(index, index   length - 1);
 }

А сейчас собственно классы SorterObjectArray и SorterGenericArray:

SorterObjectArray

private class SorterObjectArray
 {
  private object[] keys;
  private object[] items;
  private IComparer comparer;

  public SorterObjectArray(object[] keys, object[] items, IComparer comparer)
   {
    base..ctor();
    if (comparer == null)
      comparer = (IComparer) Comparer.Default;
    this.keys = keys;
    this.items = items;
    this.comparer = comparer;
   }

  public virtual void QuickSort(int left, int right)
   {
    do
     {
      int left1 = left;
      int right1 = right;
      object obj1 = this.keys[left1   right1 >> 1];
       do
        {
         while (this.comparer.Compare(this.keys[left1], obj1) < 0)
            left1;
         while (this.comparer.Compare(obj1, this.keys[right1]) < 0)
          --right1;
        }       
      if (left1 <= right1)
       {
        if (left1 < right1)
         {
           object obj2 = this.keys[left1];
           this.keys[left1] = this.keys[right1];
           this.keys[right1] = obj2;
           if (this.items != null)
            {
             object obj3 = this.items[left1];
             this.items[left1] = this.items[right1];
             this.items[right1] = obj3;
            }
          }
            left1;
          --right1;
          }
          else
           break;
        }
          while (left1 <= right1);
          if (right1 - left <= right - left1)
          {
            if (left < right1)
              this.QuickSort(left, right1);
            left = left1;
          }
          else
          {
            if (left1 < right)
              this.QuickSort(left1, right);
            right = right1;
          }
        }
        while (left < right);
      }
    } 

SorterGenericArray

private class SorterGenericArray
    {
      private Array keys;
      private Array items;
      private IComparer comparer;

      public SorterGenericArray(Array keys, Array items, IComparer comparer)
      {
        base..ctor();
        if (comparer == null)
          comparer = (IComparer) Comparer.Default;
        this.keys = keys;
        this.items = items;
        this.comparer = comparer;
      }

      public virtual void QuickSort(int left, int right)
      {
        do
        {
          int num1 = left;
          int num2 = right;
          object obj1 = this.keys.GetValue(num1   num2 >> 1);
          do
          {
              while (this.comparer.Compare(this.keys.GetValue(num1), obj1) < 0)
                  num1;
              while (this.comparer.Compare(obj1, this.keys.GetValue(num2)) < 0)
                --num2;
            }

            if (num1 <= num2)
            {
              if (num1 < num2)
              {
                object obj2 = this.keys.GetValue(num1);
                this.keys.SetValue(this.keys.GetValue(num2), num1);
                this.keys.SetValue(obj2, num2);
                if (this.items != null)
                {
                  object obj3 = this.items.GetValue(num1);
                  this.items.SetValue(this.items.GetValue(num2), num1);
                  this.items.SetValue(obj3, num2);
                }
              }
                num1;
              --num2;
            }
            else
              break;
          }
          while (num1 <= num2);
          if (num2 - left <= right - num1)
          {
            if (left < num2)
              this.QuickSort(left, num2);
            left = num1;
          }
          else
          {
            if (num1 < right)
              this.QuickSort(num1, right);
            right = num2;
          }
        }
        while (left < right);
      }
    }

Так что же здесь происходит? Дальнейший код

object[] keys1 = keys as object[];
object[] items1 = (object[]) null;
 if (keys1 != null)
  items1 = items as object[];

это не что иное, как попытка применять ковариацию массивов, которая, как вестимо, работает только для ссылочных типов. Получается, для ссылочных типов применяется класс SorterObjectArray, а для важных типов применяется SorterGenericArray. Но подождите, чем отличаются данные классы? Как вы можете подметить, они отличаются только методом доступа к элементам массива. Для важных типов применяются способы GetValue и SetValue, которые как вы знаете, являются дюже медленными… Получается, что массив целых чисел будет сортироваться дюже длинно (чай целое число является важным типом)? Нет! Массив целых чисел сортируется стремительно, причем дюже стремительно. Все дело в дальнейшем коде

  if (length > 1) {
    if (comparer == Comparer.Default || comparer == null) {
      if(TrySZSort(array, null, index, index   length - 1))
        return; 
    } }

Интерес представляет способ Array.TrySZSort. Данный способ вызывает нативную реализацию сортировки реализованную на С в самой CLR. Причем работает он для простых типов, когда мы используем стандартную логику сопоставления элементов, то есть когда comparer == Comparer.Default || comparer == null.

А вот и нативная реализация:

Нативный TrySZSort

FCIMPL4(INT32, ArrayHelper::TrySZSort, ArrayBase * keys, ArrayBase * items, UINT32 left, UINT32 right)
    //если массив не является одномерным с исходным индексом нуль не сортируем
    if (keys->GetRank() != 1 || keys->GetLowerBoundsPtr()[0] != 0)
        return FALSE;

    // Получаем тип элементов массива
    TypeHandle keysTH = keys->GetElementTypeHandle();
    // Если он не является встроенным примитивным 
    const CorElementType keysElType = keysTH.GetSigCorElementType();
    if (!CorTypeInfo::IsPrimitiveType(keysElType))
        return FALSE;
    if (items != NULL) {
        TypeHandle itemsTH = items->GetElementTypeHandle();
        if (keysTH != itemsTH)
            return FALSE;   // Can't currently handle sorting different types of arrays.
    }

    // Оптимизация для массива из одного элемента
    if (left == right || right == 0xffffffff)
        return TRUE;

    //Далее вызывается специализированная версия сортировки написанная на образцах С  .
    switch(keysElType) {
    case ELEMENT_TYPE_I1: // 1-байтовое знаковое целое число (sbyte)
        ArrayHelpers<I1>::QuickSort((I1*) keys->GetDataPtr(), (I1*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_U1: // 1-байтовое целое число без знака (byte)
    case ELEMENT_TYPE_BOOLEAN: // Логичный тип (bool)
        ArrayHelpers<U1>::QuickSort((U1*) keys->GetDataPtr(), (U1*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_I2: // 2-байтовое знаковое целое число (short)
        ArrayHelpers<I2>::QuickSort((I2*) keys->GetDataPtr(), (I2*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_U2: // 2-байтовое целое число без знака (ushort)
    case ELEMENT_TYPE_CHAR: // Символьный тип (char)
        ArrayHelpers<U2>::QuickSort((U2*) keys->GetDataPtr(), (U2*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_I4: // 4-байтовое знаковое целое число (int)
        ArrayHelpers<I4>::QuickSort((I4*) keys->GetDataPtr(), (I4*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_U4: // 4-байтовое целое число без знака (uint)
        ArrayHelpers<U4>::QuickSort((U4*) keys->GetDataPtr(), (U4*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_R4: // 4-байтовое число с плавающей запятой (float)
        ArrayHelpers<R4>::QuickSort((R4*) keys->GetDataPtr(), (R4*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_I8: // 8-байтовое знаковое целое число (long)
        ArrayHelpers<I8>::QuickSort((I8*) keys->GetDataPtr(), (I8*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_U8: // 8-байтовое целое число без знака (ulong)
        ArrayHelpers<U8>::QuickSort((U8*) keys->GetDataPtr(), (U8*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_R8: // 8-байтовое число с плавающей запятой (double)
        ArrayHelpers<R8>::QuickSort((R8*) keys->GetDataPtr(), (R8*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
        break;

    case ELEMENT_TYPE_I: // Размер целого числа в машинном коде (IntPtr)
    case ELEMENT_TYPE_U: // Размер целого числа без знака в машинном коде (UIntPtr)
        // In V1.0, IntPtr & UIntPtr are not fully supported types.  They do 
        // not implement IComparable, so searching & sorting for them should
        // fail.  In V1.1 or V2.0, this should change.                                   
        return FALSE;

    default:
        return FALSE;
    }
    return TRUE;
}

Нативный QuickSort

// Шаблонный-класс непринужденно занимающийся сортировкой
template <class KIND>
class ArrayHelpers
{
 static void QuickSort(KIND keys[], KIND items[], int left, int right) {
  do {
     int i = left;
     int j = right;
     KIND x = keys[(i   j) >> 1];
      do {
          while (Compare(keys[i], x) < 0) i  ;
          while (Compare(x, keys[j]) < 0) j--;
           if (i > j) break;
           if (i < j) {
            KIND key = keys[i];
            keys[i] = keys[j];
            keys[j] = key;
             if (items != NULL) {
               KIND item = items[i];
               items[i] = items[j];
               items[j] = item;
             }
         }
       i  ;
       j--;
     }
      while (i <= j);
       if (j - left <= right - i) 
        {
          if (left < j) QuickSort(keys, items, left, j);
            left = i;
         }
       else 
        {
         if (i < right) QuickSort(keys, items, i, right);
            right = j;
        }
      } 
      while (left < right);
    }
};

Как видите, нативная сортировка работает только для простых типов. К ним относятся все числовые типы логичный символьный. А для важных пользовательских типов все будет трудиться печально медлительно.

Переходим к рассмотрению реализации именно самого алгорифма сортировки. Будем рассматривать реализацию в классе SorterObjectArray, так как и нативная реализация и реализация для важных типов аналогична.

1. В качестве опорного элемента неизменно берется середина массива:

object obj1 = this.keys[left1   right1 >> 1];

Это не отлично, так как при дрянных входных данных время выполнения алгорифма может стать квадратичным. К тому же середина берется по формуле num1 num2 >> 1, что может привести к переполнению типа int. Такая же оплошность была сделана в алгорифме бинарного поиска и сортировки в Java (ссылка на баг).

Как увидите в следующих версиях .NET данный недочет будет поправлен.

2. Для того, Дабы избежать переполнения стека в данной реализация предусмотрена оптимизация, устраняющая одну ветвь рекурсии: взамен того, Дабы позже распределения массива вызывать рекурсивно процедуру распределения для обоих обнаруженных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения результативности в среднем случае разницы фактически нет: убыточные расходы на добавочный рекурсивный вызов и на организацию сопоставления длин подмассивов и цикла — приблизительно одного порядка. Но глубина рекурсии, ни при каких обстоятельствах не превысит log2n, а в худшем случае вырожденного распределения она вообще будет не больше 2 — каждая обработка пройдёт в цикле первого яруса рекурсии.

.NET 2.0

Новая реализация претерпела незначительные метаморфозы. От того что в .NET 2.0 возникли обобщения, то я буду приводить обобщенный вариант сортировки.

public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)
    {
      // TrySZSort все еще стремительней чем обобщенная реализация. 
      // Повод заключается в том что вызов способа Int32.CompareTo выполняется неторопливей чем "<" либо ">".
      if (length <= 1 || (comparer == null || comparer == Comparer<T>.Default) && 
          Array.TrySZSort((Array) array, (Array) null, index, index   length - 1))
        return;
      ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
    }

А вот собственно способ, тот, что сортирует

QuickSort

private static void SwapIfGreaterWithItems(T[] keys, IComparer<T> comparer, int a, int b)
    {
      if (a == b || comparer.Compare(keys[a], keys[b]) <= 0)
        return;
      T obj = keys[a];
      keys[a] = keys[b];
      keys[b] = obj;
    }

internal static void QuickSort(T[] keys, int left, int right, IComparer<T> comparer)
    {
      do
      {
        int index1 = left;
        int index2 = right;
        int index3 = index1   (index2 - index1 >> 1);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index1, index3);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index1, index2);
        ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index3, index2);
        T obj1 = keys[index3];
        do
        {
          while (comparer.Compare(keys[index1], obj1) < 0)
              index1;
          while (comparer.Compare(obj1, keys[index2]) < 0)
            --index2;
          if (index1 <= index2)
          {
            if (index1 < index2)
            {
              T obj2 = keys[index1];
              keys[index1] = keys[index2];
              keys[index2] = obj2;
            }
              index1;
            --index2;
          }
          else
            break;
        }
        while (index1 <= index2);
        if (index2 - left <= right - index1)
        {
          if (left < index2)
            ArraySortHelper<T>.QuickSort(keys, left, index2, comparer);
          left = index1;
        }
        else
        {
          if (index1 < right)
            ArraySortHelper<T>.QuickSort(keys, index1, right, comparer);
          right = index2;
        }
      }
      while (left < right);
    }

Следует сказать, что оптимизация для встроенных простых типов все еще есть, не смотря на присутствие обобщений (смотри комментарий разработчиков). То есть простые типы по-бывшему применяют нативную сортировку.

В качестве опорного элемента сейчас берется не середина массива, а медиана из первого, серединного и последнего элементов массива.

int index3 = index1   (index2 - index1 >> 1); //середина
ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index1, index3);
ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index1, index2);
ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, index3, index2);
T obj1 = keys[index3];

К тому же сейчас середина вычисляется по формуле index1 (index2 — index1 >> 1), что исключает ошибок связанных с переполнением.

В остальном все по-бывшему без изменений.

Сейчас маленькое отхождение: пускай нам нужно отсортировать по убыванию массив целых чисел. Как вы будете это делать?

Рассматривая все вышесказанное, дальнейший код

Array.Sort(a);
Array.Reverse(a);

на моем компьютере работает приблизительно в 3 раза стремительней, чем

Array.Sort(a, (x, y) => -x.CompareTo(y))

Вас может смутить тот факт, что способ Array.Reverse не обобщен, а значит, со важными типами будет трудиться медлительно (упаковка и способы GetValue, SetValue), но если взглянуть на его реализацию мы вновь увидим оптимизацию для встроенных важных типов, а именно он вызывает нативный способ Array.TrySZReverse, тот, что выглядит так:

Reverse

template <class KIND>
static void Reverse(KIND array[], UINT32 index, UINT32 count) {
        if (count == 0) {
            return;
        }
        UINT32 i = index;
        UINT32 j = index   count - 1;
        while(i < j) {
            KIND temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i  ;
            j--;
        }
    }
};

В всеобщем оптимизации в стандартной библиотеке нас поджидают за всяким углом.

Кстати крайне необычно, что нет обобщенной версии данного способа. Есть способ Reverse как способ растяжение у Enumerable, но его недочет в том, что он это делает не на месте. Получается, что вызов Array.Reverse на массиве пользовательских важных типов неизменно приводит к автобоксингу.

.NET 3.0 — .NET 4.0

Алгорифм не претерпел изменений.

.NET 4.5

Самое увлекательное начинается тут!

Но раньше чем переходить к рассмотрению алгорифма, нужно сказать пару слов о разворачивании .NET 4.5. Для полного понимания обстановки советую прочитать эту статью (к сожалению, на английском). При установке VS 2012, то есть при установки .NET 4.5 она заменяет сборки 4 фреймворка. Реально это значит, что даже когда вы сейчас пишете на .NET 4 вы использует сборки .NET 4.5. Получается увлекательная вещь: до установки 4.5 вы используете один алгорифм сортировки, позже установки вы используете иной алгорифм, причем все происходит без вашего ведома.

Дабы осознать, что собственно происходит, взглянем на код из .NET 4.5:

public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
 {
   if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
     ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer);
   else
     ArraySortHelper<T>.DepthLimitedQuickSort(keys, index, length   index - 1, comparer, 32);
 }

Как вы видите, в способе стоит проверка на то, в каком .NET мы трудимся: если это 4.5, то мы используем IntrospectiveSort если это 4.0 то DepthLimitedQuickSort.

Давайте узнаем чем отличается DepthLimitedQuickSort от сортировки, которая применялась в .NET 4.0 до установки VS 2012. Взглянем на код этого способа:

DepthLimitedQuickSort

internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparer<T> comparer, int depthLimit)
    {
      while (depthLimit != 0)
      {
        int index1 = left;
        int index2 = right;
        int index3 = index1   (index2 - index1 >> 1);
        ArraySortHelper<T>.SwapIfGreater(keys, comparer, index1, index3);
        ArraySortHelper<T>.SwapIfGreater(keys, comparer, index1, index2);
        ArraySortHelper<T>.SwapIfGreater(keys, comparer, index3, index2);
        T obj1 = keys[index3];
        do
        {
          while (comparer.Compare(keys[index1], obj1) < 0)
              index1;
          while (comparer.Compare(obj1, keys[index2]) < 0)
            --index2;
          if (index1 <= index2)
          {
            if (index1 < index2)
            {
              T obj2 = keys[index1];
              keys[index1] = keys[index2];
              keys[index2] = obj2;
            }
              index1;
            --index2;
          }
          else
            break;
        }
        while (index1 <= index2);
        --depthLimit;
        if (index2 - left <= right - index1)
        {
          if (left < index2)
            ArraySortHelper<T>.DepthLimitedQuickSort(keys, left, index2, comparer, depthLimit);
left = index1;
        }
        else
        {
          if (index1 < right)
            ArraySortHelper<T>.DepthLimitedQuickSort(keys, index1, right, comparer, depthLimit);
          right = index2;
        }
        if (left >= right)
          return;
      }
      ArraySortHelper<T>.Heapsort(keys, left, right, comparer);
    }

Как видите это та же стремительная сортировка за исключением одного: алгорифм переключается на пирамидальную сортировку, если мы исчерпаем глубину рекурсии, которая по умолчанию равна 32.

А вот собственно и пирамидальная сортировка:

Heapsort

private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer)
    {
      int n = hi - lo   1;
      for (int i = n / 2; i >= 1; --i)
        ArraySortHelper<T>.DownHeap(keys, i, n, lo, comparer);
      for (int index = n; index > 1; --index)
      {
        ArraySortHelper<T>.Swap(keys, lo, lo   index - 1);
        ArraySortHelper<T>.DownHeap(keys, 1, index - 1, lo, comparer);
      }
    }
private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> comparer)
    {
      T x = keys[lo   i - 1];
      for (; i <= n / 2; { int num; i = num;})
      {
        num = 2 * i;
        if (num < n && comparer.Compare(keys[lo   num - 1], keys[lo   num]) < 0)
            num;
        if (comparer.Compare(x, keys[lo   num - 1]) < 0)
          keys[lo   i - 1] = keys[lo   num - 1];
        else
          break;
      }
      keys[lo   i - 1] = x;
    }

Алгорифм DepthLimitedQuickSort есть ни что иное как IntroSort.

Introsort либо интроспективная сортировка — алгорифм сортировки, предложенный Дэвидом Мюссером в 1997 году. Он использует стремительную сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит определенный предварительно установленный ярус. Данный подход комбинирует в себе превосходства обоих способов с худшим случаем O(n log n) и быстродействием, сравнимым с стремительной сортировкой. Так как оба алгорифма применяют сопоставления, данный алгорифм также принадлежит классу сортировок на основе сопоставлений.

Сейчас посмотрим на то, что происходит в IntrospectiveSort. Реально это та же интроспективная сортировка только больше оптимизированная. Кстати, MSDN по-бывшему говорит, что использует стремительную сортировку.

IntroSort

private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer)
    {
      for (; hi > lo; {int num; hi = num - 1;})
      {
        int num = hi - lo   1;
        if (num <= 16) //если элементов поменьше 16 используем сортировку вставками
        {
          if (num == 1) //если один элемент
            break;
          if (num == 2) //если два элемента
          {
            ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi);
            break;
          }
          else if (num == 3) //если три элемента
          {
            ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi - 1);
            ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi);
            ArraySortHelper<T>.SwapIfGreater(keys, comparer, hi - 1, hi);
            break;
          }
          else
          {
            ArraySortHelper<T>.InsertionSort(keys, lo, hi, comparer); //сортировка вставками
            break;
          }
        }
        else if (depthLimit == 0) //если исчерпали глубину рекурсии
        {
          ArraySortHelper<T>.Heapsort(keys, lo, hi, comparer); //используем пирамидальную сортировку
          break;
        }
        else // напротив используем разбиение стремительной сортировки
        {
          --depthLimit;
          num = ArraySortHelper<T>.PickPivotAndPartition(keys, lo, hi, comparer);
          ArraySortHelper<T>.IntroSort(keys, num   1, hi, depthLimit, comparer);
        }
      }
    }

PickPivotAndPartition

//разбиение массива алгорифмом стремительной сортировки
private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer<T> comparer)
    {
      int index = lo   (hi - lo) / 2;
      ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, index);
      ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi);
      ArraySortHelper<T>.SwapIfGreater(keys, comparer, index, hi);
      T obj = keys[index];
      ArraySortHelper<T>.Swap(keys, index, hi - 1);
      int i = lo;
      int j = hi - 1;
      while (i < j)
      {
        do
          ;
        while (comparer.Compare(keys[  i], obj) < 0);
        do
          ;
        while (comparer.Compare(obj, keys[--j]) < 0);
        if (i < j)
          ArraySortHelper<T>.Swap(keys, i, j);
        else
          break;
      }
      ArraySortHelper<T>.Swap(keys, i, hi - 1);
      return i; 
}

InsertionSort

//сортировка вставками
private static void InsertionSort(T[] keys, int lo, int hi, IComparer<T> comparer)
    {
      for (int index1 = lo; index1 < hi;   index1)
      {
        int index2 = index1;
        T x;
        for (x = keys[index1   1]; index2 >= lo && comparer.Compare(x, keys[index2]) < 0; --index2)
          keys[index2   1] = keys[index2];
        keys[index2   1] = x;
      }
    }

Сейчас сортировка в массивах представляет собой смесь сортировок: сортировку вставками, стремительную сортировку и пирамидальную сортировку.

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

Сопоставление продуктивности

Сопоставление с Java

В плане сортировки Java довольно крепко отличается от .NET. Впрочем, как и в .NET в Java алгорифм так же менялся.

Как вестимо стремительная сортировка является неустойчивой, что является недостатком при сортировке ссылочных типов. От того что в Java «всё как бы объекты», то эта задача усиливается, следственно для сортировки ссылочных типов применяется сортировка слиянием. Данная сортировка является устойчивой и гарантирует O(n logn) времени выполнения в худшем случае, впрочем и требует O(n) дополнительной памяти.

От того что задача стабильности касается только ссылочных типов, для примитивов не имеет значения, меняем ли мы элементы с одним ключом либо нет. Следственно для сортировки примитивов Java использует усовершенствованный алгорифм стремительной сортировки — DualPivotQuicksort. Обыкновенный Quicksort делит массив на два отрезка, предпочтя беспричинный элемент P. Потом сортирует массив так, Дабы все элементы поменьше P попали в 1-й отрезок, а остальные — во 2-й. После этого алгорифм рекурсивно повторяется на первом и на втором отрезках. DualPivotQuicksort делит массив на три отрезка, взамен 2-х. В итоге число операций перемещения элементов массива значительно сокращается.

В Java 7 алгорифм сортировки ссылочных типов поменялся на TimSort.

Timsort — гибридный алгорифм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом. В реальное время Timsort является стандартным алгорифмом сортировки в Python, OpenJDK 7 и реализован в Android JDK 1.5. Основная идея алгорифма в том, что в настоящем мире сортируемые массивы данных Зачастую содержат в себе упорядоченные подмассивы. На таких данных Timsort значительно стремительней многих алгорифмов сортировки.

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

Что вы думаете об этом отличии в реализации сортировки в 2-х фреймворках? Так ли нам необходима стабильность в реальных задачах, на которую необходимо потратить память, и время как это сделано в Java? Либо же дозволено обойтись без стабильности, вместо на скорость и экономию памяти как это сделано в .NET? Лично я отдаю свой выбор .NET, потому что думаю, что стабильность необходима лишь в определенных задачах, которые появляются, не так Зачастую, по крайней мере, у меня за 4 года не появилась ни раз, ну, а если и возникнет то решение таких задач дозволено положить на плечи программиста, думаю, его не затруднит реализовать алгорифм устойчивой сортировки.

Завершение

Быть может такие подробности о .NET необходимы не всякому программисту, но думаю, их познание не повредит никому. К тому же, ухищренные интервьюеры могут задать вопросы о сортировке на собеседовании. В всеобщем, спасибо за прочтение. Верю, статья оказалась пригодной.

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB