Комментарии 22
Я о том, (что)[https://www.red-gate.com/simple-talk/sql/t-sql-programming/window-functions-in-sql/] "Windowing functions were added to the ANSI/ISO Standard SQL:2003 and then extended in ANSI/ISO Standard SQL:2008", а происходит это уже при наличии процедурных решений… Удобство использования расширяют
Блин! Опять быстрая сортировка! Вы рискуете распугать тех, кто действительно заинтересован декларативным подходом и призвать троллей. Это, увы, не самый лучший пример. Дело в том, что хоаровский вариант реально быстр и сортирует на месте. Рекурсивный же только записывается красиво, но хоаровским, увы, не является. Это разные алгоритмы с разными свойствами. Об этом уже много раз писали на разных языках, статьи легко гуглятся. Главный аргумент троллей: евангелисты-декларативщики опять и опять приводят два-три примера неработающих алгоритмов! В хаскеллевском Data.List используется mergesort, поскольку сам по себе quicksort непрактичен и в функциональной реализации жаден до памяти. Декларативный подход серьезно играет в большем: в построении реактивных систем, в алгебраическом описании сложных архитектур, в принципиальной доказуемости декларативных утверждений. Я понимаю и полностью разделяю восхищение, испытываемое при первом знакомстве с ленивым "решетом Эратосфена" на Хаскеле (которое тоже вовсе не оно), или тем же рекурсивным quicksort, но прошу: не останавливайтесь на этом! Мы не должны выглядеть евангелистами с одними и теми же простыми притчами, у функционального и логического программирования есть гораздо больше классных результатов. Правда, они сложнее . А главное: не противопоставляйте парадигмы. Это мешает искусству владения ими всеми.
Спасибо, может немного и наивно получилось, но выразить декларативно сортировку слиянием, у меня выходит без обращений к первоисточнику, а вот представить себе алгоритм (Фон-Неймана)[http://www.sql.ru/forum/719824/sortirovka-sliyaniem] в алгоритмическом виде — совсем не просто.
Есть принцип сортировки, а он алгоритмический или декларативный, вот это меня интересует, как мы представляем себе вычисления?
Как вы формулируете решения, удобно ли задумываясь о последовательности действий?
Может и правда хватит изучать императивные языки, а что для вас более привлекательно?
Аналогично, зачем стричь ногти, когда есть топор?
Мы как путешественники по своим мыслям, и анализаторы своего состояния, должны понимать где хорошо, а где иначе, где же именно мы находимся, вот к этому хочу привлечь внимание читателей.
Чтобы понимать, где хорошо, а где иначе, полезно бы уметь выражать свои мысли.
Как мы складываем цепочки мыслей,
По-разному. А вам это не очевидно?
выражать все последовательностью команд и переходов между ними, мне кажется архаичным и устаревшим
Рецепты вам тоже кажутся "архаичными и устаревшими"?
Мне кажется, если выражать программу логическим языком, она будет выглядеть понятнее
Вам кажется. Программы бывают разные, и для разных программ удобнее разные способы выражения.
При небольшой разнице в производительности
На глаз — qsort всего процентов на пятьдесят дольше выполняется. Совершенно небольшая разница. Незначительная.
qsort([H|T])->qsort([X||X<-T,X<H]++[H|qsort([X||X<-T,X>=H])].
Тут закрывающая круглая скобка не пропущена, случайно?
qsort([])->[];
qsort([H|T])->qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].
А вот так, работает еще быстрее:
qsort2([])->[];
qsort2([H|T])->{S1,S2}=part(H,T,[],[]),qsort2(S1)++[H|qsort2(S2)].
part(_,[],S1,S2)->{S1,S2};
part(H,[H1|T],S1,S2) when H1<H->part(H,T,[H1|S1],S2);
part(H,[H1|T],S1,S2)->part(H,T,S1,[H1|S2]).
Не буду сейчас щурить глаза и смотреть в нюансы реализаций квиксорта.
Тем более, что квиксорт на цепочках и квиксорт на массивах — это два разных квиксорта, как уже верно заметили товарищи.
===Мысль вслух.===
Декларативность может идти в разных направлениях:
1) Контрактное программирование.
Мы расписываем все предусловия, инварианты, постусловия до самых мелочей, — и вуаля, если у нас последнее постусловие — "набор состоит из тех же элементов, что были на входе, и упорядочен", — мы описали сортировку. Плюс, конечно, мы должны расписать проблему остановки, а потом напихать эвристик для выбора более-менее эффективной стратегии среди прочих равновозможных.
2) Наглядное программирование.
Мы декомпозируем задачу на детальки, каждая из которых очевидным образом решает свою подзадачу, — получаем самодокументируемый код.
Сводим к минимуму залезание в чужие зоны ответственности, — именно это ставится в упрёк императивному программированию, где практикуется переприсваивание значений, и пойди отследи кто что когда.
Иммутабельность — это не самоцель, а полезная фишечка. Так-то мы спокойно можем рассмотреть изменяемый массив как некую функцию от времени на массивы: в каждый отсчёт времени (после каждой правки) — новый массив.
А если потом завернём в какую нибудь идеологию CPS и/или STM, — получим мутабельность поверх иммутабельности (или просто мутабельность, но с битьём по пальцам при желании вспомнить ушедшее былое).
===Мысль вслух.===
Когда люди берут лучшие (а точнее, единственно доступные) практики программирования на лиспе и прологе, где циклы — это рекурсия, а концевая рекурсия — это избавление от всех бед,
и переносят слово в слово на языки с достаточно дорогой рекурсией (например, на питон), — получается фигня.
В этом нет никакой декларативности! Декларативно было бы — "здесь мы выполняем одну операцию над набором данных в цикле!", вот операция, вот набор, давай-мапь-редюсь!
У квиксорта есть две большие беды.
Первое: честная рекурсия, в силу того, что задача разбивается на две подзадачи. И если один из вызовов мы можем вывернуть мясом наружу и превратить в концевую рекурсию, то второй-то уж точно никак. Тут нам пригодится эвристика, говорящая о том, что — давайте будем проваливаться в более короткую подзадачу, а более длинную оставлять на десерт.
Второе: при неудачном стечении обстоятельств декомпозиция вырождается в линейную. Соответственно, N памяти (если только мы не исхитримся с концевыми рекурсиями) и N**2 времени.
Тут нам пригодится другая эвристика, говорящая следующее: нам, в общем-то, пофиг, как именно будут отсортированы подмассивы.
Код на псевдо-эрланге, не тестировал, не обессудьте. Чисто пруф оф концепт.
qsort([]) -> [];
qsort(Xs) ->
{Ls, X, Rs} = partition(Xs),
qsort(Ls) ++ [X] ++ qsort(Rs).
% переделаем на концевую
sort(Xs) -> qsort_tail([], Xs). % голова - упорядочена и меньше хвоста
qsort_tail(Hs, []) -> Hs;
qsort_tail(Hs, [X]) -> Hs ++ [X];
qsort_tail(Hs, Xs) ->
{Ls, X, Rs} = partition(Xs),
qsort_tail(Hs ++ sort(Ls) ++ [X], Rs).
% переделаем на концевую с эвристикой - куда лучше сваливаться
sort(Xs) -> qsort_tail([], Xs, []). % голова и хвост упорядочены и меньше-больше середины
qsort_tail(Hs, [], Ts) -> Hs ++ Ts;
qsort_tail(Hs, [X], Ts) -> Hs ++ [X] ++ Ts;
qsort_tail(Hs, Xs, Ts) ->
{Ls, X, Rs} = partition(Xs),
if length(Ls) < length(Rs) ->
qsort_tail(Hs ++ sort(Ls) ++ [X], Rs, Ts);
true ->
qsort_tail(Hs, Ls, [X] ++ sort(Rs) ++ Ts)
end.
% напишем сортировку более тупую, но гарантирующую логлинейное время
heapsort(Xs) -> sort_heap(make_heap(Xs)).
% и более медленную (квадратичную) на больших наборах, но стремительную на маленьких
introsort(Xs) -> ?????. % лень выдумывать
sort(Xs) -> sort(Xs, 0).
sort(Xs, Depth) when length(Xs) < ThresholdOfIntrosort -> introsort(Xs);
sort(Xs, Depth) when Depth > ThresholdOfRecursion -> heapsort(Xs);
sort(Xs, Depth) -> qsort_tail([], Xs, [], Depth+1).
Примерно так работает std::sort в реализациях C++ для современных компиляторов — gcc, clang, VS. Ну, только с той разницей, что там всё inplace.
Кстати! Вы можете сказать: "зачем ты делаешь [X] ++ Ts, это же неэффективно? Почему не [X|Ts]?"
Да, неэффективно по скорости. Хотя и единообразно.
Но мы ведь можем сформулировать задачу сортировки так:
- разбить массив на кучу внутренне упорядоченных и взаимно упорядоченных массивов
- а потом склеить их одним махом
sort(Xs) -> flatten(sorted(Xs)).
sorted(Xs) -> qsort_tail([], Xs, []).
qsort_tail(Hs, [], Ts) -> [Hs, [], Ts];
qsort_tail(Hs, Xs, Ts) ->
{Ls,X,Rs} = partition(Xs),
if length(Ls) < length(Rs) ->
qsort_tail( [Hs, sorted(Ls), [X]], Rs, Ts );
true ->
qsort_tail( Hs, Ls, [[X], sorted(Rs), Ts] ).
(вот это — вообще пруф оф концепт, тут я специально оставил за кадром ряд возникающих проблем, которые мне лень решать на псевдоэрланге)
О, мой вопрос, в каком виде храниться или рождается мысль, как появляется следствие — решение задачи из полученных требований. какое количество входов требуется проанализировать, сортировка списка или массива, это один из входов на получение выхода "подход к сортировке", надо учесть, что каждая отдельная структура будет иметь свой эффективнейший способ обработки, для данных на магнитной ленте потребуется метод слияний и никаких быстрых сортировок не реализовать, а для Питона-массива не надо получать хвост как [1:]
Упрощение мыслей и получение более коротких упрощений, позволяет точнее формулировать решение задачи — тут перебор, а тут энлогарифм, и это решает то, какой способ выбран для описании, какова будет структура программы, накладывает структура данных и способ конвертирования данных, появляются накопительные параметры, только как промежуточное состояние, которое по цепочке приводит к нужному следствию...
А если Питону представить список как составной терм, как структуру из головы и хвоста, или кортеж из двух элементов, то уместно будет обработать его рекурсивно:
def qsort(lst):
if lst==None: return None
else:
h,t=lst
slst, ulst=parts(h,t)
return app(qsort(slst),(h,qsort(ulst)))
def app(a,b):
if a==None: return b
else:
h,t=a
return (h,app(t,b))
def parts(a,lst):
if lst==None: return (None,None)
else:
h,t=lst
mlst,ulst=parts(a,t)
if h>a: return (mlst, (h,ulst))
else: return ((h,mlst), ulst)
def flattern(lst):
if lst==None: return None
else:
if type(lst) is tuple:
h,t=lst
return app(flattern(h),flattern(t))
else: return (lst, None)
А если хвостовую рекурсию?, он превратит в цикл или просто в "гоуту"… или тут сборщик мусора все потянет на себя?
stackless python, возможно, и будет снисходителен к концевой рекурсии.
Но, скорее всего, даже ему сплохеет.
А уж референтные реализации CPython и PyPy — точно вычерпают весь стек.
Концевая рекурсия — это такое рукодельное неявное continuation passing style.
Это как на фортране — ты пишешь цикл, а компилятор такой "эге! здесь же векторная, а то и матричная, операция! дай-ка вставлю векторную команду или вызову функцию из библиотеки линейной алгебры!"
Беда в том, что интерпретаторы питона не настолько сильны, чтобы говорить "эге!"
Поэтому лучше выражать операции над списками именно через операции над ними — в виде циклов, генераторных выражений, вызовов функций высшего порядка.
Концевая рекурсия — это некоторая свёртка. Поэтому мы можем декомпозировать её на элементарную операцию и на диспетчерский код, выполняющий забег в цикле. (Возможно, что это будет явно написанный цикл :) )
Кстати, для настраивания мозгов рекомендую статью Эрика Мейера "бананы, линзы, конверты и колючая проволока" — про всевозможные разновидности преобразования списков.
Нашёл только английский пдф https://maartenfokkinga.github.io/utwente/mmf91m.pdf — вроде, кто-то брался переводить на русский, но то ли заглохло, то ли утонуло в поисковой выдаче.
И ещё момент. Конс-пары безжалостны к памяти.
В языках, где конс-пары являются фундаментальным типом — а это практически все ФП и пролог, — куча устроена так, чтобы как можно дешевле хранить огромную тучу пар. Например, отдельно пул памяти для пар, отдельно для атомов, и отдельно — для больших объектов.
В питоне все примитивные структуры — это массивы переменной длины. Даже кортеж содержит, помимо своих данных, ещё заголовок объекта с указателем на тип, счётчиком ссылок и размером массива…
Получается, на каждый элемент списка мы разворачиваем рядом кортеж.
Ну и поскольку кортежи и прочие данные ничем особо друг от друга не отличаются, то все они хранятся в одном общем пуле и бешено фрагментируют его.
Как игрушечный код — можно делать список по-лисповски. Как промышленный — лучше даже не пробовать.
Декларативное мышление