Aprendiendo LINQ: QuickSort

Question

Me lancé a la zaga esta tarde y comencé a estudiar LINQ, hasta el momento solo estaba jugando con LINQ en colecciones. Una de las primeras cosas que intenté fue implementar QSort.

Ahora - ignorando el hecho de que yo podía sólo tiene que utilizar un orderBy y que se trata de una aplicación muy tonta qsort - lo que 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(); 
    } 
} 

La única cosa 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

sólo cambia el tipo del parámetro a IEnumerable y utilizar el constructo var en lugar de su List<int> para sus variables locales.

Esto hará . el método de QSLinq mejor porque va a aceptar más tipos de parámetros, por ejemplo int[], así como List<int>

Ver 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 2

¿Qué tal esto? (Si entiendo bien no le gusta 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))); 
} 

exención de responsabilidad basado en Jon answer: no utiliza este algoritmo en un verdadero problema. Es muy ineficiente

Answer 3

Todo el casting involucrado? No veo ningún casting. Lo que do ver son las llamadas a "ToList" que son terriblemente ineficaces. 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, usted tiene una gran cantidad de datos de copia pasando aquí :(

Answer 4

Diversión ¡Pregunta! 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)); 
    } 

que genera inadvertidamente un stackoverflow durante el desarrollo, ya que cuando el QSorted == Clave 0.

---

Sólo por diversión He probado 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 (entrada invertido se peor de los casos para la clasificación rápida)

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

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

Answer 5

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 6

¿Soy yo o la respuesta elegida está rota? Pasa el 99% del tiempo calculando la longitud de entrada, y no debería incluir 'lo mismo' en llamadas posteriores. ¡Nunca termina!

Me doy cuenta de que es poco ortodoxo convertir a la lista <> de IEnumerable <> pero funciona si no te molesta la copia. Tal vez haya una forma de .FirstOrDefault() + .Skip (1) .FirstOrDefault() para calcular si tiene 0 o 1 de longitud sin hacer el trabajo masivo para .Length()? ¿Es esto más rápido que morder la bala y usar .Length()? tal vez no ...

La comparación de velocidad entre una consulta adecuada en lugar de .ForEach no es concluyente. Una entrada más grande puede ser necesaria para ver?

polvo rápido:

case 0: ites.ForEach(k => { if (k < piv) les.Add(k); }); break; 
case 1: ites.ForEach(k => { if (k == piv) sam.Add(k); }); break; 
case 2: ites.ForEach(k => { if (k > piv) mor.Add(k); }); break; 

quickie2:

private static List<int> quickie2(List<int> ites) 
{ 
    if (ites.Count <= 1) 
     return ites; 
    var piv = ites[0]; 
    List<int> les = new List<int>(); 
    List<int> sam = new List<int>(); 
    List<int> mor = new List<int>(); 
    Enumerable.Range(0, 3).AsParallel().ForAll(i => 
    { 
     switch (i) 
     { 
      case 0: les = (from _item in ites where _item < piv select _item).ToList(); break; 
      case 1: sam = (from _item in ites where _item == piv select _item).ToList(); break; 
      case 2: mor = (from _item in ites where _item > piv select _item).ToList(); break; 
     } 
    }); 
    List<int> allofem = new List<int>(); 
    var _les = new List<int>(); 
    var _mor = new List<int>(); 
    ConcurrentBag<ManualResetEvent> finishes = new ConcurrentBag<ManualResetEvent>(); 
    for (int i = 0; i < 2; i++) 
    { 
     var fin = new ManualResetEvent(false); 
     finishes.Add(fin); 
     (new Thread(new ThreadStart(() => 
     { 
      if (i == 0) 
       _les = quickie(les); 
      else if (i == 1) 
       _mor = quickie(mor); 
      fin.Set(); 
     }))).Start(); 
    } 
    finishes.ToList().ForEach(k => k.WaitOne()); 
    allofem.AddRange(_les); 
    allofem.AddRange(sam); 
    allofem.AddRange(_mor); 
    return allofem; 
} 

longitud de entrada: 134217728

polvo rápido: 00: 00: 08,2481166 quickie2: 00: 00: 05,0694132

polvo rápido : 00: 00: 03.4997753 quickie2: 00: 00: 0 4.3986761

rapidito: 00: 00: 06,9764478 quickie2: 00: 00: 04,8243235

rapidito: 00: 00: 08,2962985 quickie2: 00: 00: 04,0703919

rapidito: 00: 00: 04,2339839 quickie2: 00: 00: 08,5462999

rapidito: 00: 00: 07,0605611 quickie2: 00: 00: 05,0110331

rapidito: 00: 00: 03,1742108 quickie2: 00: 00: 06,9817196

rapidito: 00: 00: 06,9593572 quickie2: 00: 00: 05,8098719

rapidito: 00: 00: 03,4487516 quickie2: 00: 00: 04,1156969

Quickie: 00: 00: 03.1562592 quickie2: 00: 00: 05.6059656