Сегодня днем я сделал решительный шаг и начал изучать LINQ, пока просто возился с LINQ над коллекциями. Одним из первых, что я попробовал, было реализовать QSort.
Теперь - игнорируя тот факт, что я мог просто использовать ORDERBY и что это очень глупая реализация qsort - я придумал следующее:
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();
}
}
Единственное, что меня действительно беспокоит, - это кастинг. Могу ли я использовать какие-нибудь уловки LINQ? Или я просто использую LINQ для того, для чего он не предназначен?
Просто измените тип параметра на IEnumerable и используйте конструкцию var вместо List<int> для ваших локальных переменных.
Это улучшит ваш QSLinq метод, поскольку он будет принимать больше типов параметров, например int[], а также List<int>.
Смотрите новый метод:
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));
}
Надеюсь это поможет.
Ответ 2 · рейтинг 9 · Amy B
Интересный вопрос! Это не превосходит OrderBy, но несколько ограничивает повторные перечисления.
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));
}
Я случайно сгенерировал stackoverflow во время разработки, так как QSorted, когда Key == 0.
Ради интереса я протестировал эти решения. Я совершил кардинальный грех тестирования производительности (тестирование в режиме отладки), но я не думаю, что это повлияет на большой эффект O, который мы увидим. Вот ввод (обратный ввод - худший случай для быстрой сортировки)
Решение тройного concat-where заняло 71000 миллисекунд.
Мое решение заняло 330 миллисекунд
OrderBy.ToArray занял 15 миллисекунд (разрешение таймера, поэтому фактическое время, вероятно, меньше)
Ответ 3 · рейтинг 3 · Panos
Как насчет этого? (Если я хорошо понимаю, вам не нравятся вызовы .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)));
}
Отказ от ответственности на основании ответа Джона: НЕ используйте это алгоритм в реальной задаче. Это очень неэффективно.
Ответ 4 · рейтинг 2 · Jon Skeet
Вовлечен весь кастинг? Я не вижу кастинга. То, что я делаю, - это вызовы ToList, которые ужасно неэффективны. В основном LINQ предназначен для работы с последовательностями, которые по сути не позволяют вам работать на месте (или в дублированном пространстве) так, как это обычно делается при быстрой сортировке. По сути, здесь происходит очень много копирования данных :(
Ответ 5 · рейтинг 2 · Amy B
Вот еще одно решение с использованием Aggregate. Я называю это: Group and Go Fish. Это занимает 170 мс в моем тесте на 1000 обратных элементов.
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;
}
Почему это быстрее, чем мое решение, использующее OrderBy? Я думаю, это немного более устойчиво к худшему случаю.
Ответ 6 · fartwhif
Выбранный ответ неверен, потому что он включает QSLinq (_same) вместо просто _same в возвращаемой коллекции и приводит к исключению StackOverflowException. Я буду использовать фиксированную версию в качестве контроля. Если решение может использовать копирование, то скорость можно резко увеличить. Использование потоков вместо параллельного на самом деле немного снижает производительность при копировании вариантов. Использование потоков для вариантов без копирования немного увеличивает производительность. Отличие параллельной и некопирующей производительности от контроля незначительное.
самое быстрое копирование:
private static List<int> quickie7(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;
}
});
var _les = new List<int>();
var _mor = new List<int>();
Enumerable.Range(0, 2).AsParallel().ForAll(i =>
{
switch (i)
{
case 0: _les = quickie7(les); break;
case 1: _mor = quickie7(mor); break;
}
});
List<int> allofem = new List<int>();
allofem.AddRange(_les);
allofem.AddRange(sam);
allofem.AddRange(_mor);
return allofem;
}
самый быстрый без копирования:
public static IEnumerable<int> QSLinq3(IEnumerable<int> _items)
{
if (_items.Count() <= 1)
return _items;
var _pivot = _items.First();
IEnumerable<int> _less = null;
IEnumerable<int> _same = null;
IEnumerable<int> _greater = null;
ConcurrentBag<ManualResetEvent> finishes = new ConcurrentBag<ManualResetEvent>();
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));
}
