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

RD>Боюсь, что я не настолько силен в Haskell чтобы сходу понять. В частности, не ясно что происходит с "y" в qsort3'. Название "part" тоже ясности не добавляет.
RD>Мой ghc, кстати, тоже в непонятках. Говорит "Non-exhaustive patterns in function qsort3'".

Я не dmz, но представлю, по-сути аналогичное, но рабочее решение.

Все как и раньше, но:
1. На каждой итерации список просматривается один раз (достигается за счет split)
2. Сортировка идет относительно значения из середины списка (mean), а не головы списка.

qsort [] = []
qsort xs = qsort lesser ++ equals ++ qsort greater
  where (lesser,equals,greater) = split mean xs
        mean = xs !! (length xs `div` 2)

-- делит список xs на три части, возвращает тупл (элементы меньшие mean, равные mean, большие mean)
split mean xs = split' [] [] [] xs
  where split' ls es gs [] = (ls,es,gs)
        split' ls es gs (p:ps) | p < mean  = split' (p:ls) es     gs     ps
                               | p == mean = split' ls     (p:es) gs     ps
                               | p > mean  = split' ls     es     (p:gs) ps

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

RD>Мой ghc, кстати, тоже в непонятках. Говорит "Non-exhaustive patterns in function qsort3'".
Выпала пара клауз:

qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []

qsort3' [] y     = y   -- +++
qsort3' [x] y    = x:y -- +++
qsort3' (x:xs) y = part xs [] [x] []  
    where
        part [] l e g = qsort3' l (e ++ (qsort3' g y))
        part (z:zs) l e g 
            | z > x     = part zs l e (z:g) 
            | z < x     = part zs (z:l) e g 
            | otherwise = part zs l (z:e) g

Z>Выпала пара клауз:

Z>

Z>qsort3 :: Ord a => [a] -> [a]
Z>qsort3 x = qsort3' x []

Z>qsort3' [] y     = y   -- +++
Z>qsort3' [x] y    = x:y -- +++
Z>qsort3' (x:xs) y = part xs [] [x] []  
Z>    where
Z>        part [] l e g = qsort3' l (e ++ (qsort3' g y))
Z>        part (z:zs) l e g 
Z>            | z > x     = part zs l e (z:g) 
Z>            | z < x     = part zs (z:l) e g 
Z>            | otherwise = part zs l (z:e) g
Z>

Спасибо, теперь все заметно понятнее :)

Попробовал сделать bench и сравнить три имеющихся варианта. Результаты для 1 000 000 случайных чисел на ghc -O2:

Version: Vanilla
Time taken: 8.376607 seconds
Time taken: 2.953175 seconds
Time taken: 2.874494 seconds
Time taken: 2.930531 seconds
Time taken: 2.854348 seconds
-----------------
Version: Buravchik's
Time taken: 2.190905 seconds
Time taken: 2.301595 seconds
Time taken: 2.318359 seconds
Time taken: 2.234913 seconds
Time taken: 2.26321 seconds
-----------------
Version: dmz / z00n
Time taken: 1.388251 seconds
Time taken: 1.462289 seconds
Time taken: 1.387326 seconds
Time taken: 1.510869 seconds
Time taken: 1.223017 seconds
-----------------

По-моему неплохо. Хотя императивный алгоритм в той же Javа справляется за 0.15 секунд, в некоторых случаях это не критично. А когда нужна только часть результата то у Хаскеля есть все шансы порвать императивных конкурентов.
P.S. Всплеск в первом проходе в "vanilla" видимо вызван тем, что что-то недовычислилось в исходных данных. Я в Haskell не силен, так что сделать все strict у меня не получилось.

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

RD>По-моему неплохо. Хотя императивный алгоритм в той же Javа справляется за 0.15 секунд, в некоторых случаях это не критично. А когда нужна только часть результата то у Хаскеля есть все шансы порвать императивных конкурентов.
RD>P.S. Всплеск в первом проходе в "vanilla" видимо вызван тем, что что-то недовычислилось в исходных данных. Я в Haskell не силен, так что сделать все strict у меня не получилось.

