Подтвердить что ты не робот

Поведение списка <T>.Sort в .NET 4.5 изменено с .NET 4.0?

У меня есть следующий тест внутри проекта, ориентированного на .NET 4.0:

[TestFixture]
public class Donkey
{
    [Test]
    public void TestListSorting()
    {
        var expected = new[]
                    {
                                MockRepository.GenerateStub<IComparable>(),
                                MockRepository.GenerateStub<IComparable>()
                    };

        var sorted = new List<IComparable>(expected);

        CollectionAssert.AreEqual(expected, sorted);
        sorted.Sort();
        CollectionAssert.AreEqual(expected, sorted);

    }
}

Если я запустил его на компьютере с установленным только .NET 4.0, он терпит неудачу. Если я запустил его на машине с установленным только .NET 4.5, он пройдет.

Я предполагаю, что в .NET 4.5 реализация Sort была изменена для поддержания порядка при сортировке списка объектов, каждый из которых возвращает 0 из CompareTo.

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

Неужели это перерыв? Он не указан на этой странице о совместимости между .NET 4.0 и 4.5.

Есть ли причина для этого? Я что-то упускаю? Есть ли другая страница, которая показывает фактические изменения? Должен ли я просто садиться и перестать паниковать?

4b9b3361

ОТВЕТЫ

Ответ 1

Я уже ответил на аналогичный вопрос. Метод сортировки изменился между 4.5 и 4.0, от быстрой сортировки до интроспективный вид.

Это на самом деле быстрее, но все же это не стабильный вид 1 то есть тот, который имеет одинаковый результат для каждого выполнения, сохраняя порядок равных элементов. Поскольку реализация List.Sort не является стабильной сортировкой, я не думаю, что вы запустили свой unit test более чем достаточно раз, чтобы иметь ошибку в обоих режимах работы?

Я попытался воспроизвести его сам с эквивалентным кодом и компаратором, который возвращает 0. Иногда порядок списка сохраняется, а иногда и нет, как в .NET 4.5, так и в .NET 3.5.

Даже если он изменил тип сортировки от стабильного до неустойчивого, его не было изменением. Тип сортировки и точный результат не являются частью контракта для List.Sort. Все, что гарантирует контракт на метод, заключается в том, что ваши товары будут отсортированы в соответствии с используемым компаратором.

Интересно, однако, потому что [документация MSDN] (http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx) все еще говорит, что использует QuickSort (через `Array.Sort`), но это не в том случае, если вы должны пройти через исходный источник .NET. Дел >

1 По определению использования комбинации QuickSort и HeapSort он должен быть нестабильным. Даже Дэвид Муссер, разработчик алгоритма, утверждает в свою статью:

Introsort, как и quicksort, нестабилен - не сохраняет порядок эквивалентных элементов - поэтому все еще необходимо иметь отдельное требование для стабильной процедуры сортировки.

Ответ 2

В спецификации для List.Sort указано, что используемый сортировка нестабильна и, следовательно, может не сохранять порядок равных элементов; он не указывает конкретного переупорядочения равных элементов, поэтому вы не можете называть это изменение изменением.

Ответ 3

Как сказал @Rawling, посмотрите документацию для Sort():

Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок может не сохраниться.

Итак, вы пытаетесь проверить что-то, что явно задокументировано как undefined. Это не нарушение.

Ответ 4

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

Смотрите: Документация списка <T> . Сортировка

Ответ 5

Из MSDN

Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок не может быть сохранен.

Не похоже, что заказ надежный, поэтому тест недействителен. Кроме того, почему вы все равно тестируете метод Sort? Мне кажется ненужным тестом.

Ответ 6

Вопросы, подобные этому, часто возникают с новыми версиями фреймворка. Есть некоторые для перехода 3.5 → 4.0 здесь и здесь.

Для этого конкретного изменения версий разница возникает уже с массивом или List<> из двух элементов, как показывает ваш вопрос. Другой простой пример:

using System;
using System.Linq;

namespace SortTest
{
  static class Program
  {
    static void Main()
    {
      var arr = new[] { new { Name = "Mary", Age = 17, }, new { Name = "Louise", Age = 17, }, };

      Array.Sort(arr, (x, y) => x.Age.CompareTo(y.Age));

      Console.WriteLine(string.Join(",", arr.Select(x => x.Name)));
    }
  }
}

С .NET 4.0 это печатает Louise,Mary. Элементы меняются местами. Однако с .NET 4.5 он печатает Mary,Louise. Обратите внимание, что обе девочки имеют одинаковый возраст.

List<>.Sort метод экземпляра и статический метод Array.Sort документируются как нестабильные. Они могут оставлять элементы равного "размера" в любом порядке. Поэтому ваш код не должен делать никаких предположений о том, какие элементы эквивалентного порядка входят.

Напротив, метод Linq OrderBy выполняет стабильную сортировку. Так

var ordered = arr.OrderBy(x => x.Age);

требуется не менять Мэри и Луизу, учитывая, что они имеют одинаковые Age.