ejemplos - linq to sql c#

Learning LINQ: QuickSort

Question

Esta tarde me lancé a la zaga y comencé a estudiar LINQ, hasta ahora solo me metía con LINQ en colecciones. Una de las primeras cosas que intenté fue implementar QSort.

Ahora, ignorando el hecho de que solo podía usar un ORDERBY y que esta es una implementación de qsort muy tonta, lo que se me ocurrió fue esto:

public class lqsort
{
public static List<int> QSLinq(List<int> _items)
{
if (_items.Count <= 1)
return _items;
int _pivot = _items[0];
List<int> _less = (from _item in _items where _item < _pivot select _item).ToList();
List<int> _same = (from _item in _items where _item == _pivot select _item).ToList();
List<int> _greater = (from _item in _items where _item > _pivot select _item).ToList();
return (QSLinq(_less).Concat(_same.Concat(QSLinq(_greater)))).ToList();
}
}

Lo único que realmente me molesta es todo el casting involucrado. ¿Hay algún truco de LINQ que pueda usar? ¿O acabo de usar LINQ para cosas para las que no estaba destinado?

Answer 1

Todo el casting involucrado? No veo ningún casting. Lo que sí veo son llamadas a "ToList" que son terriblemente ineficientes. Básicamente LINQ está diseñado para trabajar sobre secuencias, que intrínsecamente no le permiten trabajar en su lugar (o en un espacio duplicado) en la forma en que tiende la oferta rápida. Básicamente tienes una gran cantidad de copia de datos pasando aquí :(

Answer 2

¡Pregunta divertida! Esto no supera a OrderBy, pero limita algunas enumeraciones repetidas.

 public static IEnumerable<int> QSort2(IEnumerable<int> source)
{
if (!source.Any())
return source;
int first = source.First();
return source
.GroupBy(i => i.CompareTo(first))
.OrderBy(g => g.Key)
.SelectMany(g => g.Key == 0 ? g : QSort2(g));
}

Inadvertidamente generé un durante el desarrollo, ya que QSorted cuando Key == 0.

Solo por diversión, probé estas soluciones. Cometí la prueba de rendimiento cardinal sin (probar en modo de depuración), pero no creo que eso afecte al gran efecto O que veremos. Aquí está la entrada (la entrada invertida es el peor caso para el quicksort)

IEnumerable<int> source = Enumerable.Range(0, 1000).Reverse().ToList();

• La solución triple concat-where tomó 71000 milisegundos.
• Mi solución tomó 330 milisegundos
• OrderBy.ToArray tomó 15 milisegundos (la resolución del temporizador, por lo que el tiempo real es probablemente menor)

Answer 3

Simplemente cambie el tipo de parámetro a IEnumerable y use el constructo var lugar de su List<int> para sus variables locales.

Esto mejorará su método QSLinq porque aceptará más tipos de parámetros, por ejemplo int[] , así como List<int> .

Vea el nuevo método:

 public static IEnumerable<int> QSLinq(IEnumerable<int> _items)
{
if (_items.Count() <= 1)
return _items;
var _pivot = _items.First();
var _less = from _item in _items where _item < _pivot select _item;
var _same = from _item in _items where _item == _pivot select _item;
var _greater = from _item in _items where _item > _pivot select _item;
return QSLinq(_less).Concat(QSLinq(_same)).Concat(QSLinq(_greater));
}

Espero que esto ayude.

Answer 4

Aquí hay otra solución usando Agregado. Lo llamo: Group and Go Fish . Este toma 170 ms por mi prueba de 1000 elementos invertidos.

 public static IEnumerable<int> QSort3(IEnumerable<int> source)
{
if (!source.Any())
return source;
int first = source.First();
QSort3Helper myHelper =
source.GroupBy(i => i.CompareTo(first))
.Aggregate(new QSort3Helper(), (a, g) =>
{
if (g.Key == 0)
a.Same = g;
else if (g.Key == -1)
a.Less = g;
else if (g.Key == 1)
a.More = g;
return a;
});
IEnumerable<int> myResult = Enumerable.Empty<int>();
if (myHelper.Less != null)
myResult = myResult.Concat(QSort3(myHelper.Less));
if (myHelper.Same != null)
myResult = myResult.Concat(myHelper.Same);
if (myHelper.More != null)
myResult = myResult.Concat(QSort3(myHelper.More));
return myResult;
}
public class QSort3Helper
{
public IEnumerable<int> Less;
public IEnumerable<int> Same;
public IEnumerable<int> More;
}

¿Por qué es esto más rápido que mi solución usando OrderBy? Supongo que es un poco más resistente al peor de los casos.

Answer 5

¿Qué tal esto? (Si entiendo bien, no te gustan las llamadas .ToList)

public static IEnumerable<int> QSLinq(IEnumerable<int> items)
{
if (items.Count() <= 1)
return items;
int pivot = items.First();
return QSLinq(items.Where(i => i < pivot))
.Concat(items.Where(i => i == pivot))
.Concat(QSLinq(items.Where(i => i > pivot)));
}

Descargo de responsabilidad basado en la respuesta de Jon : NO use este algoritmo en un problema real. Es muy ineficiente