T-D-K Jul 8 2013 at 19:10

Интересное поведение сортировки в .NET

3 min

5.2K

.NET*

From sandbox

Comments 21

VenomBlood Jul 8 2013 at 19:19

Таким образом, получается что в Microsoft сделали всё правильно, потом неправильно, потом опять правильно.

На самом деле это у вашей коллеги ошибка в тестах (или в коде), т.к. если элементы сортируются и при сортировке считаются одинаковыми, то и при проверке в тестах должен использоваться тот же самый метод сравнения (тот же самый компарер или Equals).

T-D-K Jul 8 2013 at 19:22

Читаем внимательно статью. В одной версии .NET Framework количество сравнений для 100 элементов — 390, в более поздней (т.е. та, что должна быть лучше) — 813, а ещё более поздней — опять 390. В Microsoft что-то сделали правильно, потом неправильно, потом опять правильно.

VenomBlood Jul 8 2013 at 19:26

Я не видел исходников для разных версий, но пока вы выглядите голословно, возможно у версии в 4.0 была асимптотика лучше, возможно она на наиболее распространенных наборах данных (по версии MS) давала в среднем меньшее время. Много еще критериев. Говорить что кто-то что-то сделал неправильно только потому что на вашем наборе в 100 элементов было больше сравнений — это нонсенс.
Кроме того, использовать разные компареры при сортировке и в тестах — это тоже очень странно как минимум.

T-D-K Jul 8 2013 at 19:29

В коде, что представлен в статье воссозданы один к одному условия что были в тесте. Пускай у нас есть тест на очень много одинаковых решений, который в 4.0.30319.17929 будет работать одно время, а в 4.0.30319.18047 в 2.5 раза дольше на одинаковых данных. И, имхо, этот факт надо держать в голове. В пределах одной версии такой разброс, имхо, странно.

VenomBlood Jul 8 2013 at 19:45

В таком случае вам будет интересно знать, что в List.Sort (а точнее в Array.Sort, который используется внутри) в .net используется не совсем QuickSort, там используется как минимум 5 сортировок, включая HeapSort, QuickSort и InsertionSort, котрые выбираются в зависимости от текущей глубины рекурсии, размера сортируемого куска, установленной версии фреймворка и т.д.
Но вот только ИМХО держать в голове такие мелочи (тем более для какой-то версии, различающейся в шестом знаке — не нужно)

T-D-K Jul 8 2013 at 19:46

В статье даже ссылка есть на msdn, в которой английским по белому написано: This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.

Можно ссылку на то, что там используется «HeapSort, QuickSort и InsertionSort»?

VenomBlood Jul 8 2013 at 19:48

В MSDN тонкости не описаны, ссылки нету, используйте рефлектор или исходники.
Ниже вам уже ответили с кодом.

T-D-K Jul 8 2013 at 19:54

В коде я вижу использование для версии 4 — QuickSort. Где HeapSort и InsertionSort?

VenomBlood Jul 8 2013 at 19:54

Перестаньте быть таким упрямым, также перестаньте верить тому, что написано на обертке. Все остальные сортировки внутри.

T-D-K Jul 8 2013 at 20:47

Не нашёл исходников CLR 4 (если они у вас есть — буду очень благодарен за возможность на них глянуть), но в CLR 2 функция TrySZSort просто вызывает QuickSort на C++ для стандартных типов. И выигрыш в скорости появляется из-за того что таким образом имеется возможность сравнивать элементы за одну инструкцию сравнения "<", вместо 10, необходимых для того же Int32.CompareTo().
Я по прежнему хочу видеть доказательства того, что Microsoft использует HeapSort и InsertionSort в .NET 4.0

VenomBlood Jul 8 2013 at 20:50

Используйте рефлектор.

T-D-K Jul 8 2013 at 20:52

https://habrastorage.org/getpro/habr/comment_images/840/0e8/aa1/8400e8aa1cfe0b6c64d6b67664da4dab.png
Вот из рефлектора для .NET 4.0 Вызывается либо QuickSort, либо TrySZSort, который тоже QuickSort, но для нативных типов. Ваши доказательства, какие?

VenomBlood Jul 8 2013 at 21:04

Надо было всего лишь на 1 шаг глубже зайти.

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

