Re: Быстрая сортировка массива на Nemerle - Nemerle

Здравствуйте, <Аноним>, Вы писали:

А>Господа, подскажите, как лучше всего написать алгоритм быстрой сортировки массива (quicksort) на Nemerle.

Не ясно зачем это делать. Ведь есть Array.Sort() и обертка над ним в NArray:

/** Attention! It's inplace sort. */
public SortInplace[T] (this source : array [T], comparison : System.Comparison[T]) : array [T]
{
    System.Array.Sort(source, comparison);
    source
}

Если интерес чисто теоритический, то отвечу — лучше писть обобщенный варинат в императивном стиле. Красота в таких вещах совсем не к чему. Оптимальный вариант — это классический Хоровский алгоритм дополненный использованием сортировки вставками при малых размерах массива. Но можно и вообще классику использовать.

Вот адаптировал свои C#-пные примеры:

using System;
using System.Console;
using Nemerle.Utility;

module Utils
{
    public Sort[T](this ary : array[T]) : void
      where T : IComparable[T]
    {
      Sort(ary, 0, ary.Length - 1, (x, y) => x.CompareTo(y) > 0);
    }
    
    public Sort[T](this ary : array[T], left : int, right : int) : void    
      where T : IComparable[T]
    {
      Sort(ary, left, right, (x, y) => x.CompareTo(y) > 0);
    }
  
    public Sort[T](this ary : array[T], isGreat : T * T -> bool) : void
    {
        Sort(ary, 0, ary.Length - 1, isGreat);
    }

    public Sort[T](
        this ary : array[T],
            left : int,
           right : int,
         isGreat : T * T -> bool
    )
      : void    
    {
      mutable i = left;
        mutable j = right;
        def center = ary[(left + right) / 2];

        while (i <= j)
        {
            while (isGreat(center, ary[i]))
                i++;
            while (isGreat(ary[j], center))
                j--;

            when (i <= j)
            {
              ary[i] <-> ary[j];
                i++;
                j--;
            }
        }

        when (left < j)
            Sort(ary, left, j, isGreat);
        when (right > i)
            Sort(ary, i, right, isGreat);
    }
}

module Program
{
  Main() : void
  {
    def ary1 = array[2, 3, 1, 9, 3, 7, 0];
    ary1.Sort();
    WriteLine(ary1.ToString(", "));

    ary1.Sort(_ < _);
    WriteLine(ary1.ToString(", "));

    def ary2 = array["str2", "str23", "str21", "str29", "str23", "str27", "str20"];
    ary2.Sort();
    WriteLine(ary2.ToString(", "));
    
    ReadLine();
  }
}

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, VladD2, Вы писали:

VD> def center = ary[(left + right) / 2];
Ай-ай-ай: Статическая типизация — как это мило....

Правильно

def center = ary[left + (right - left) / 2];

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Андрей Хропов, Вы писали:

АХ>Правильно
АХ>

АХ>def center = ary[left + (right - left) / 2];
АХ>

Не смешите мои тапочки (с). Какое переполнение на логарифмических алгоритмах? У тебя сортировка сдохнет раньше. В общем, смысла в этом мало.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, Аноним, Вы писали:

А>Господа, подскажите, как лучше всего написать алгоритм быстрой сортировки массива (quicksort) на Nemerle.

Сорри за offtop, но мне кажется людям это будет интересно. В качестве первого шага в Nemerle я решил написать сортировку списка. Вот результат:

using System;

namespace NemerleTest
{
  module Program
  {
    [STAThread]
    public Main() : void
    {
      def s = mergesort([1,3,9,4,7,2,3,6]);
      Console.WriteLine(s);
    }
    
    public mergesort(l : list[int]):list[int]
    {
        | [] => []
        | a::[] => [a]
        | a::b::[] when a < b => [a,b]
        | a::b::[] => [b,a]
        | _ =>
            def merge(l1, l2)
            {
                | (a1::h1, a2::_) when a1 < a2 => a1::merge(h1,l2)
                | (_, a2::h2) => a2::merge(l1,h2)
                | (_, []) => l1
                | ([], _) => l2
            }
            def left = mergesort(l.FirstN(l.Length/2));
            def right = mergesort(l.LastN(l.Length - l.Length/2));
            merge(left, right);
    }
  }
}

