Самый быстрый способ сортировки массива в порядке убывания

Question

Почему следующий код

Array.Sort(values);
Array.Reverse(values);

намного быстрее при сортировке массива в порядке убывания по сравнению с

Array.Sort(values, (a,b)=>(-a.CompareTo(b)));

Код был запущен в режиме Release вне отладчика.

Каков наиболее эффективный способ создания сортировки по убыванию для массивов, предпочтительно в один слой?

Answer 1

Это отличный вопрос. Бьюсь об заклад, ваш массив значений является массивом примитивного типа!

Здесь действительно доминирует сортировка, потому что сложность Reverse равна O (n), а сортировка O (n logn).

Дело в том, что при сортировке примитивных типов .NET фактически вызывает встроенную функцию, которая чрезвычайно быстра - намного быстрее, чем при использовании Comparison или Comparator.

Функция называется TrySZSort:

[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecurityCritical]
[MethodImpl(MethodImplOptions.InternalCall)]
private static bool TrySZSort(Array keys, Array items, int left, int right);

а вот как это называется в классе Array:

[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecuritySafeCritical]
public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)
{
  if (array == null)
    throw new ArgumentNullException("array");
  else if (index < 0 || length < 0)
    throw new ArgumentOutOfRangeException(length < 0 ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  else if (array.Length - index < length)
    throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  else if (length > 1 && (comparer != null && comparer != Comparer<T>.Default || !Array.TrySZSort((Array) array, (Array) null, index, index + length - 1)))
    ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
}

Answer 2

Как указывает ссылка

Метод сортировки здесь всегда заканчивается внутренним TrySZSort или QuickSort метод, когда он не выдает исключение. TrySZSort внутренний Метод оптимизирован для одномерных массивов, также известных как «Ноль» массивы или векторы

Поскольку метод TrySZSort, используемый в библиотеках базовых классов, реализованный в нативном коде, он был сильно оптимизирован. Следовательно, этот метод, вероятно, быстрее, чем любое решение, написанное на C # язык

Answer 3

Делегаты.

Вызов делегату намного медленнее, чем вызов по умолчанию IComparable.CompareTo

Обновление:

Если хотитес той же (или близкой) скоростью реализуйте интерфейс IComparer и передайте его в метод сортировки.

http://msdn.microsoft.com/en-us/library/bzw8611x

Answer 4

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

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