Здесь надо понимать, что императивный вариант использует технику Хоара, а в случае Хаскеля применяются однонаправленные списки. Хаскельный вариант на полной сортировке никогда не обгонит quicksort в варианте Хоара на массиве.

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

RD>По-моему неплохо. Хотя императивный алгоритм в той же Javа справляется за 0.15 секунд, в некоторых случаях это не критично. А когда нужна только часть результата то у Хаскеля есть все шансы порвать императивных конкурентов.

Кстати, в приведенном варианте функция part использует хвостовую рекурсию, и поэтому должна вычисляться полностью при обращении к первому элементу. Анализатор строгости ghc, соответственно, в компиляторе должен будет убить ленивость в part. Это может плохо сказаться на характеристике получения части результата. И наоборот — хорошо сказаться при вычислении всего результата. По хорошему, надо ее переписать без хвостовой рекурсии, и сравнить на частичных результатах.

RD>>По-моему неплохо. Хотя императивный алгоритм в той же Javа справляется за 0.15 секунд, в некоторых случаях это не критично. А когда нужна только часть результата то у Хаскеля есть все шансы порвать императивных конкурентов.
RD>>P.S. Всплеск в первом проходе в "vanilla" видимо вызван тем, что что-то недовычислилось в исходных данных. Я в Haskell не силен, так что сделать все strict у меня не получилось.

G>Здесь надо понимать, что императивный вариант использует технику Хоара, а в случае Хаскеля применяются однонаправленные списки. Хаскельный вариант на полной сортировке никогда не обгонит quicksort в варианте Хоара на массиве.

Насчет разницы алгоритмов — согласен. Но быть может есть какой-то purely functional вариант quicksort что порвет вариант Хоара даже на полной сортировке. Так или иначе, результат в целом неплохой при умеренной сложности самого алгоритма. :-)

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

RD>Насчет разницы алгоритмов — согласен. Но быть может есть какой-то purely functional вариант quicksort что порвет вариант Хоара даже на полной сортировке.

Нету. Вариант Хоара — самый оптимальный и экономный вариант quicksort из известных человечеству, сформулированный в терминах, близких к железу . Так как Хаскельный вариант выполняется на том же железе, то быстрее на полной сортировке он в принципе оказаться не может .

Тем более, что если не оперировать списками, то пропадет вся приятная функциональшина. Ибо список — самый "функциональный" тип данных. Так же как массив — самый "императивный".

RD>Так или иначе, результат в целом неплохой при умеренной сложности самого алгоритма.

А вот это — да. Собственно, об этом и надо говорить, ИМХО Немногие программы сейчас требуют производительности любой ценой. Скажем так, отношение производительности программы к умственным затратам программиста существенно превосходит таковые для языка С. Поэтому, в реальных условиях Хаскельные программы могут оказаться быстрее, чем С++. Или, по крайней мере, не сильно медленнее. Зато — проще и надежнее.

Это если не говорить о встраиваемых системах, высоконагруженных серверных приложениях (они по принципам программирования похожи на предыдущие), и вообще — задачах, требующих реакций реального времени.

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

Я тоже провел небольшое исследование...

Вот реализации, которые были использованы:

-- Вариант 0 (quick sort "в лоб")
qsort0 [] = []
qsort0 (x:xs) = qsort0 (filter (<x) xs) ++ [x] ++ qsort0 (filter (>=x) xs)

-- Вариант 1 (мой вариант) - один проход по списку
-- сортировка относительно середины списка
qsort2 [] = []
qsort2 xs = qsort2 lesser ++ equals ++ qsort2 greater
  where (lesser,equals,greater) = split mean xs
        mean = xs !! (length xs `div` 2)

split mean xs = split' [] [] [] xs
  where split' ls es gs [] = (ls,es,gs)
        split' ls es gs (p:ps) | p < mean  = split' (p:ls) es     gs     ps
                               | p == mean = split' ls     (p:es) gs     ps
                               | p > mean  = split' ls     es     (p:gs) ps

-- Вариант 1 (dmz / z00n)
qsort3 x = qsort3' x []