Это конечно не qsort, но мне хотелось бы знать, как и что в этом коде можно улучшить.

Я бы как-то так написал бы, тут принципиально ничего нового, но читаемость ИМХО лучше.

    public MergeSort(l : list[int]) : list[int]
    {
        | []       => []
        | x::[]    => [x]
        | _        => 
            def merge(left, right, acc)
            {
                match (left, right)
                {
                    | ([],    [])    => acc
                    | (l,     [])    => acc + l
                    | ([],    r)     => acc + r
                    | (x::xs, y::ys) => 
                                        if (x < y) 
                                            merge(xs, y::ys, acc + [x])
                                        else
                                            merge(x::xs, ys, acc + [y])
                }
            }

            def left  = MergeSort(l.FirstN(l.Length / 2));
            def right = MergeSort(l.LastN (l.Length - l.Length / 2));
            merge(left, right, [])
    }

А вообще тоже хочу offtopic

То же самое, но на CL:

(defun merge-sort (list)
  (if (endp (rest list)) list
      (insert (first list) (merge-sort (rest list)))))

(defun insert (item list)
  (if (or (endp list) (< item (car list))) (cons item list)
      (cons (first list) (insert item (rest list)))))

Здравствуйте, VladD2, Вы писали:

VD>Не смешите мои тапочки (с). Какое переполнение на логарифмических алгоритмах?
Мьсьё, Вы не эстет. И совершенно не думаете о будущем. В пользовательском интерфейсе Windows 2024 4-х гигабайтными массивами никого не удивишь.

... << RSDN@Home 1.2.0 alpha rev. 692>>

Здравствуйте, Kisloid, Вы писали:

K>Я бы как-то так написал бы, тут принципиально ничего нового, но читаемость ИМХО лучше.

K>    public MergeSort(l : list[int]) : list[int]
K>    {
K>    | []       => []  // Здесь согласен - два лишних паттерна можно удалить.
K>        | x::[]    => [x]
K>        | _        => 
K>            def merge(left, right, acc) // Мне лишняя переменная не нравится. ИМХО лучше обойтись без нее.
K>            {
K>                match (left, right) // Здесь match не нужен, acc можно привязывать к _
K>                {
K>                    | ([],    [])    => acc
K>                    | (l,     [])    => acc + l
K>                    | ([],    r)     => acc + r
K>                    | (x::xs, y::ys) => 
K>                                        if (x < y) // по возможности хочется обойтись без императивщины
K>                                            merge(xs, y::ys, acc + [x])
K>                                        else
K>                                            merge(x::xs, ys, acc + [y])
K>                }
K>            }

K>            def left  = MergeSort(l.FirstN(l.Length / 2));
K>            def right = MergeSort(l.LastN (l.Length - l.Length / 2));
K>            merge(left, right, [])
K>    }

Добавив немного общности в алгоритм, в итоге у меня получилось:

    public mergesort[T](l : list[T]):list[T]
        where T : IComparable
    {
        | [] => []
        | a::[] => [a]
        | _ =>
            def merge(l1, l2)
            {
                | (a1::h1, a2::_) when a1.CompareTo(a2) < 0 => a1::merge(h1,l2)
                | (_::_, a2::h2) => a2::merge(l1,h2)
                | _ => l1 + l2
            }
            def left = mergesort(l.FirstN(l.Length/2));
            def right = mergesort(l.LastN(l.Length - l.Length/2));
            merge(left, right);
    }

K>А вообще тоже хочу offtopic

K>То же самое, но на CL:

K>

K>(defun merge-sort (list)
K>  (if (endp (rest list)) list
K>      (insert (first list) (merge-sort (rest list)))))

K>(defun insert (item list)
K>  (if (or (endp list) (< item (car list))) (cons item list)
K>      (cons (first list) (insert item (rest list)))))
K>

К сожалению с LISP-ом я плохо знаком — не могу адекватно оценить пример. Но леконичность впечатляет, и количество скобок тоже

Здравствуйте, gloomy rocker, Вы писали:

GR>Добавив немного общности в алгоритм, в итоге у меня получилось:

GR>

GR>    public mergesort[T](l : list[T]):list[T]
GR>        where T : IComparable

Ну тогда уж лучше вообще компаратор передавать для еще большей общности:

GR>    public mergesort[T](l : list[T], cmp : (T * T) -> int) : list[T]