Для DeepLimitedQuickSort внутри код примерно такой же.

T-D-K Jul 8 2013 at 21:10

Так, можно пожалуйста скриншот переходов от List.Sort к IntroSort для .NET 4.0?
Для 4.5 microsoft не отрицает использование IntroSoft msdn.microsoft.com/en-us/library/kwx6zbd4.aspx, но 4.0 msdn.microsoft.com/en-us/library/kwx6zbd4(v=vs.100).aspx использует только QuickSort.

VenomBlood Jul 8 2013 at 21:14

Внизу уже ответили:

        if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
          ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer);
        else
          ArraySortHelper<T>.DepthLimitedQuickSort(keys, index, length + index - 1, comparer, 32);

Вот DepthLimitedQuickSort тоже внутри использует как минимум HeapSort, и он, как мы видим — работает когда версия ниже 4.5.

Мне, если честно, наскучило вам уже объяснять. Дальше как-нибудь сами.

VenomBlood Jul 8 2013 at 21:16

Тем более исходный посыл был в том, что у вас в первую очередь бажный код, который упал из за изменения тонкостей .net, которые никто и не гарантировал.
А работает он дольше только на вашем примере из 100 одинаковых элементов, очень синтетически. На основании этого нельзя делать выводы о качестве алгоритма.

И еще — quicksort может быть реализован как стабильная сортировка, так что утверждение «которая, как мы все прекрасно знаем, неустойчива» — неверно.

hotach Jul 8 2013 at 19:46

Самое забавное, что .NET 4.0 и .NET 4.5 используют разные алгоритмы сортировки.
Вот код из глибин Рефектора:
<code

public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
    {
      try
      {
        if (comparer == null)
          comparer = (IComparer<T>) Comparer<T>.Default;

        if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
          ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer);
        else
          ArraySortHelper<T>.DepthLimitedQuickSort(keys, index, length + index - 1, comparer, 32);

      }
      catch (IndexOutOfRangeException ex)
      {
        IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer((object) comparer);
      }
      catch (Exception ex)
      {
        throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), ex);
      }
    }

UFO landed and left these words here

tym32167 Jul 9 2013 at 07:32

1. Тест у вас какой то странный. Сравнение результата неустойчивой сортировки с компаратором, который в данных условиях возвращает всегда 0. Конечно, тест когда то, да должен упасть.
2. Я думаю, что в МСДНе имелось ввиду, что метод внутри, кроме всего прочего, использует быструю сортировку как основной метод сортировки. Это предостережение скорее всего связано с неустойчивостью метода. К тому же, судя по коду, в асмиптотике количество сравнений должно сходиться. Я не спец по алгоритмам, но вот что натестил.
кол-во элементов / 4 фремворк / 4.5 фреймворк / отношение кол-ва сравнений 4 и 4.5 фреймворков
1000000 / 20715517 /16898758 / 0,815753621
10000000 / 248621693 / 208306444 / 0,837845007
100000000 / 2737859069 / 2388941074 / 0,872558088
3. Я тоже писал реализации быстрой сортировки, сортировки слиянием, и много других сортировок, но на рандомных данных мои реализации по времени уступали Array.Sort. Возможно, это связано с данными оптимизациями, которые в Вашем конкретном случае, выдают большое количество сравнений.

PsyHaSTe Jul 9 2013 at 09:08

Вы могли с тем же успехом использовать компаратор
internal class SmthComparer: IComparer {
#region Implementation of IComparer
public int Compare(Smth x, Smth y) {
return 0;
}
#endregion
}
а потом удивляться, что у вас сортировка массивы любых элементов будет разная на различных версиях фреймворка.

извиняюсь, но почему-то теги выделения кода и пр не работают.

T-D-K Jul 9 2013 at 09:29

с нашим компаратором, который именно на этом тесте всегда возвращает 0

тестировалось поведение метода при разных входных данных. Метод вызывает в себе ещё несколько десятков методов (каждый из которых был оттестирован отдельно), вот их совокупное влияние на результат и тестируется. Тестов было очень много. И был среди них тест, в котором все данные одинаковые, т.е. компаратор именно на этом тесте всегда возвращает 0. К чему Ваши утрирования?