qsort3' [] y = y
qsort3' [x] y = x:y
qsort3' (x:xs) y = part xs [] [x] []  
    where
        part [] l e g = qsort3' l (e ++ (qsort3' g y))
        part (z:zs) l e g 
            | z > x     = part zs l e (z:g) 
            | z < x     = part zs (z:l) e g 
            | otherwise = part zs l (z:e) g

---

Результаты. Каждая клетка обозначает:

Время / память для 100 тыс. элементов Время / память для 1 млн. элементов

Сортируемый список --> Алгоритм сортировки	Случайные значения	Отсортированные значения	В обратном порядке
Вариант 0 ("простая программа" на Haskell)	1.06 sec / 10 Mb 103.77 sec / 92 Mb	480.72 sec / 7 Mb * Более 600 sec *	* out of memory * * out of memory *
Вариант 1 (мой)	0.17 sec / 12 Mb 1.86 sec / 122 Mb	0.17 sec / 6 Mb 2.08 sec / 56 Mb	0.16 sec / 6 Mb 2.03 sec / 56 Mb
Вариант 2 (dmz / z00n)	0.08 sec / 6 Mb 1.08 sec / 57 Mb	258.28 sec / 7 Mb * Более 600 sec *	259.47 sec / 7 Mb * Более 600 sec *
Sort из стандартной библиотеки (merge sort)	0.34 sec / 17 Mb 5.67 sec / 150 Mb	0.13 sec / 9 Mb 1.64 sec / 75 Mb	0.16 sec / 12 Mb 1.83 sec / 121 Mb

Выводы:
Как видно, некоторые алгоритмы проваливаются при сортировке уже отсортированных списков (в прямолм или обратном порядке).
Самый быстрый алгоритм на случайных данных — вариант 2 (dmz / z00n), начальный вариант 0 в 10 раз медленнее.
На отсортированных списках лучше всех работает merge sort, хотя он и проседает на случайных данных.
Вариант 1 (мой) — что-то среднее между этим всеми алгоритмами Работает стабильно на всех типах входных данных.

Б>Вариант 1 (мой) — что-то среднее между этим всеми алгоритмами Работает стабильно на всех типах входных данных.

Очень интересно.

Буду знать, на всякий случай.

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

В предыдущем сообщении я представлял замеры для случайных и отсортированных списков.
И если для отсортированных все понятно — там использовались списки [1..n] и [n,n-1 .. 1], то со случайными есть вопрос.

Похоже, у меня получился какой-то неправильный случайный список Поэтому оказались не верны и результаты для случайных списков.
Исправляя данную оплошность я сделал изменения:
— длина списков 200 тыс, 400 тыс, 800 тыс., 1,6 млн, 3,2 млн
— случайные списки формируются 5 раз с разными seed

rnds seed = randomRs (1,1000000) (mkStdGen seed) :: [Int]
list = take n $ rnds seed

— в каждой клетке 5 значений — для seed = [1..5]

RANDOM LISTS

