How to become an author
Search
Write a publication
Pull to refresh

Comments 21

Таким образом, получается что в Microsoft сделали всё правильно, потом неправильно, потом опять правильно.
На самом деле это у вашей коллеги ошибка в тестах (или в коде), т.к. если элементы сортируются и при сортировке считаются одинаковыми, то и при проверке в тестах должен использоваться тот же самый метод сравнения (тот же самый компарер или Equals).
Total votes 6: ↑4 and ↓2+2
Читаем внимательно статью. В одной версии .NET Framework количество сравнений для 100 элементов — 390, в более поздней (т.е. та, что должна быть лучше) — 813, а ещё более поздней — опять 390. В Microsoft что-то сделали правильно, потом неправильно, потом опять правильно.
Total votes 8: ↑4 and ↓40
Я не видел исходников для разных версий, но пока вы выглядите голословно, возможно у версии в 4.0 была асимптотика лучше, возможно она на наиболее распространенных наборах данных (по версии MS) давала в среднем меньшее время. Много еще критериев. Говорить что кто-то что-то сделал неправильно только потому что на вашем наборе в 100 элементов было больше сравнений — это нонсенс.
Кроме того, использовать разные компареры при сортировке и в тестах — это тоже очень странно как минимум.
Total votes 10: ↑7 and ↓3+4
В коде, что представлен в статье воссозданы один к одному условия что были в тесте. Пускай у нас есть тест на очень много одинаковых решений, который в 4.0.30319.17929 будет работать одно время, а в 4.0.30319.18047 в 2.5 раза дольше на одинаковых данных. И, имхо, этот факт надо держать в голове. В пределах одной версии такой разброс, имхо, странно.
Total votes 3: ↑1 and ↓2-1
В таком случае вам будет интересно знать, что в List.Sort (а точнее в Array.Sort, который используется внутри) в .net используется не совсем QuickSort, там используется как минимум 5 сортировок, включая HeapSort, QuickSort и InsertionSort, котрые выбираются в зависимости от текущей глубины рекурсии, размера сортируемого куска, установленной версии фреймворка и т.д.
Но вот только ИМХО держать в голове такие мелочи (тем более для какой-то версии, различающейся в шестом знаке — не нужно)
Total votes 4: ↑4 and ↓0+4
В статье даже ссылка есть на 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»?
Total votes 5: ↑2 and ↓3-1
В MSDN тонкости не описаны, ссылки нету, используйте рефлектор или исходники.
Ниже вам уже ответили с кодом.
Total votes 4: ↑4 and ↓0+4
В коде я вижу использование для версии 4 — QuickSort. Где HeapSort и InsertionSort?
Total votes 9: ↑3 and ↓6-3
Перестаньте быть таким упрямым, также перестаньте верить тому, что написано на обертке. Все остальные сортировки внутри.
Total votes 5: ↑5 and ↓0+5
Не нашёл исходников CLR 4 (если они у вас есть — буду очень благодарен за возможность на них глянуть), но в CLR 2 функция TrySZSort просто вызывает QuickSort на C++ для стандартных типов. И выигрыш в скорости появляется из-за того что таким образом имеется возможность сравнивать элементы за одну инструкцию сравнения "<", вместо 10, необходимых для того же Int32.CompareTo().
Я по прежнему хочу видеть доказательства того, что Microsoft использует HeapSort и InsertionSort в .NET 4.0
Total votes 4: ↑2 and ↓20
Надо было всего лишь на 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 внутри код примерно такой же.
Total votes 3: ↑3 and ↓0+3
Внизу уже ответили: 
        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.

Мне, если честно, наскучило вам уже объяснять. Дальше как-нибудь сами.
Total votes 2: ↑2 and ↓0+2
Тем более исходный посыл был в том, что у вас в первую очередь бажный код, который упал из за изменения тонкостей .net, которые никто и не гарантировал.
А работает он дольше только на вашем примере из 100 одинаковых элементов, очень синтетически. На основании этого нельзя делать выводы о качестве алгоритма.

И еще — quicksort может быть реализован как стабильная сортировка, так что утверждение «которая, как мы все прекрасно знаем, неустойчива» — неверно.
Total votes 4: ↑4 and ↓0+4
Самое забавное, что .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);
      }
    }
Total votes 7: ↑7 and ↓0+7
UFO just landed and posted this here
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. Возможно, это связано с данными оптимизациями, которые в Вашем конкретном случае, выдают большое количество сравнений.

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

извиняюсь, но почему-то теги выделения кода и пр не работают.
Total votes 2: ↑2 and ↓0+2
с нашим компаратором, который именно на этом тесте всегда возвращает 0

тестировалось поведение метода при разных входных данных. Метод вызывает в себе ещё несколько десятков методов (каждый из которых был оттестирован отдельно), вот их совокупное влияние на результат и тестируется. Тестов было очень много. И был среди них тест, в котором все данные одинаковые, т.е. компаратор именно на этом тесте всегда возвращает 0. К чему Ваши утрирования?
Total votes 1: ↑0 and ↓1-1
Sign up to leave a comment.

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr