¿Qué algoritmo de clasificación utiliza LINQ "OrderBy"?

Evidentemente, "OrderBy" de LINQ se había especificado originalmente como inestable, pero en el momento de Orca se especificó como estable. No toda la documentación se ha actualizado en consecuencia - en cuenta estos enlaces:¿Qué algoritmo de clasificación utiliza LINQ "OrderBy"?

Pero si OrdenarPor de LINQ es ahora "estable", entonces significa que no está utilizando una clasificación rápida (que es inherentemente inestable) a pesar de que cierta documentación (por ejemplo, el libro de Troy) dice que sí. Entonces mi pregunta es: si no es quicksort, ¿cuál es el algoritmo real que está usando el pedido de LINQ?

Fuente

2010-05-07 Brent Arias

stictly, 'OrderBy' de LINQ no se especifica para la estabilidad. 'Enumerable.OrderBy' se especifica como estable, otros proveedores son libres de ofrecer esa promesa, pero es posible que no. Hacerlo puede ser imposible o muy costoso (considere el impacto que tendría en la paralelización en términos de p-linq por ejemplo) o relativamente barato, lo cual es una gran influencia en lo que los proveedores harán. –

Una publicación muy relacionada [aquí] (https://stackoverflow.com/q/148074/465053). – RBT

Para LINQ a objetos, que es una clasificación rápida estable que se utiliza. Para cualquier otro tipo de LINQ, se deja a la implementación subyacente.

Fuente

2010-05-07 22:57:55

Si tengo un objeto al que se hace referencia como 'IEnumerable ', ¿cómo sabe Linq si se trata de Linq-to-Objects o algo así? ¿más? – Dai

IEnumerable es siempre Linq para objetos (frente a IQueryable que es Linq a lo que sea) – John

@Dai IEnumerable es una interfaz, por lo que realmente depende de qué tipo tenga la colección subyacente (no estoy de acuerdo con @John). Por ejemplo, List implementa IEnumerable , y puede tener una lista declarada como IEnumerable . Si realiza un pedido en esta lista, se utiliza el proveedor Linq-to-objects. Por otra parte.DbSet también implementa IEnumerable . Si realiza un pedido en este DbSet, incluso si se declara como IEnumerable, se usará el proveedor de Linq a sql. Si quería usar linq-to-objects en un dbset, podría hacer dbset.AsEnumerable(). OrderBy (lambda) –

Entiendo que OrderBy se traduce a SQL que realiza el ordenamiento en la base de datos. Al menos en el caso de LINQ to SQL

Fuente

2010-05-07 22:32:56

Sí, pero eso solo es cierto para Linq a SQL y otros proveedores de bases de datos Linq. Linq no es solo un ORM ... (Linq a Objetos, Linq a XML ...) –

+1 Por considerar algo diferente de LINQ a Objetos –

Arranque del reflector, abierto a System.Linq.EnumerableSorter revela que Linq2Objects utiliza la ordenación rápida

Fuente

2010-05-07 22:41:06 LorenVS

+1 por buscarlo –

+1 por buscarlo – helios456

+1 por buscándolo. Pero una simple prueba muestra que no hay crecimiento en el consumo de tiempo a medida que aumenta el número de elementos de la lista ordenada inversa de int, como debería ser de acuerdo con en.wikipedia.org/wiki/Quickort Probé los elementos de 1k y 1M en el peor de los casos el consumo aumentó solo aproximadamente 50 veces – EvAlex

Se usa Quicksort, pero la razón por la que es estable se debe a que los índices de cada par de elementos se comparan si todas las claves son iguales.

En otras palabras, puede hacer que cualquier quicksort sea estable al incluir en la función de comparación una comparación de los índices originales de los dos elementos como una alternativa.

Fuente: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34

Fuente

2015-05-07 04:49:20

cool. No sabía eso – AaronHS

¿Qué algoritmo de clasificación utiliza LINQ "OrderBy"?

Respuesta

Cuestiones relacionadas