c# - Comportamiento de la lista<T>. ¿El orden en.NET 4.5 cambió de.NET 4.0?

.net-4.0 .net-4.5

Question

Tengo la siguiente prueba dentro de un proyecto dirigido a .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);

    }
}

Si lo ejecuto en una máquina con solo .NET 4.0 instalado, falla. Si lo ejecuto en una máquina con solo .NET 4.5 instalado, se pasa.

Supongo que en .NET 4.5, la implementación de la Sort se ha cambiado para mantener el orden al ordenar una lista de objetos que cada uno devuelve 0 de CompareTo .

Ahora, deja a un lado la locura obvia de esta prueba. Sé que es una locura confiar en este tipo de comportamiento.

Seguramente este es un cambio de ruptura? No aparece en esta página sobre la compatibilidad entre .NET 4.0 y 4.5.

¿Hay alguna razón para esto? ¿Me estoy perdiendo de algo? ¿Hay otra página que muestra los cambios de ruptura reales? ¿Debo sentarme y dejar de entrar en pánico?

Answer 1

Como dijo @Rawling, eche un vistazo a la documentación de Sort() :

Esta implementación realiza una ordenación inestable; es decir, si dos elementos son iguales, su orden podría no conservarse.

Entonces, estás tratando de probar algo que está documentado explícitamente como indefinido. Eso no es un cambio de ruptura.

Answer 2

Desde MSDN

Esta implementación realiza una ordenación inestable; es decir, si dos elementos son iguales, su orden podría no conservarse

No parece que la orden sea confiable, por lo que la prueba es nula. Además, ¿por qué estás probando el método de Sort todos modos? Me parece una prueba innecesaria.

Answer 3

He respondido una pregunta similar a esto antes. El método de clasificación ha cambiado entre 4.5 y 4.0, de una clasificación rápida a una clasificación introspectiva .

En realidad, es más rápido, pero aún no es una clasificación estable ¹ , es decir, una que tiene el mismo resultado para cada ejecución al preservar el orden de los elementos iguales. Dado que ninguna implementación de List.Sort es una clasificación estable, ¿no creo que haya realizado su prueba de unidad el tiempo suficiente para que se List.Sort un error en ambos tiempos de ejecución?

Intenté reproducirlo con un código equivalente y un comparador que devuelve 0. A veces, el orden de la lista se conserva y otras no, tanto en .NET 4.5 como en .NET 3.5.

Incluso si cambió el tipo de clasificación de estable a inestable, no es un cambio importante . El tipo de clasificación utilizado y la salida exacta no forman parte del contrato para List.Sort . Todo lo que garantiza el contrato de método es que sus artículos estarán ordenados de acuerdo con el comparador utilizado.

Sin embargo, es interesante porque la [documentación de MSDN] (http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx) todavía dice que usa QuickSort (a través de `Array.Sort`), pero esto es no es el caso si tuviera que pasar por la fuente de referencia de .NET.

_{¹ Por la definición de usar una mezcla de QuickSort y HeapSort , debe ser una clasificación inestable. Incluso David Musser, el diseñador del algoritmo afirma en su artículo :}

_{Introsort, al igual que quicksort, no es estable, no conserva el orden de los elementos equivalentes, por lo que todavía es necesario tener un requisito separado para una rutina de clasificación estable.}

Answer 4

No veo ningún cambio. Como otros ya escribieron, ambas versiones realizan una clasificación inestable. Lo que significa que no puedes confiar en el orden de los elementos que se comparan como iguales. Su orden puede o no cambiar durante la clasificación. Ciertamente no es un cambio de ruptura.

Ver: Documentación de Lista <T> .Ordenar

Answer 5

Preguntas como esta a menudo vienen con nuevas versiones de framework. Hay algunos para la transición 3.5 → 4.0 here y here .

Para este cambio particular de versiones, la diferencia ya surge con una matriz o List<> de dos elementos, como muestra su pregunta. Otro ejemplo simple es:

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

Con .NET 4.0 esto imprime a Louise,Mary . Los elementos son intercambiados. Sin embargo, con .NET 4.5 imprime Mary,Louise . Tenga en cuenta que las dos niñas tienen la misma edad.

List<>.Sort método de instancia de Array.Sort y el método estático Array.Sort se documentan como ordenaciones no estables. Son libres de dejar elementos de igual "tamaño" en el orden que deseen. Por lo tanto, su código no debe hacer suposiciones sobre en qué orden entran los elementos equivalentes.

En contraste, el método OrderBy de Linq realiza una ordenación estable. Asi que

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

Se requiere que no se intercambien a Mary y Louise, dado que tienen la misma Age .

Answer 6

La especificación para List.Sort dice que la clasificación utilizada es inestable y, por lo tanto, puede no preservar el orden de elementos iguales; no especifica un reordenamiento particular de elementos iguales, por lo que realmente no puede llamar a este cambio un cambio de ruptura.