Count --> Algorithm	200'000	400'000	800'000	1'600'000	3'200'000
sort ( mergesort from Data.List)	2.16s secs / 76 Mb 2.17s secs / 76 Mb 2.16s secs / 76 Mb 2.17s secs / 76 Mb 2.14s secs / 76 Mb	5.95s secs / 152 Mb 5.97s secs / 152 Mb 6.00s secs / 152 Mb 6.00s secs / 152 Mb 5.92s secs / 152 Mb	18.13s secs / 298 Mb 18.09s secs / 298 Mb 18.14s secs / 298 Mb 18.05s secs / 298 Mb 18.03s secs / 298 Mb	59.30s secs / 596 Mb 59.45s secs / 596 Mb 59.55s secs / 596 Mb 59.47s secs / 596 Mb 59.42s secs / 596 Mb	209.13s secs / 1193 Mb 209.42s secs / 1193 Mb 208.73s secs / 1193 Mb 209.22s secs / 1193 Mb 209.16s secs / 1193 Mb
qsort ( quick sort original)	0.75s secs / 21 Mb 0.73s secs / 22 Mb 0.70s secs / 18 Mb 0.70s secs / 18 Mb 0.75s secs / 21 Mb	1.66s secs / 41 Mb 1.59s secs / 43 Mb 1.52s secs / 37 Mb 1.58s secs / 37 Mb 1.56s secs / 41 Mb	3.64s secs / 86 Mb 3.55s secs / 86 Mb 3.33s secs / 73 Mb 3.39s secs / 75 Mb 3.39s secs / 81 Mb	7.98s secs / 166 Mb 7.67s secs / 172 Mb 7.31s secs / 149 Mb 7.48s secs / 146 Mb 7.47s secs / 163 Mb	17.88s secs / 342 Mb 17.22s secs / 343 Mb 16.45s secs / 292 Mb 16.83s secs / 284 Mb 16.94s secs / 328 Mb
qsort2 ( quick sort Buravchik)	0.94s secs / 44 Mb 0.98s secs / 44 Mb 0.97s secs / 44 Mb 0.95s secs / 43 Mb 0.97s secs / 43 Mb	2.48s secs / 83 Mb 2.48s secs / 83 Mb 2.45s secs / 83 Mb 2.36s secs / 83 Mb 2.48s secs / 83 Mb	6.92s secs / 165 Mb 6.88s secs / 165 Mb 6.70s secs / 165 Mb 6.64s secs / 165 Mb 6.70s secs / 165 Mb	20.56s secs / 329 Mb 20.38s secs / 329 Mb 20.41s secs / 329 Mb 20.69s secs / 329 Mb 20.89s secs / 329 Mb	68.50s secs / 657 Mb 69.56s secs / 657 Mb 68.91s secs / 657 Mb 69.19s secs / 657 Mb 68.84s secs / 657 Mb
qsort3 ( quick sort dmz / z00n)	0.33s secs / 10 Mb 0.34s secs / 11 Mb 0.34s secs / 10 Mb 0.33s secs / 11 Mb 0.34s secs / 10 Mb	0.75s secs / 22 Mb 0.73s secs / 22 Mb 0.73s secs / 22 Mb 0.75s secs / 23 Mb 0.72s secs / 22 Mb	1.58s secs / 43 Mb 1.69s secs / 45 Mb 1.63s secs / 45 Mb 1.56s secs / 46 Mb 1.64s secs / 45 Mb	3.72s secs / 91 Mb 3.67s secs / 90 Mb 3.70s secs / 93 Mb 3.70s secs / 91 Mb 3.63s secs / 93 Mb	8.44s secs / 181 Mb 8.73s secs / 185 Mb 8.05s secs / 182 Mb 8.25s secs / 182 Mb 8.09s secs / 184 Mb

1. Как и было ранее лучшим был признан алгоритм (dmz / z00n)
2. В два раза от победителя отстает простейший qsort (раньше отставал сильнее).
3. Мой алгоритм qsort2 раньше отставал в 1,7 раз. Сейчас при увеличении длины списка отстает от победителя все сильнее и сильнее. Очевидно, что сложность его выше.
4. Худшим стал стандартный sort (на основе merge sort). Судя по исходникам бывший когда-то quicksort заменили на mergesort. Время работы растет быстрее, чем у qsort и qsort3, и даже быстрее чем у qsort2.

Так, что стабильность моего алгоритма отменяется

В общем, вот такая ситуация для случайных списков...

Может вообще перед сортировкой проверять насколько сильно уже отсортирован список и потом вызывать соответствующий тип сортировки:
для отсортированных списков — Data.List.sort, для неотсортированных — qsort3?

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

Б> mean = xs !! (length xs `div` 2)

Вот эта часть очень смущает. Полтора раза по списку проходит?

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

Б>> mean = xs !! (length xs `div` 2)

DM>Вот эта часть очень смущает. Полтора раза по списку проходит?

Ну, в общем-то да. Но это позволяет хоть как-то отрабатать на отсортированных списках. И я не знаю иного способа найти в них подходящий опорный элемент.

Вот интересно, можно ли за один проход по списку найти его медиану? Построением дерева какого-нибудь, например. Частный случай со списком чисел не рассматриваем.