Learning LINQ: QuickSort

Question

Bu öğleden sonra dalmayı attım ve LINQ üzerinde çalışmaya başladım, şimdiye kadar koleksiyonlarda LINQ ile uğraştım. Denediğim ilk şeylerden biri QSort'u uygulamaktı.

Şimdi - bunu sadece orderBy kullanıp ki gerçeğini görmezden bu çok saçma qsort uygulama olduğunu - Ben bu ile geldi:

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

tek şey gerçekten beni ilgilendiren tüm dökümler. Kullanabileceğim herhangi bir LINQ numarası var mı? Yoksa sadece amaçlanmadığı şeyler için LINQ kullanıyor muyum?

Answer 1

Sadece IEnumerable için parametrenin türünü değiştirmek ve yerel değişkenler için senin List<int> yerine var yapısını kullanmaktadır.

Bu yapacaktır .

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

: o List<int> yanı sıra örneğin int[] için, parametrelerin daha türlerini kabul eder çünkü QSLinq yöntem daha iyi

yeni bir yöntem görün

Bu yardımcı olur umarım.

Answer 2

Bu nasıl? Jon answer dayalı

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

Yasal Uyarı (ben de anlıyorum Eğer .ToList aramaları sevmiyorum): gerçek sorun bu algoritmayı KULLANMAYIN. Bu çok verimsiz.

Answer 3

Tüm döküm işlemleri içeriyor mu? Ben bir döküm görmüyorum. 'un numarasına baktığımda, görmezden verimsiz olan "ToList" e yapılan çağrıları görebilirsiniz. Temel olarak LINQ, hızlı bir şekilde oruç tutmaya meyilli şekilde yerinde (veya bir kopya boşlukta) çalışmanıza izin vermeyen diziler üzerinde çalışmak üzere tasarlanmıştır. veri kopyalama çok şey burada Temelde Elinizdeki oluyor :(

Answer 4

Eğlenceli Soru! Bu, OrderBy'den daha iyi performans göstermez, ancak tekrarlanan numaralandırmaların bazılarını sınırlandırır. Anahtar == 0.

---

Sadece eğlence için ben bu çözümleri test edildiğinde ben QSorted olarak

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

farkında olmadan, geliştirme sırasında bir stackoverflow üretti. Kardinal performans testi günahını (hata ayıklama modunda test etme) yaptım, ancak bunun göreceğimiz büyük O etkiyi etkilemediğini düşünüyorum. İşte girişi (ters giriş quicksort için kötü durum edilir)

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

• olan üçlü concat çözüm 71000 milisaniye sürdü.
• Çözümüm, 330 milisaniye olarak
• OrderBy ürününü aldı.ToArray 15 milisaniyeyi aldı (zamanlayıcı çözünürlüğü, bu nedenle gerçek zaman muhtemelen daha azdır).

Answer 5

Aggregate kullanarak bir başka çözüm daha. Ben buna Group and Go Fish deyin. Bu 1000 ters elemanlar testi ile 170 ms alır.

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

Bu, neden SiparişBy'yi kullanarak benim çözümümden daha hızlıdır? Sanırım en kötü durum için biraz daha dayanıklı.

Answer 6

Sadece ben miyim, yoksa seçilen cevap kırık mı? Giriş uzunluğunu hesaplayan zamanın% 99'unu harcar ve sonraki aramalarda 'aynı' içermemelidir. Asla bitmez!

List <> IEnumerable <> 'ye dönüştürmek için alışılmışın dışında olduğunun farkındayım, ancak kopyalama işlemini önemsemiyorsanız işe yarayacaktır. Belki .FirstOrDefault() + .Skip (1) .FirstOrDefault() için bir yol var .Length() için muazzam bir iş yapmadan 0 veya 1 uzunluğunda olup olmadığını hesaplamak için? Bu mermi ısırma ve .Length() kullanarak daha hızlı mı? Belki de ...

.ForEach yerine uygun bir sorgu arasındaki hız karşılaştırması sonuçsuz! Görmek için daha büyük bir giriş gerekli olabilir?

şipşak:

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

giriş uzunluğu: 134.217.728

şipşak: 00: 00: 08,2481166 quickie2: 00: 00: 05,0694132

şipşak : 00: 00: 03.4997753 quickie2: 00: 00: 0 4.3986761

şipşak: 00: 00: 06,9764478 quickie2: 00: 00: 04,8243235

şipşak: 00: 00: 08,2962985 quickie2: 00: 00: 04,0703919

şipşak: 00: 00: 04,2339839 quickie2: 00: 00: 08,5462999

şipşak: 00: 00: 07,0605611 quickie2: 00: 00: 05,0110331

şipşak: 00: 00: 03.1742108 quickie2: 00: 00: 06,9817196

şipşak: 00: 00: 06,9593572 quickie2: 00: 00: 05,8098719

şipşak: 00: 00: 03,4487516 quickie2: 00: 00: 04,1156969

Daha fazla bilgi için: 00: 00: 03.1562592 quickie2: 00: 00: 05.6059656