Apprendre LINQ: QuickSort

Question

J'ai franchi le pas cet après-midi et j'ai commencé à étudier LINQ, jusqu'à présent, je me balade avec LINQ sur les collections. L'une des premières choses que j'ai essayé a été d'implémenter QSort.

maintenant - en ignorant le fait que je pouvais utiliser juste un ORDERBY et que cela est une implémentation qsort très stupide - ce que je suis venu avec était la suivante:

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 seule chose qui a vraiment bugs moi est tout le casting impliqué. Y a-t-il des astuces LINQ que je pourrais utiliser? Ou est-ce que j'utilise simplement LINQ pour des choses pour lesquelles il n'était pas prévu?

Answer 1

il suffit de changer le type de paramètre à IEnumerable et utiliser la construction var au lieu de votre List<int> pour vos variables locales.

Cela fera . votre méthode QSLinq mieux, car il accepte plusieurs types de paramètres, par exemple int[], ainsi que List<int>

Voir la nouvelle méthode:

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

Espérons que cela aide.

Answer 2

Que pensez-vous de cela? (Si je comprends bien, vous ne l'aimez pas les appels .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))); 
} 

disclaimer sur Jon answer: Ne pas utiliser cet algorithme dans un vrai problème. C'est très inefficace.

Answer 3

Tout le moulage impliqué? Je ne vois pas de casting. Qu'est-ce que je voir est des appels à "ToList" qui sont hideusement inefficaces. Fondamentalement, LINQ est conçu pour fonctionner sur des séquences qui, intrinsèquement, ne vous permettent pas de travailler en place (ou dans un espace dupliqué) de la même manière que le quicksort. Fondamentalement, vous avez un très grand nombre de copies de données passe ici :(

Answer 4

Fun Question! Cela ne surpasse pas OrderBy, mais cela limite les énumérations répétées.

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

I, par inadvertance, a généré un stackoverflow au cours du développement, comme je QSorted lorsque le == clé 0.

---

Juste pour le fun j'ai testé ces solutions. J'ai testé le test de performance cardinal sin (test en mode debug), mais je ne pense pas que cela affecte le grand effet O que nous verrons. Voici l'entrée (entrée inversée est pire des cas pour quicksort)

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

• Le triple-concat où la solution a 71000 millisecondes.
• Ma solution a pris 330 millisecondes
• OrderBy.ToArray a pris 15 millisecondes (la résolution du temporisateur, donc le temps réel est probablement moins)

Answer 5

Voici une autre solution utilisant Aggregate. Je l'appelle: Groupe et Go Fish. Celui-ci prend 170 ms par mon test de 1000 éléments inversés.

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

Pourquoi est-ce plus rapide que ma solution utilisant OrderBy? Je suppose que c'est un peu plus résistant au pire des cas.

Answer 6

Est-ce juste moi, ou la réponse choisie est-elle brisée? Il passe 99% du temps à calculer la longueur d'entrée, et ne devrait pas inclure «identique» dans les appels suivants. Il ne finit jamais!

Je me rends compte qu'il est peu orthodoxe de convertir à la liste <> de IEnumerable <> mais cela fonctionne si cela ne vous dérange pas la copie. Peut-être qu'il y a un moyen de .FirstOrDefault() + .Skip (1) .FirstOrDefault() pour calculer si c'est 0 ou 1 de longueur sans faire le travail massif pour .Length()? Est-ce plus rapide que de mordre la balle et d'utiliser .Length()? peut-être pas ...

La comparaison de vitesse entre une requête correcte au lieu de .ForEach n'est pas concluante! Une plus grande entrée pourrait être nécessaire pour voir?

quickie:

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

longueur d'entrée: 134217728

quickie: 00: 00: 08,2481166 quickie2: 00: 00: 05,0694132

quickie : 00: 00: 03.4997753 quickie2: 00: 00: 0 4.3986761

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

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

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

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

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

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

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

quickie: 00: 00: 03.1562592 quickie2: 00: 00: 05.6059656