Пользователь
0,0
рейтинг
29 июля 2013 в 00:00

Разработка → Сортировка в .NET

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

Итак, начнем с того, что первые версии .NET используют алгоритм быстрой сортировки по умолчанию. Поэтому небольшой экскурс в быструю сортировку:

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

Недостатки:
  1. Сильно деградирует по скорости до O(n2) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, выбирая опорный элемент случайно, а не фиксированным образом;
  2. Наивная реализация алгоритма может привести к ошибке переполнения стека, так как ей может потребоваться сделать O(n) вложенных рекурсивных вызовов. В улучшенных реализациях, в которых рекурсивный вызов происходит только для сортировки меньшей из двух частей массива, глубина рекурсии гарантированно не превысит 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)
        {
            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)
        {
            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 попали в первый отрезок, а остальные — во второй. Затем алгоритм рекурсивно повторяется на первом и на втором отрезках. DualPivotQuicksort делит массив на три отрезка, вместо двух. В результате количество операций перемещения элементов массива существенно сокращается.

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

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

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

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

Заключение


Быть может такие подробности о .NET нужны не каждому программисту, но думаю, их знание не повредит никому. К тому же, изощренные интервьюеры могут задать вопросы о сортировке на собеседовании. В общем, спасибо за прочтение. Надеюсь, статья оказалась полезной.
Гуев Тимур @timyrik20
карма
111,7
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (37)

  • 0
    Пожалуйста, уточните — в некоторых местах у вас «наивный алгоритм», а в других «нативный алгоритм»
    Это опечатка или американизмы?
    • +4
      Я полагаю это разные термины. Нативный имеется ввиду «родной», такое часто применяется когда идет речь о прямом использовании функционала нижележащей среды. Т.е. реализованная непосредственно в CLR ([MethodImpl(MethodImplOptions.InternalCall)]) функциональность для BLC может называться нативной.
      Наивная реализация — это фактически синоним слова «топорная реализация», т.е. без учета каких-либо тонкостей, которые ценой небольших модификаций базового описания алгоритма дадут какой-либо выигрыш.
  • 0
    А я на стороне Java и тимсорта. Понятно, что ими движет: вот было у нас 100 файликов в папке, отсортированных по имени, юзер бросил еще два и снова попросил посортировать. 100 из 102 файлов уже расположены верно относительно друг друга, надо лишь поставить 2 новых на правильные места, тимсорт это сделает лучше дотнетовской сортировки. Таких примеров много: новые фотки на фотоаппарате, новые поступления данных в базу, консолидация данных из нескольких идентичных источников. Дотнет же предполагает, что мир больше хаотичен и случаен, мне в это меньше верится.
    • +1
      Немного странные примеры, так как в этом случае алгоритм бинарной вставки все равно быстрее TimSort.
      Из моего опыта часто встречаются кластеры схожих данных, к примеру вы достаете данные из N страниц памяти или читаете из N мест, как правило данные в каждой странице близки по значения (одинаково удаленны от центра сортировки), а следовательно получается много схожих подпоследовательностей, так скажем подгрупп со схожими свойствами относительно других элементов. И тут TimSort быстрее? (затрудняюсь ответить)
      • 0
        Было бы интересно посмотреть на бенчмарки при реализации алгоритмов на одном языке. А то «на глазок» сравнивать — как-то не научно.
  • +6
    Было бы интересно узнать ещё и про реализацию сортировки в LINQ. Написать цепочку из OrderBy и ThenBy приятнее, чем реализовать метод для сравнения вручную: меньше кода, лучше читается, меньше шансов ошибиться в логике и т.п. Соответственно, интересно, насколько LINQ проигрывает по скорости сортировке массива.
    • +1
      В OrderBy используется устойчивый алгоритм в отличие от Array.Sort. А вообще если речь идет о LINQ to EF\NH\SQL то там вообще запрос в бд :-)
    • 0
      Посмотрите рефлектором EnumerableSorter<T>. Там чистый QuickSort, вроде бы ни во что не переходящий.
  • –3
    В примерах кода SorterGenericArray и SorterObjectArray закрывающих фигурных скобок больше, чем открывающих. И бросается в глаза do без while.

    Стану читать дальше, если сделаете везде одинаковые отступы. В одном и том же куске кода встречается 1, 2 и 4 пробела. Крыша едет, глаза слезятся.
    • 0
      Стало читабельнее, спасибо. Ещё бы так же исправить раскардаш отступов в «Нативный QuickSort».
  • –2
    Сильно деградирует по скорости до O(n2) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, выбирая опорный элемент случайно, а не фиксированным образом;

    Не обязательно случайно, можно сделать быструю сортировку детерминировано за O(n log n).

    А с TimSort сравнения не делали? Насколько я знаю, в питоне он используется достаточно давно, и менять не собираются.
  • +1
    Не обязательно случайно, можно сделать быструю сортировку детерминировано за O(n log n).

    Не можете сказать идею такой сортировки или дать ссылку? Или это делается через какой-нибудь поиск медианы за O(N)? Тогда константа должна быть просто ужасной.
  • 0
    На графике секунды? .NET 4.5 Миллионный массив чего-нибудь за 10 минут сортируется?
    • 0
      Наверное, это миллисекунды.
    • 0
      Это миллисекунды.
    • –1
      Да запросто — главное в критерий сравнения добавить аналог Thread.sleep().
  • +5
    К слову, замечу, что в C++, в реализации std::sort от microsoft используется тот же подход – использование insertion sort, heapsort, quick sort в зависимости от условий.

    std::sort в VS2010
    template<class _RanIt,
    	class _Diff,
    	class _Pr> inline
    	void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
    	{	// order [_First, _Last), using _Pred
    	_Diff _Count;
    	for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
    		{	// divide and conquer by quicksort
    		_STD pair<_RanIt, _RanIt> _Mid =
    			_Unguarded_partition(_First, _Last, _Pred);
    		_Ideal /= 2, _Ideal += _Ideal / 2;	// allow 1.5 log2(N) divisions
    
    		if (_Mid.first - _First < _Last - _Mid.second)
    			{	// loop on second half
    			_Sort(_First, _Mid.first, _Ideal, _Pred);
    			_First = _Mid.second;
    			}
    		else
    			{	// loop on first half
    			_Sort(_Mid.second, _Last, _Ideal, _Pred);
    			_Last = _Mid.first;
    			}
    		}
    
    	if (_ISORT_MAX < _Count)
    		{	// heap sort if too many divisions
    		_STD make_heap(_First, _Last, _Pred);
    		_STD sort_heap(_First, _Last, _Pred);
    		}
    	else if (1 < _Count)
    		_Insertion_sort(_First, _Last, _Pred);	// small
    	}
    


    Интересно, что при малых выборках и использовании Insertion sort, вы получите устойчивую сортировку, а на больших данных – уже нет.

    К слову, проводил недавно эксперименты с разными сортировками, писал руками и замерял время сортировки на разных объемах данных (ссылка на github). Что интересно, до 1 000 000 значений алгоритмы с STL работают быстрее, при бОльших объемах – начинают проигрывать.

    Полученные результаты на Google Docs
    Еще раз ссылка на Github – исходники, графики, описания

    Полученные результаты картинкой

    Попсовый график сравнения лучших алгоритмов на больших объемах данных
    image


    • 0
      Странно, что у вас MergeSort работает так медленно.
      Я погонял эти тесты, подставив недефолтную функцию сравнения ( bool cmp(int x,int y){ return (x^13)<(y^13); } ) — получились такие результаты:
      64 bit, Intel i7
      5000000:
      MergeSort = 492.8ms
      MergeSortInPlace = 670.9ms
      MergeSortBottomUp = 536.2ms
      QuickSort = 615.5ms
      std::sort = 666.4ms
      std::stable_sort = 628.6ms
      
      10000000:
      MergeSort = 1025.2ms
      MergeSortInPlace = 1425.2ms
      MergeSortBottomUp = 1117.6ms
      QuickSort = 1269.2ms
      std::sort = 1397.8ms
      std::stable_sort = 1323.8ms
      
      50000000:
      MergeSort = 5318ms
      MergeSortInPlace = 8034.67ms
      MergeSortBottomUp = 6154ms
      QuickSort = 7048ms
      std::sort = 7671.33ms
      std::stable_sort = 7189.33ms
      
      100000000:
      MergeSort = 11444ms
      MergeSortInPlace = 17040ms
      MergeSortBottomUp = 13166ms
      QuickSort = 14647ms
      std::sort = 15944ms
      std::stable_sort = 14953ms
      
      200000000:
      MergeSort = 23447ms
      MergeSortInPlace = 35907ms
      MergeSortBottomUp = 27430ms
      QuickSort = 30298ms
      std::sort = 33544ms
      std::stable_sort = 31094ms
      
      



      MergeSortInPlace — экспериментальная сортировка с дополнительной памятью O(1) и гарантированным временем O(N*log(N)). Работает чуть хуже, чем мой прошлый опыт (проигрывает quicksort'у 10-20%), зато код намного более простой…
      • 0
        Скорее всего из-за того, что память медленная, там на гитхабе указаны характеристики машины — RAM 8Gb, 1033. На домашней машине, где память быстрее, MergeSort работает тоже довольно таки значительно быстрее, но не скажу на сколько точно. Может на процентов 5-10.
        • +1
          Я немного доработал код, теперь он (по моим тестам) на уровне остальных MergeSort (хотя память по-прежнему O(1)).

          www.dropbox.com/s/cag6ao6xsyccnr8/MergeInPlaceSort.h
          • 0
            Оу, спасибо, я посмотрю.
  • 0
    Всегда расстраивался что в .NET FW не зашили несколько реализаций сортировок которые можно было бы выбирать при сортировке. Зачастую разработчик представляет природу своих данных и смог бы подобрать оптимальный алгоритм.
    • 0
      Никто не запрещает реализовать (или скопипастить) подходящий алгоритм сортировки, если вам так критичны 10% производительности в операции, которая занимает 5% времени работы программы. :)
      • +1
        Да что вы говорите? А я всё ждал такого бесценного совета.

        Суть не в том что я не могу это сделать. Суть в том что в каждом проекте видишь эти ваши «копипасты», и тошнить начинает от этих через зад прилепленных реализаций.
        Моя идея была в том что MS написав такой гигансткий фреймворк где уже есть некоторые алгоритмы сортировки, могли бы управление алгоритмом вытащить наружу для тех кто понимает какой алгоритм в текущей задаче ему даст эти 10%.

        А что касается 5% времени работы программы — если вы занимаетесь формочками и CRUD'ом — это ваши личные проблемы. Я уверен что очень многие разработчики тут пишут приложения в которых есть обработка больших объемов данных и их пользователям пригодились бы те самые 10% производителности.
        • 0
          Мне ещё не доводилось видеть на коленке реализованных алгоритмов сортировки. :) Вот сколько EnumerableExtensions и иже с ними повидал, чего только там не встречал, а сортировок — не было.

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

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

          Э… чо? Сделать настройку, которая меняет реализацию Array.Sort во всём приложении что ли?

          Я уверен что очень многие разработчики тут пишут приложения в которых есть обработка больших объемов данных и их пользователям пригодились бы те самые 10% производителности.

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

          Вообще, пихать всё в фреймворк — не самая хорошая идея. И так эта дура 50 метров весит, а после установки — полтора-два гига (посмотрите на досуге размер C:\Windows\Assembly и C:\Windows\Microsoft.NET).
        • 0
          Не совсем понятно, что вы предлагаете разработчику в ситуации, когда ему полезны «10% производительности» и у него есть алгоритм той самой сортировки, который даёт эти самые 10%, но библиотечным не является? Писать код, от которого вас будет тошнить, потому как используется реализация, написанная на коленке? Или наступить на горло собственной песне, взять библиотечную реализацию и сказать пользователям «покупайте железо помощнее»?
          • +1
            Писать код, от которого вас будет тошнить, потому как используется реализация, написанная на коленке?

            Пишем extension method. Вместо array.Sort() имеем array.SuperSort(). Да даже если банальный статический метод в двух местах будет вызываться вместо Sort — что же, от этого тошнить должно?
            • 0
              Пишем extension method. Вместо array.Sort() имеем array.SuperSort().

              Пожалуй, я так и сделаю. Спасибо за идею! Жаль только, что универсальная сортировка у меня узким местом пока не является :(
      • 0
        5% времени работы программы могут быть критичными, если они составляют время между моментом, когда пользователь нажал кнопку и моментом, когда он увидел результат — чтобы еще что-то сделать, запустить долгий процесс и пойти пить кофе. 15 секунд он потерпит, а если это будет 20 секунд — отвлечется на какой-нибудь фейсбук, а потом будет говорить, что программа строила preview полчаса…
    • 0
      Может быть, дело в том, что когда эффективности Quicksort не хватает, то оптимальный алгоритм будет слишком специфичным? И шансов, что он окажется среди ещё десятка универсальных алгоритмов, которые могли бы предложить разработчики, будет не так уж много? Ведь кроме предполагаемого порядка элементов оптимальный алгоритм будет учитывать ещё и их вероятное распределение, кластеризацию, особенности функции сравнения. Например «сначала пустим поразрядную сортировку по этому полю, потом quicksort по этому сравнению на полученные фрагменты, а потом сольём их по этой быстро вычисляемой функции сравнения». Какие шансы, что такое удастся найти хоть в какой-нибудь библиотеке?
      А меня в .NET больше расстраивает, что у них нет функции сортировки фрагмента массива по заданной функции сравнения. Для всего массива есть, а для фрагмента нет. Приходится в этом месте (если фрагмент небольшой) писать какой-нибудь пузырёк. Открыли бы они хотя бы создание компаратора по лямбда-выражению — не пришлось бы тратить время. Но нет, 10 строчек, а класс internal…
      • 0
        Есть ведь метод который сортирует элементы в диапазоне элементов массива, используя заданный компоратор
        public static void Sort(T[] array, int index, int length, IComparer comparer).
        Или вы имели ввиду метод принимающий Comparison?
        • 0
          Да, Comparison (обычно это лямбда-выражение, использующее текущее окружение). Сами они делают из него компаратор. Но нам этого класса не дают.
          • 0
            Да знаю. Сам пользуюсь часто перегрузкой с делегатом) Согласен, что было бы удобнее если бы такой метод был бы, так как с компоратором не очень удобно.
            • +1
              Может быть, просто украсть у них этот класс и пользоваться:

                      internal sealed class FunctorComparer<T> : IComparer<T> { 
                          Comparison<T> comparison;
               
                          public FunctorComparer(Comparison<T> comparison) {
                              this.comparison = comparison;
                          }
               
                          public int Compare(T x, T y) {
                              return comparison(x, y); 
                          } 
                      }
              

              • 0
                Можно!!!)))) Но лучше бы они добавили реализацию, при которой нам не понадобиться красть)))))
      • 0
        Можно написать свою реализацию генерации компаратора, иногда довольно удобно. Лично я для себя остановился на таком:

        [TestMethod]
        public void TestComparerFull4()
        {
            Tuple<string, int> a = new Tuple<string, int>("1", 2), b = new Tuple<string, int>("2", 4);
            Tuple<string, int> x = new Tuple<string, int>("2", 2), y = new Tuple<string, int>("2", 4);
            var comparer = CustomComparer<Tuple<string, int>>.New(t => t.Item1).Add(t => t.Item2).CreateDelegate();
            var comparerNeg = CustomComparer<Tuple<string, int>>.NewNeg(t => t.Item1).Add(t => -t.Item2).CreateDelegate();
        
            Assert.AreEqual(-1, comparer(a, b));
            Assert.AreEqual(1, comparer(b, a));
        
            Assert.AreEqual(1, comparerNeg(x, y));
            Assert.AreEqual(-1, comparerNeg(y, x));
        }
        

        Сами делегаты строятся на экспрешенах. В итоге получается достаточно удобно.
        Сама реализация на гитхабе: тыц и тыц. Планирую потом перенести в другое отдельное решение, может кому пригодится. Но вообще довольно юзабельным должно быть. Ну и конечно каждый под себя может переделать как ему больше нравится.
  • 0
    Кстати, лучше все же смотреть на referencesource, ибо декомпилятор не показывает комментарии и директивы условной компиляции, которые зачастую весьма интересны (и магическое число 32 тоже объясняется):

    internal void Sort(int left, int length)
    {
    #if FEATURE_CORECLR
    // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade 
    // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka 
    // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
    
        IntrospectiveSort(left, length);
    #else
        if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
        {
            IntrospectiveSort(left, length);
        }
        else
        {
            DepthLimitedQuickSort(left, length + left - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
        }
    #endif
    }

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.