Здравствуйте, Kisloid, Вы писали:

K>

K>            def left  = MergeSort(l.FirstN(l.Length / 2));
K>            def right = MergeSort(l.LastN (l.Length - l.Length / 2));
K>

Господа, вы бы поосторожнее были с такими вещами. Тут одна и та же работа выполняется дважды.
Я думаю, что делить список надо как-то так:

public SplitAt[T](this lst : list[T], n : int) : list[T]*list[T]
{   
        | ([], n) when n != 0 => throw Exception()
        | (xs, n) when n <= 0 => ([],xs)
        | (x::xs, n) => 
                def (xs1, xs2) = xs.SplitAt(n-1);
                (x::xs1, xs2)
}

... << RSDN@Home 1.2.0 alpha rev. 655>>

Здравствуйте, Блудов Павел, Вы писали:

VD>>Не смешите мои тапочки (с). Какое переполнение на логарифмических алгоритмах?
БП>Мьсьё, Вы не эстет. И совершенно не думаете о будущем. В пользовательском интерфейсе Windows 2024 4-х гигабайтными массивами никого не удивишь.

Там еще будут 24 процессора для которых один фиг все быстрые сортировки нужно буде переписывать (распараллеливая их работу при больших объемах).

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Блудов Павел, Вы писали:

VD>>>Не смешите мои тапочки (с). Какое переполнение на логарифмических алгоритмах?
БП>>Мьсьё, Вы не эстет. И совершенно не думаете о будущем. В пользовательском интерфейсе Windows 2024 4-х гигабайтными массивами никого не удивишь.

VD>Там еще будут 24 процессора для которых один фиг все быстрые сортировки нужно буде переписывать (распараллеливая их работу при больших объемах).

Мсье будет работать в 2024-м на таком древнем старье?

Я понимаю хотяб 1024

Здравствуйте, Kisloid, Вы писали:

K>А вообще тоже хочу offtopic

K>То же самое, но на CL:
K>

K>(defun merge-sort (list)
K>  (if (endp (rest list)) list
K>      (insert (first list) (merge-sort (rest list)))))

K>(defun insert (item list)
K>  (if (or (endp list) (< item (car list))) (cons item list)
K>      (cons (first list) (insert item (rest list)))))
K>

Каким боком это тоже самое? И вообще это не сортировка слиянием, меньше надо верить википедии. Это больше похоже на сортировку вставкой.
Аналогичный код на Nemerle:

    public InsertSort[T](this lst : list[T]) : list[T] where T : IComparable[T]
        | item :: rest =>
            def insert(lst)
                | [] | h :: _ when item.CompareTo(h) < 0 => item :: lst
                | h :: t => h :: insert(t)
            insert(MergeSort(rest))
        | _ => lst

Здравствуйте, Vermicious Knid, Вы писали:

VK>Каким боком это тоже самое? И вообще это не сортировка слиянием, меньше надо верить википедии. Это больше похоже на сортировку вставкой.

Упс, действительно просмотрел

То то я удивился, почему так кратко, но разбираться в коде не стал... лень

Вот:

(defun merge-sort (list)
  (if (small list) list
      (merge-lists
        (merge-sort (left-half list))
        (merge-sort (right-half list)))))

(defun small (list)
  (or (eq (length list) 0) (eq (length list) 1)))

(defun right-half (list)
  (last list (ceiling (/ (length list) 2))))
(defun left-half (list)
  (ldiff list (right-half list)))

(defun merge-lists (list1 list2)
  (merge 'list list1 list2 #'<))

Здравствуйте, Курилка, Вы писали:

К>Мсье будет работать в 2024-м на таком древнем старье?

К>Я понимаю хотяб 1024

Ой, лидирующую двоечку я как-то не заметил. Тогда к моей цифре добавим три нолика

Здравствуйте, Аноним, Вы писали:

А>Господа, подскажите, как лучше всего написать алгоритм быстрой сортировки массива (quicksort) на Nemerle.

У меня такая штука получилась:

  public qsort(arr: list[int], distinct: bool): list[int]
  {
    | ([], _) => [];
    | (x::[], _) => [x];
    | (x::xs, true) => qsort($[y | y in xs, y<x], distinct) + [x] + qsort($[y | y in xs, y>x], distinct);
    | (x::xs, false) => qsort($[y | y in xs, y<=x], distinct) + [x] + qsort($[y | y in xs, y>x], distinct);
  }

