学习LINQ：QuickSort

今天下午我开始学习LINQ，到目前为止只是在收集LINQ。 我尝试的第一件事就是实现QSort。

现在 – 忽略我可以使用ORDERBY并且这是一个非常愚蠢的qsort实现的事实 – 我想出的是：

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

唯一真正让我烦恼的是所涉及的所有演员。 我可能会使用任何LINQ技巧吗？ 或者我只是使用LINQ来做它不适合的事情？

Answer 1

只需将参数类型更改为IEnumerable然后使用var构造而不是List作为局部变量。

这将使您的QSLinq方法更好，因为它将接受更多类型的参数，例如int[] ，以及List 。

看到新方法：

  public static IEnumerable QSLinq(IEnumerable _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)); } 

希望这可以帮助。

Answer 2

有趣的问题！ 这并不比OrderBy好，但它确实限制了重复的枚举。

  public static IEnumerable QSort2(IEnumerable 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)); } 

我无意中在开发过程中生成了一个stackoverflow，因为我在Key == 0时QSorted。

---

为了好玩，我测试了这些解决方案。 我提交了基本性能测试罪（在调试模式下测试），但我认为这不会影响我们将看到的大O效应。 这是输入（反向输入是quicksort的最坏情况 ）

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

• 三连续解决方案耗时71000毫秒。
• 我的解决方案需要330毫秒
• OrderBy.ToArray花了15毫秒（计时器的分辨率，因此实际时间可能更短）

Answer 3

这个怎么样？ （如果我理解你不喜欢.ToList调用）

 public static IEnumerable QSLinq(IEnumerable 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))); } 

免责声明基于Jon答案 ： 不要在真正的问题中使用此算法。 这是非常低效的。

Answer 4

所有的演员都涉及？ 我没有看到任何铸造。 我所看到的是调用“ToList”，它们效率极低。 基本上LINQ旨在处理序列，本质上不允许您以快速排序的方式在原位（或在重复空间中）工作。 基本上你在这里进行了大量的数据复制:(

Answer 5

这是使用Aggregate的另一种解决方案。 我称之为： Group and Go Fish 。 我的1000个反向元素测试需要170毫秒。

  public static IEnumerable QSort3(IEnumerable 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 myResult = Enumerable.Empty(); 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 Less; public IEnumerable Same; public IEnumerable More; } 

为什么这比使用OrderBy的解决方案更快？ 我想这对最坏的情况更有抵抗力了。

Answer 6

选择的答案被破坏，因为它在返回的集合中包含QSLinq（_same）而不仅仅是_same，并导致StackOverflowException。 我将使用固定版本作为控件。 如果解决方案可以使用复制，那么速度可以大幅提高。 使用线程而不是并行实际上会降低复制变体的性能。 对非复制变体使用线程会略微提高性能。 与控制的并行和非复制性能差异是疏忽的。

最快复制：

 private static List quickie7(List ites) { if (ites.Count <= 1) return ites; var piv = ites[0]; List les = new List(); List sam = new List(); List mor = new List(); 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; } }); var _les = new List(); var _mor = new List(); Enumerable.Range(0, 2).AsParallel().ForAll(i => { switch (i) { case 0: _les = quickie7(les); break; case 1: _mor = quickie7(mor); break; } }); List allofem = new List(); allofem.AddRange(_les); allofem.AddRange(sam); allofem.AddRange(_mor); return allofem; } 

最快的非复制：

 public static IEnumerable QSLinq3(IEnumerable _items) { if (_items.Count() <= 1) return _items; var _pivot = _items.First(); IEnumerable _less = null; IEnumerable _same = null; IEnumerable _greater = null; ConcurrentBag finishes = new ConcurrentBag(); Enumerable.Range(0, 3).AsParallel().ForAll(i => { var fin = new ManualResetEvent(false); finishes.Add(fin); (new Thread(new ThreadStart(() => { if (i == 0) _less = from _item in _items where _item < _pivot select _item; else if (i == 1) _same = from _item in _items where _item == _pivot select _item; else if (i == 2) _greater = from _item in _items where _item > _pivot select _item; fin.Set(); }))).Start(); }); finishes.ToList().ForEach(k => k.WaitOne()); return QSLinq(_less).Concat(_same).Concat(QSLinq(_greater)); }