Обучение LINQ: QuickSort

Сегодня я сделал решительный шаг и начал изучать 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 для вещей, для которых он не предназначался?

Ответы

Ответ 1

Просто измените тип параметра на 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

Веселый вопрос! Это не превзойдет 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, который мы увидим. Вот вход (обратный вход в худшем случае для быстрой сортировки)

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

Решение triple concat-where заняло 71000 миллисекунд.
Мое решение заняло 330 миллисекунд
OrderBy.ToArray занял 15 миллисекунд (разрешение таймера, поэтому фактическое время, вероятно, меньше)

Ответ 3

Как насчет этого? (Если я хорошо понимаю, вам не нравятся вызовы .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)));
}

Отказ от ответственности на основе Jon answer: НЕ использовать этот алгоритм в реальной проблеме. Это очень неэффективно.

Ответ 4

Все участие в кастинге? Я не вижу кастинга. То, что я вижу, это призывы к "ToList", которые ужасно неэффективны. В основном LINQ предназначен для работы над последовательностями, которые по сути не позволяют вам работать на месте (или в дублированном пространстве) так, как это происходит в quicksort. В основном у вас здесь очень много копий данных: (

Ответ 5

Здесь другое решение, использующее 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

Это только я, или выбранный ответ сломан? Он тратит 99% времени на вычисление входной длины и не должен включать "то же" в последующие вызовы. Он никогда не заканчивается!

Я понимаю, что это неортодоксально, чтобы преобразовать в List < > из IEnumerable < > но он работает, если вы не против копирования. Может быть, есть способ .FirstOrDefault() +.Skip(1).FirstOrDefault(), чтобы вычислить, имеет ли он 0 или 1 в длину, не делая массивную работу для .Length()? Это быстрее, чем кусать пулю и использовать .Length()? возможно, не...

Сравнение скорости между правильным запросом вместо .ForEach неубедительно! Может потребоваться больший ввод?

халтура:

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

длина ввода: 134 217 728

quickie: 00: 00: 08.2481166 quickie2: 00: 00: 05.0694132

quickie: 00: 00: 03.4997753 quickie2: 00: 00: 04.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