Если второй параметр true, то заодно и повторяющиеся элементы убираются...

Здравствуйте, gloomy rocker, Вы писали:

GR>Сорри за offtop, но мне кажется людям это будет интересно. В качестве первого шага в Nemerle я решил написать сортировку списка. Вот результат:
Вобще говоря самый быстрый и короткий способ отсортировать список в немерле это:

    public arrsort[T](l : list[T], cmp : T * T -> int) : list[T]
    {
        l.ToArray().SortInplace(cmp).ToList()
    }

Ну а если уж хочется написать руками то нужно писать правильно (попробуй своей сортировкой отсортировать список хотябы из 100К элементов):

    public mergesort[T](src : list[T], cmp : T * T -> int) : list[T]
    {
        def merge(list1, list2, merged = [])
        {
            def cat(merged, tail)
            {
            | ([], tail) => tail;
            | (head :: merged, tail) => cat(merged, head :: tail);
            }
            match (list1, list2)
            {
            | (head1 :: tail1, head2 :: tail2) =>
                if (cmp(head1, head2) < 0)
                    merge(tail1, list2, head1 :: merged);
                else
                    merge(list1, tail2, head2 :: merged);
            | (list1, []) => cat(merged, list1);
            | ([], list2) => cat(merged, list2);
            }
        }
        def sort(tail, len1, sorted1, len2, sorted2)
        {
            match (tail)
            {
            | [] | _ when len1 == len2 =>
                (tail, len1 + len2, merge(sorted1, sorted2));
            | head :: tail =>
                def (tail, len2, sorted2) = sort(tail, len2, sorted2, 1, [head]);
                sort(tail, len1, sorted1, len2, sorted2);
            }
        }
        match (src)
        {
        | head :: tail =>
            def ([], _, sorted) = sort(tail, 0, [], 1, [head]);
            sorted;
        | [] => [];
        }
    }

... << RSDN@Home 1.2.0 alpha rev. 745>>

Здравствуйте, WolfHound, Вы писали:

WH>Вобще говоря самый быстрый и короткий способ отсортировать список в немерле это:
WH>

WH>    public arrsort[T](l : list[T], cmp : T * T -> int) : list[T]
WH>    {
WH>        l.ToArray().SortInplace(cmp).ToList()
WH>    }
WH>

Вообще-то у списка есть метод Sort (вызывающий List.MergeSort()) который применяет метод сортировки слиянием. Возоможно на коротких списках он окажется эффективнее. По крайней мере он вполне эффективен чтобы его применять в большинстве мест.

А вообще, если нужны сортированные списки, то лучше использовать массивы. Список не очень рассчитан на это.

Здравствуйте, VladD2, Вы писали:

VD>Вообще-то у списка есть метод Sort (вызывающий List.MergeSort()) который применяет метод сортировки слиянием. Возоможно на коротких списках он окажется эффективнее. По крайней мере он вполне эффективен чтобы его применять в большинстве мест.
На коротких списках они примерно одинаковы. По крайней мере наводки от всякой фигни больше.
Чем дальше тем сильнее сортировка через массив выигрывает.
Кстати мой mergesort работает быстрее чем List.MergeSort

... << RSDN@Home 1.2.0 alpha rev. 745>>

	От:	Аноним
	Дата:	22.01.07 10:53
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	22.01.07 11:32
Оценка:

	От:	Андрей Хропов
	Дата:	22.01.07 13:05
	Оценка:	15 (2) +1

От:	VladD2	www.nemerle.org
Дата:	22.01.07 14:00
Оценка:

	От:	gloomy rocker
	Дата:	09.08.07 08:50
	Оценка:

	От:	Блудов Павел
	Дата:	10.08.07 11:51
	Оценка:

От:	Курилка	http://kirya.narod.ru/
Дата:	12.08.07 16:33
Оценка:

	От:	Vermicious Knid
	Дата:	13.08.07 12:50
	Оценка:

	От:	RomulS
	Дата:	24.01.08 22:17
	Оценка:

	От:	WolfHound
	Дата:	25.01.08 19:15
	Оценка:

	От:	WolfHound
	Дата:	27.01.08 17:22
	Оценка: