Эй, фулстеки, давайте тренировать навыки. Предлагаю разминать извилины, как мне кажется, это интересно делать используя иную, непривычную, парадигму. Большинство разработчиков имеют развитой скилл алгоритмизации — задача превращается в кирпичики, которые нужно соединить, продумать последовательность ходов, которая приводит к желаемому заключению.
Вот тут, неделю назад, был упомянут Пролог, хотелось бы ответить, что язык Пролог подходит для решения задачек. Я уже затрагивал эту тему, и приводил несколько доступных мне решений случайных задач с сайта с заданиями на алгоритмы, хотелось бы показать, что любое сложное решение доступно изложению на декларативном языке, да и работать оно может не медленнее (ну-у, может, заметно не очень медленнее).
Взяться за представления следующей задачки долго не получалось, и вот уже получено первое решение, демонстрирую задачу и узнаю, на сколько оно сильно медленно.
Пролог интересен тем, что можно сотворить дедуктивную программу, которая показывает множество решений и может даже ограничивать его, но не дает способ перебора,
алгоритм будет выработан решателем интерпретатором.
Так вот, задача такова:
- Trapping Rain Water II
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Example:
Given the following 3x6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
Return 4.
После продолжительных попыток сформулировать решение, я дошел до вот такой формулировки:
Нужно в каждую клеточку налить максимум воды, который бы из нее не вылился. Я предлагаю залить в каждую клеточку, какое-то количество воды, но так чтобы оно было менее равно максимально значения из всех возможных.
Получилось так:
reptest(X0,X2):-
flatten(X0,FX0),
sort(0,>,FX0,Vals),
repdown(X0,Vals,X0,X2),!.этот предикат берет входной список (матрицу), и превращает ее в решение, в матрицу, в которой стоят другие значения, которые будут допустимым ответом. Потом другой предикат эти два списка отнимет поэлементно и найдет итоговую сумму.
repdown(X0,Vals,X,X1):-
puts(Vals,X0,X1),
X\=X1,
balns(X0,X1),!.
repdown(_,_,X,X).этот предикат будет брать одно из решений, и проверять "нормально" ли оно заполнено, если удовлетворяет условию задачи, тогда это и есть решение.
Это метод "генерировать и проверить", мы говорим что величина в таком-то множестве и пересматриваем все элементы этого множества, проверяя какое-то условие выхода.
Значит, далее предикатом puts(Vals,X0,X1) буду получать новое решение, здесь на первом месте стоит список всех возможных значений высот, которые есть в этой матрице, из него будут выбираться возможные значения высот для каждой клеточки. По анализу входных тестов, было выяснено, что в этой задаче можно залить всю клеточку, если вокруг нее можно вставить столько воды, что ее переливает "с головой".
Итого этот предикат, выглядит посложнее, надо обработать тройки строк, из которых складывается один квадрат 3х3 (да-да в Прологе нет массива, но так выглядит описание входных данных, так этим и пользуемся, в декларативном программировании можно не знать про индексы элементов в массиве, тут есть только список с его головой и хвостом, поэтому просто описываем такой шаблон, который соответствует входной спецификации).
puts(_,[],[]).
puts(_,[X],[X]).
puts(_,[X,Z],[X,Z]).
puts(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,sel_biger(R2,V,R21),puts(V,[R21,R3|T],St).
puts(V,[R1,R2,R3|T],[R1|St]) :- puts(V,R2,R21),puts(V,[R21,R3|T],St).Вот так получается выразить обход матрицы, у которой можно взять три первых (и далее) строки, у которых, также можно выделить, слева-направо, тройки элементов, и вот между восемью соседями окажется одна [Итая][Ётая] клеточка ландшафта. С помощью sel_biger(R2,V,R21) делается новое значение этой клеточки.
Это значение можно установить текущей клеточке, оно может быть одной из возможных высот, да еще и список их отсортирован по-убыванию, так что первой будет наибольшая высота, которая доступна вообще, а далее любая за ней:
sel_biger(C,[H|_],H):-H>=C.
sel_biger(C,[_|T],X):-sel_biger(C,T,X).Это было описание "генератора решений", а далее надо убедиться, что получена матрица, из как угодно заполненных высот в каждой точке, похожа на требуемый от нас ответ.
А требовалось найти такое состояние, что вода осядет в лунках, попробую выразится вот так:
из девяти значений квадрата три на три, в центре всегда должна быть такая высота, чтобы она не противоречила входной карте, чтобы не получалось изменение баланса, который был изначально в этих клеточках, если была высота, то выше нее не должно остаться клеточек, даже если все зальет водой, тогда тут можно говорить, что высокая клеточка должна оставаться собой или быть заменена на более высокое значение, но такое что оно равно всем соседям, т.е. клеточки слева-справа и сверху-снизу от текущей должны ее превышать или быть равны, если в клеточке стало более воды, то только если и вокруг поднялась...
%%проход по строкам
balns([],[]).
balns([_],[_]).
balns([_,_],[_,_]).
balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :-
blevel(B1,B2,B3,R1,R2,R3),
balns([B2,B3|Tb],[R2,R3|T]).
%%из трех строк выбираем по тройке, для создания квадрата 3х3
blevel([],[],[],[],[],[]).
blevel([_],[_],[_],[_],[_],[_]).
blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]).
blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb],
[_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):-
equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]),
blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb],
[U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]).
%%одинаков характер элементов в квадратах,
%значение может сохраняется или быть менее равно соседей
equ(_,[],_,[]):-!.
equ(C,_,C,_):-!.
equ(C0,_,C,N):-C>C0,!,findall(X,(member(X,N),X<C),[]).
equ(C0,[C0|T0],C,[C|T]):-!,equ(C0,T0,C,T).И финальные два предиката, которые берут входную матрицу, запускают поиск подходящего результата, вычитают сумму элементов между собой, и находят конечную сумму, которая требовалась в задаче:
diffall(L0,L2,S):-
flatten(L0,F0),sum_list(F0,S0),
flatten(L2,F2),sum_list(F2,S2),
S is S2-S0.
%%это главный предикат, входной список и выход сумма
sums(X,S):-reptest(X,X1),diffall(X,X1,S).Продемонстрирую тесты, которые предоставил сайт.
reptest(X0,X2):-
flatten(X0,FX0),
sort(0,>,FX0,Vals),
repdown(X0,Vals,X0,X2),!.
repdown(X0,Vals,X,X1):-
puts(Vals,X0,X1),
X\=X1,
balns(X0,X1),!.
repdown(_,_,X,X).
puts(_,[],[]).
puts(_,[X],[X]).
puts(_,[X,Z],[X,Z]).
puts(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,sel_biger(R2,V,R21),puts(V,[R21,R3|T],St).
puts(V,[R1,R2,R3|T],[R1|St]) :- puts(V,R2,R21),puts(V,[R21,R3|T],St).
sel_biger(C,[H|_],H):-H>=C.
sel_biger(C,[_|T],X):-sel_biger(C,T,X).
%проход по строкам
balns([],[]).
balns([_],[_]).
balns([_,_],[_,_]).
balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :-
blevel(B1,B2,B3,R1,R2,R3),
balns([B2,B3|Tb],[R2,R3|T]).
%из трех строк выбираем по тройке, для создания квадрата 3х3
blevel([],[],[],[],[],[]).
blevel([_],[_],[_],[_],[_],[_]).
blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]).
blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb],
[_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):-
equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]),
blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb],
[U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]).
%одинаков характер элементов в квадратах,
%значение может сохраняется или быть более равно соседей
equ(_,[],_,[]):-!.
equ(C,_,C,_):-!.
equ(C0,_,C,N):-C>C0,!,findall(X,(member(X,N),X<C),[]).
equ(C0,[C0|T0],C,[C|T]):-!,equ(C0,T0,C,T).
diffall(L0,L2,S):-
flatten(L0,F0),sum_list(F0,S0),
flatten(L2,F2),sum_list(F2,S2),
S is S2-S0.
sums(X,S):-reptest(X,X1),diffall(X,X1,S).
%unit-tests framework
assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp).
:-assert_are_equal(sums([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]],4),true).
:-assert_are_equal(sums([[1,3,3,1,3,2],[3,2,1,3,2,3],[3,3,3,2,3,1]],4),true).
:-assert_are_equal(sums([[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]],14),true).
:-assert_are_equal(sums([[2,3,4],[5,6,7],[8,9,10],[11,12,13],[14,15,16]],0),true).
:-assert_are_equal(sums([],0),true).
:-assert_are_equal(sums([[1]],0),true).
:-assert_are_equal(sums([[2,3]],0),true).
:-assert_are_equal(sums([[3],[2]],0),true).
:-assert_are_equal(sums([[18,2,3],[4,5,6],[7,8,9]],0),true).
:-assert_are_equal(sums([[3,5,5],[5,4,5],[5,5,5]],1),true).
:-assert_are_equal(sums([[5,5,5,1],[5,1,1,5],[5,1,5,5],[5,2,5,8]],3),true).
:-assert_are_equal(sums([[2,2,2],[2,1,2],[2,1,2],[2,1,2]],0),true).
:-assert_are_equal(sums([[17,2,3,4,5,6,7,8,9,10]],0),true).
:-assert_are_equal(sums([[9,9,9,9,9],[9,2,1,2,9],[9,2,8,2,9],[9,2,3,2,9],[9,9,9,9,9]],57),true).
%:-assert_are_equal(sums([[9,9,9,9,9,9,8,9,9,9,9],[9,0,0,0,0,0,1,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,9,9,9,9,9,9,9,9,9,9]],215),true).
:-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true).
:-assert_are_equal(sums([[3,3,4,4,4,2],[3,1,3,2,1,4],[7,3,1,6,4,1]],5),true).
%:-assert_are_equal(sums([[78,16,94,36],[87,93,50,22],[63,28,91,60],[64,27,41,27],[73,37,12,69],[68,30,83,31],[63,24,68,36]],44),true).Пришлось тесты подкомментировать т.к. не все проходили.
Задача, как это ускорить?
Часть решений не находиться, из-за долгого перебора решений, слишком медленно генерировать их в таком порядке, тут сложность наверное n!, все возможные значения для каждой клеточки массива перебираются.
Эту задачу удобно выразить в системе программирования в ограничениях, как раз на Прологе это называется так: CLP(FD): Constraint Logic Programming over Finite Domains.
clp(fd) is a library included in the standard SWI-Prolog distribution. It solves problems that involve sets of variables, where relationships among the variables need satisfied.
>>
Сформулирую задачу вот так:
Нам нужен такой список, каждый элемент которого из множества значений более или равно его и максимального значения по всей карте, с учетом ограничения, что элементы должны быть расположены четко в порядке соответствующем разлившейся жидкости.
Вот так я делаю из входного списка, новый список, элементы которого стали неизвестными в заданном диапазоне (от Значения R2 текущего элемента и до Максимального значения V)
На входе список из списков, на выходе новый список с максимальной расстановкой значений,
которые удовлетворяют ограничению "баланса жидкости" balns:
checks(X0,X2):-
flatten(X0,FX),
max_list(FX,Max),checks(Max,X0,X2),
balns(X0,X2),
flatten(X2,FX2),
labeling([down],FX2).
checks(_,[],[]).
checks(_,[X],[X]).
checks(_,[X,Z],[X,Z]).
checks(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,
R21 in R2..V,
checks(V,[R21,R3|T],St).
checks(V,[R1,R2,R3|T],[R1|St]) :- checks(V,R2,R21),checks(V,[R21,R3|T],St).Это и генератор и одновременно проверка, указано что элементы находятся в таком множестве, а потом постепенно накладывая проверку происходит сужение этого множества. Далее, что-то остается, и его можно "пометить", т.е. расставить целочисленные значения, которые будут удовлетворять сумме всех ограничений. Вызов labeling([down],FX2) заставляет заполниться(связаться) переменным неизвестным с конкретными значениями, и таких вариантов может быть несколько, но всегда возьмем самый первый, так как было сказано, что все переменные двигаются вниз при поиске, от своих верхних границ, это опции поиска [down].
16.2.1. variable selection strategy
The variable selection strategy lets you specify which variable of Vars is labeled next and is one of:
leftmost — Label the variables in the order they occur in Vars. This is the default.
ff First fail. Label the leftmost variable with smallest domain next, in order to detect infeasibility early. This is often a good strategy when there are small domains for the subsequent variables when a first variable is chosen.
ffc Of the variables with smallest domains, the leftmost one participating in most constraints is labeled next. Applying a constraint has to remove a subtree, so this can be a good strategy.
min Label the leftmost variable whose lower bound is the lowest next. note that this is min/0, different than min/1, which determines solution order and is discussed in the previous section above. This is a good tactic if you’re trying to minimize some global value that is likely to be lower if various variables are (e.g. a minimum cost solution).
max Label the leftmost variable whose upper bound is the highest next. This too is different than max/1. And the advice for min applies to max when trying to maximize a global value.
16.2.2. value order
The value order is one of:
up Try the elements of the chosen variable’s domain in ascending order. This is the default.
down Try the domain elements in descending order.
Obviously, if you’ve got an assymmetric distribution, like we demonstraed in how to label efficiently above, try elements in most common first order.
16.2.3. branching strategy
The branching strategy is one of:
step For each variable X, a choice is made between X = V and X #\= V, where V is determined by the value ordering options. This is the default.
enum For each variable X, a choice is made between X = V_1, X = V_2 etc., for all values V_i of the domain of X. The order is determined by the value ordering options.
bisect For each variable X, a choice is made between X #=< M and X #> M, where M is the midpoint of the domain of X. Choose this option if many variables are selections among a range of integers, a value, rather than one among a set of enumerated values (e.g. percentages, vs a=0, b=1, c=2)
Теперь собственно что такое "сбалансировано", это когда налитая вода не переливается из клеточки в клеточку. Это соответствие исходной упорядоченности элементов. Можно думать, что заполняясь клеточки сохранят форму исходного ландшафта, это значит если была стена, то она может покрыться водой поверх, так, что станет обязательно равна всем своим соседям, или если она не покрытая водой стена…
Рассмотрим балансные ситуации:
-Если клеточку залило, то рядом такие-же или еще выше (вдруг это стены).
-Если клеточка была равна соседней, то она должна быть равна и новой соседней.
-И крайний случай, клеточка не изменила своего значения, и все равно какие у нее были соседи:
%проход по строкам
balns([],[]).
balns([_],[_]).
balns([_,_],[_,_]).
balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :-
blevel(B1,B2,B3,R1,R2,R3),
balns([B2,B3|Tb],[R2,R3|T]).
%из трех строк выбираем по тройке, для создания квадрата 3х3
blevel([],[],[],[],[],[]).
blevel([_],[_],[_],[_],[_],[_]).
blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]).
blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb],
[_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):-
equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]),
blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb],
[U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]).
%одинаков характер элементов в квадратах,
%значение может сохраняется или быть менее равно соседей
equ(C0,_,C,[U,L,R,D]):-C#>C0,C#=<U,C#=<R,C#=<L,C#=<D.
equ(_,[],_,[]).
equ(C0,[C0|T0],C,[C|T]):-equ(C0,T0,C,T).
equ(C,_,C1,_):-C1#=C.Вот так можно перенести в программу свое отношение к задаче. Мне не алгоритм решения необходимо продумать, важно предоставить корректное описание результата, задать правильно все начальные ограничения (множества значений). Этот подход можно просто "миксовать" с обычным поиском с возвратом и рекурсией присущей Прологу. Это способ формулировать еще более декларативные программы, чем используя классические методы Пролога.
Приведу полученное решение, с набором тестов:
:- use_module(library(clpfd)).
checks(X0,X2):-
flatten(X0,FX),
max_list(FX,Max),checks(Max,X0,X2),
balns(X0,X2),
flatten(X2,FX2),
labeling([down],FX2).
checks(_,[],[]).
checks(_,[X],[X]).
checks(_,[X,Z],[X,Z]).
checks(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,
R21 in R2..V,
checks(V,[R21,R3|T],St).
checks(V,[R1,R2,R3|T],[R1|St]) :- checks(V,R2,R21),checks(V,[R21,R3|T],St).
%проход по строкам
balns([],[]).
balns([_],[_]).
balns([_,_],[_,_]).
balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :-
blevel(B1,B2,B3,R1,R2,R3),
balns([B2,B3|Tb],[R2,R3|T]).
%из трех строк выбираем по тройке, для создания квадрата 3х3
blevel([],[],[],[],[],[]).
blevel([_],[_],[_],[_],[_],[_]).
blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]).
blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb],
[_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):-
equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]),
blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb],
[U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]).
%одинаков характер элементов в квадратах,
%значение может сохраняется или быть менее равно соседей
equ(C0,_,C,[U,L,R,D]):-C#>C0,C#=<U,C#=<R,C#=<L,C#=<D.
equ(_,[],_,[]).
equ(C0,[C0|T0],C,[C|T]):-equ(C0,T0,C,T).
equ(C,_,C1,_):-C1#=C.
diffall(L0,L2,S):-
flatten(L0,F0),sum_list(F0,S0),
flatten(L2,F2),sum_list(F2,S2),
S is S2-S0.
sums(X,S):-checks(X,X1),!,diffall(X,X1,S).
%unit-tests framework
assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp).
:-assert_are_equal(sums([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]],4),true).
:-assert_are_equal(sums([[1,3,3,1,3,2],[3,2,1,3,2,3],[3,3,3,2,3,1]],4),true).
:-assert_are_equal(sums([[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]],14),true).
:-assert_are_equal(sums([[2,3,4],[5,6,7],[8,9,10],[11,12,13],[14,15,16]],0),true).
:-assert_are_equal(sums([[18,2,3],[4,5,6],[7,8,9]],0),true).
:-assert_are_equal(sums([[3,5,5],[5,4,5],[5,5,5]],1),true).
:-assert_are_equal(sums([[5,5,5,1],[5,1,1,5],[5,1,5,5],[5,2,5,8]],3),true).
:-assert_are_equal(sums([[2,2,2],[2,1,2],[2,1,2],[2,1,2]],0),true).
:-assert_are_equal(sums([[17,2,3,4,5,6,7,8,9,10]],0),true).
:-assert_are_equal(sums([[9,9,9,9,9],[9,2,1,2,9],[9,2,8,2,9],[9,2,3,2,9],[9,9,9,9,9]],57),true).
:-assert_are_equal(sums([[78,16,94,36],[87,93,50,22],[63,28,91,60],[64,27,41,27],[73,37,12,69],[68,30,83,31],[63,24,68,36]],44),true).
:-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true).
:-assert_are_equal(sums([[5,5,5],[5,1,5],[5,5,5]],4),true).
:-assert_are_equal(sums([[5,5,5],[5,1,5],[5,1000,6]],4),true).
:-assert_are_equal(sums([[5,8,7,7],[5,2,1,5],[7,1,7,1],[8,9,6,9],[9,8,9,9]],12),true).
:-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true).
:-assert_are_equal(sums([[3,3,4,4,4,2],[3,1,3,2,1,4],[7,3,1,6,4,1]],5),true).
:-assert_are_equal(sums([[14,17,18,16,14,16],[17,3,10,2,3,8],[11,10,4,7,1,7],[13,7,2,9,8,10],[13,1,3,4,8,6],[20,3,3,9,10,8]],25),true).
:-assert_are_equal(sums([[14,17,12,13,20,14],[12,10,5,8,9,5],[16,1,4,7,2,1],[17,4,3,1,7,2],[16,6,5,8,7,6],[17,10,4,8,5,6]],12),true).:-assert_are_equal(sums([[13,16,15,18,15,15],[14,1,8,9,7,9],[19,5,4,2,5,10],[13,1,7,9,10,3],[17,7,5,10,6,1],[15,9,8,2,8,3]],36),true).
:-assert_are_equal(sums([[18,13,13,17,12,11],[17,2,6,10,5,10],[11,10,2,8,8,2],[12,6,10,8,8,7],[18,4,7,6,7,4],[20,5,9,2,3,10]],18),true).
:-assert_are_equal(sums([[14,20,11,19,19,16],[11,10,7,4,9,6],[17,2,2,6,10,9],[15,9,2,1,4,1],[15,5,5,5,8,7],[14,2,8,6,10,7]],11),true).
:-assert_are_equal(sums([[19383,10886,12777,16915,17793,18335,15386,10492,16649,11421],[12362,27,8690,59,7763,3926,540,3426,9172,5736],[15211,5368,2567,6429,5782,1530,2862,5123,4067,3135],[13929,9802,4022,3058,3069,8167,1393,8456,5011,8042],[16229,7373,4421,4919,3784,8537,5198,4324,8315,4370],[16413,3526,6091,8980,9956,1873,6862,9170,6996,7281],[12305,925,7084,6327,336,6505,846,1729,1313,5857],[16124,3895,9582,545,8814,3367,5434,364,4043,3750],[11087,6808,7276,7178,5788,3584,5403,2651,2754,2399],[19932,5060,9676,3368,7739,12,6226,8586,8094,7539]],79058),true).
:-assert_are_equal(sums([[10795,10570,11434,10378,17467,16601,10097,12902,13317,10492],[16652,756,7301,280,4286,9441,3865,9689,8444,6619],[18440,4729,8031,8117,8097,5771,4481,675,709,8927],[14567,7856,9497,2353,4586,6965,5306,4683,6219,8624],[11528,2871,5732,8829,9503,19,8270,3368,9708,6715],[16340,8149,7796,723,2618,2245,2846,3451,2921,3555],[12379,7488,7764,8228,9841,2350,5193,1500,7034,7764],[10124,4914,6987,5856,3743,6491,2227,8365,9859,1936],[11432,2551,6437,9228,3275,5407,1474,6121,8858,4395],[16029,1237,8235,3793,5818,4428,6143,1011,5928,9529]],68900),true).
:-assert_are_equal(sums([[18776,12404,14443,15763,14613,14538,18606,16840,12904,14818],[15128,688,7369,7917,9917,6996,3324,7743,9470,2183],[18490,5499,9772,6725,5644,5590,7505,8139,2954,9786],[17669,8082,8542,8464,197,9507,9355,8804,6348,8611],[13622,7828,9299,7343,5746,5568,4340,5422,3311,3810],[17605,1801,5661,3730,4878,1305,9320,8736,9444,8626],[18522,3465,6708,3416,8282,3258,2924,7637,2062,5624],[12600,2036,3452,1899,9379,5550,7468,71,973,7131],[13881,4930,8933,5894,8660,163,7199,7981,8899,2996],[12959,3773,2813,9668,7190,1095,2926,6466,5084,1340]],61413),true).
:-assert_are_equal(sums([[12090,17684,13376,15542,15936,19107,17445,19756,19179,18418],[16887,9412,3348,2172,1659,2009,2336,5210,6342,7587],[18206,9301,7713,7372,5321,1255,4819,4599,7721,9904],[15939,9811,3940,5667,1705,6228,1127,9150,5984,6658],[13920,9224,2422,7269,1396,4081,5630,84,9292,1972],[17672,3850,7625,5385,1222,9299,6640,6042,3898,713],[12298,6190,524,2590,8209,8581,8819,9336,7732,1155],[15994,8004,379,4769,5273,1776,8850,7255,1860,8142],[15579,5884,1993,3205,7621,9567,2504,613,1961,2754],[11326,4259,8944,8202,3202,3506,6784,2021,2842,868]],89383),true).
:-assert_are_equal(sums([[19528,15189,18872,19908,19958,10498,18036,18808,17753,16248],[13303,3333,2133,1648,2890,9754,7567,1746,368,9529],[14500,8046,3788,9797,6249,6990,3303,3033,5363,2497],[10253,4892,7686,9125,1152,3996,5975,9188,9157,3729],[15436,2460,3414,3921,460,6304,28,8027,8050,6748],[17556,8902,4794,7697,8699,1043,1039,2002,428,6403],[14500,681,7647,8538,6159,5151,2535,2134,4339,1692],[12215,6127,504,5629,49,964,8285,6429,5343,6335],[13177,2900,5238,7971,6949,289,5367,7988,2292,5795],[10743,3144,2829,8390,1682,5340,3541,569,3826,4232]],100439),true).Это были тесты с сайта, только первые 30 штук. Результат отличный, задача решается, да еще и быстро, все времена до одной секунды.
Как вывод
Декларативное программирование предполагает детальную формализацию задачи, а решатель будет искать наиэффективнейшее решение, которое удовлетворит условиям.
Немного углубившись в тему можно открыть minizinc, язык программирования, в котором заложена только эта парадигма. Сформулировали множество значений, указали ограничения, и вуаля, ответ. Они решают судоку, задачи раскраски карт, составление планов работ, resource problems, Scheduling. Предлагаю тренироваться...
Комментарии (68)
go-prolog Автор
04.01.2019 15:10Вы правы, тесты беру с сайта, следующий был 50*50 и его решение не оканчивается.
Был бы рад увидеть более совершенное и лаконичное решение...mk2
04.01.2019 15:29+1Давайте будем перебирать клетки в порядке возрастания высоты.
Если от клетки, которую мы рассматриваем сейчас, нет пути до края по уже рассмотренным клеткам — мы можем налить в неё сколько-то воды сверх её высоты.
Соответственно, если мы рассмотрели какую-то клетку и при этом от другой рассмотренной появился путь до края(через рассмотренную сейчас клетку) — значит, мы в эту другую можем налить воды до уровня рассмотренной сейчас.
Чтобы сделать это быстро, объединим находящиеся рядом рассмотренные клетки в множества, и для каждого множества будем хранить количество клеток в нём, общую высоту и есть ли сейчас путь из клеток этого множества к краю. Соответственно, множества нужно уметь соединять и быстро вычислять, к какому множеству относится клетка. И обновлять ответ, когда объединяем множество с путем к краю и множество без пути.
Такое называется «система непересекающихся множеств» и есть алгоритм, который обе операции делает почти за константное время.
lair
04.01.2019 16:15Пришлось тесты подкомментировать т.к. не все проходили.
А финальный ваш вариант, кстати, проходит все оригинальные тесты?
Декларативное программирование предполагает детальную формализацию задачи, а решатель будет искать наиэффективнейшее решение, которое удовлетворит условиям.
"наиэффективнейшее" по каким критериям?
Вот, например, банальный вопрос: какова вычислительная сложность вашего решения?
go-prolog Автор
04.01.2019 16:41Я показал два решения, первое «генерировать и проверить» не проходило все приведенные тесты, второе с использованием CLP проходит все плюс еще приведенные…
В данном случае, мне интересна «вычислительная сложность», но хочу обратить внимание на «познавательную сложность». Какая задача труднее, сформулировать решения прибегая к алгоритму или описав формулировку?lair
04.01.2019 17:03В данном случае, мне интересна «вычислительная сложность»,
Вот и мне интересна. Какая вычислительная сложность у вашего решения? И вы так и не ответили: по каким критериям эффективности выбирается решение решателем?
Какая задача труднее, сформулировать решения прибегая к алгоритму или описав формулировку?
В случае задач "из реального мира" — одинаково, потому что на описание формулировки уходят недели и месяцы.
Но отдельная проблема в том, что ваше "полученное решение" не удовлетворяет "просто опишите формулировку": в нем не видно, собственно, формулировки задачи; да и вообще понять, что там происходит, очень и очень непросто. Так что "декларативность" оказалась ложной.
go-prolog Автор
04.01.2019 17:44Спасибо, у вас замечания всегда очень критические, всех ответов не имею.
А как будете доказывать:
Так что "декларативность" оказалась ложной.
Предоставьте алгоритм, покажите его сложность, давайте сравнивать решения...
lair
05.01.2019 00:19Спасибо, у вас замечания всегда очень критические, всех ответов не имею.
Ну то есть на самом деле ваше утверждение "решатель будет искать наиэффективнейшее решение, которое удовлетворит условиям" ни на чем не основано?
А как будете доказывать:
Так что "декларативность" оказалась ложной.
А легко.
Возьмем описание задачи:
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Возьмем ваше решение:
checks(X0,X2):- flatten(X0,FX), max_list(FX,Max),checks(Max,X0,X2), balns(X0,X2), flatten(X2,FX2), labeling([down],FX2). checks(_,[],[]). checks(_,[X],[X]). checks(_,[X,Z],[X,Z]). checks(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!, R21 in R2..V, checks(V,[R21,R3|T],St). checks(V,[R1,R2,R3|T],[R1|St]) :- checks(V,R2,R21),checks(V,[R21,R3|T],St). balns([],[]). balns([_],[_]). balns([_,_],[_,_]). balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :- blevel(B1,B2,B3,R1,R2,R3), balns([B2,B3|Tb],[R2,R3|T]). blevel([],[],[],[],[],[]). blevel([_],[_],[_],[_],[_],[_]). blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]). blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb], [_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):- equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]), blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb], [U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]). equ(C0,_,C,[U,L,R,D]):-C#>C0,C#=<U,C#=<R,C#=<L,C#=<D. equ(_,[],_,[]). equ(C0,[C0|T0],C,[C|T]):-equ(C0,T0,C,T). equ(C,_,C1,_):-C1#=C. diffall(L0,L2,S):- flatten(L0,F0),sum_list(F0,S0), flatten(L2,F2),sum_list(F2,S2), S is S2-S0. sums(X,S):-checks(X,X1),!,diffall(X,X1,S).
А теперь покажите мне, какая часть вашего решения является формулировкой задачи?
go-prolog Автор
05.01.2019 00:56Так я говорю о том, что если нам сейчас предоставят «блок схему» с алгоритмом, то отклонение задачи от ее формулировки будет еще более заметно.
lair
05.01.2019 01:00Так я говорю о том, что если нам сейчас предоставят «блок схему» с алгоритмом, то отклонение задачи от ее формулировки будет еще более заметно.
Более, чем та условная бесконечность, которая представлена в вашем коде? Я вообще не могу восстановить по нему исходную задачу.
go-prolog Автор
05.01.2019 01:15А мне кажется, что такие программы, показывают математическую суть задачи, у каждой неизвестной осталось указать квантор *существования* или *всеобщности*, заменить ":-" на «следование» и получаем математическую модель.
И мне интересно, как же будет выглядеть императивное решение этой задачи?, не так ли будет понятно как быстрая сортировка?lair
05.01.2019 01:18А мне кажется, что такие программы, показывают математическую суть задачи
Конкретно ваша программа не показывает математическую суть данной задачи. Более того, в самой формулировке задания нет математической модели, следовательно, ее вывод — это и есть этап "формулирования решения".
И мне интересно, как же будет выглядеть императивное решение этой задачи?
Я над своим вариантом размышляю, но на том же leetcode есть множество решений в обсуждении этой задачи.
не так ли будет понятно как быстрая сортировка?
Быстрая сортировка как раз прекрасно понятна в императивных языках.
go-prolog Автор
05.01.2019 01:25Продолжу про быструю сортировку, по-моему «понятно», это когда можно взять и записать этот алгоритм по памяти, проведите эксперимент, запишите сюда быструю сортировку «по-памяти», реально ли ее восстановить?
А быструю сортировку в Эрланге еще раз продемонстрирую:
qsort([])->[];
qsort([H|T])->qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].lair
05.01.2019 01:40А быструю сортировку в Эрланге еще раз продемонстрирую:
Вы знаете, да, что этот решение не выполняет одного из основных критериев быстрой сортировки — константного расхода памяти?
(ну и я бы, конечно, отдельно поинтересовался тем, какая же конкретно вычислительная сложность у этого решения)
go-prolog Автор
05.01.2019 01:57А мне остается поинтересоваться, а как же «понятный» алгоритм быстрой сортировки сейчас вот записать, восстановить из памяти…
Понятность и вычислительная сложность конечно разные понятия, но когда они приближаются, тогда решение «хорошее».lair
05.01.2019 02:02А мне остается поинтересоваться, а как же «понятный» алгоритм быстрой сортировки сейчас вот записать, восстановить из памяти…
- Выберите пивот.
- Поместите все, что меньше пивота, до пивота, а все, что больше пивота — после пивота.
- Повторите на участке до пивота
- Повторите на участке после пивота
Сложности начинаются тогда, когда вы начинаете учитывать граничные случаи.
Понятность и вычислительная сложность конечно разные понятия, но когда они приближаются, тогда решение «хорошее».
Эти две метрики не могут "приблизиться", у них разные единицы измерения. Точнее говоря, вторую можно измерить, а первая субъективна.
Так все-таки, какая вычислительная сложность у приведенной вами реализации быстрой сортировки, и можно ли ее, собственно, называть быстрой сортировкой?
go-prolog Автор
05.01.2019 02:08- Выберите пивот.
Тут надо бы поподробнее, не все еще понятно.
А записать в программу его будет тоже не просто..
Это же, как ассемблер заменили на фортран, что-то стало более понятнее.
И "Эти две метрики", если это метрики, то они имеют числовое выражение.
lair
05.01.2019 02:09Тут надо бы поподробнее, не все еще понятно.
Это алгоритм, он, знаете ли, такой. Все остальное — детали имплементации, и именно в них таится дьявол. Так вас алгоритм интересует, или точная имплементация?
go-prolog Автор
05.01.2019 02:13А алгоритм не должен обладать свойством «повторяемости», а от выбора этого пивота будем получать разные «неповторимые» реализации сложности, когда же кончается алгоритм?
lair
05.01.2019 02:15Ну так у quick sort и больше одной реализации с разными гарантиями сложности. Для вас это новость?
Вы думали, это простой алгоритм? Так нет.
go-prolog Автор
05.01.2019 02:18Так может, то что я написал, на Эрланге, тот же самый алгоритм, он же такой — с «разными гарантиями»?
lair
05.01.2019 02:23Так может, то что я написал, на Эрланге, тот же самый алгоритм, он же такой — с «разными гарантиями»?
Ну так покажите это. Посчитайте вычислительную сложность, посчитайте сложность по памяти — вот и узнаем, помещается ли он в общие гарантии quick sort, или нет.
(на всякий случай, напомню: вычислительная сложность quick sort n log n в среднем и квадратичная в худшем случае, требования по памяти на каждом уровне рекурсии — константа; есть вариант с отдельным буфером равным по размеру сортируемой области)
go-prolog Автор
05.01.2019 02:31Вот, а я нашел вот такое свойство алгоритмов:
детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
На каждом рекурсивном вызове Эрланга, список разделяется на два других, меньших, а входной после выхода из функции пропадает далее сортируються меньшие списки, так что константность памяти сохранится. А сложность n*log(n) сохраняется, так это выражение того-же самого принципа быстрой сортировки.
lair
05.01.2019 02:38список разделяется на два других, меньших
Что значит "список разделяется"? Какова вычислительная сложность и сложность по памяти для этой операции?
входной после выхода из функции пропадает
Что значит "пропадает"? Какова вычислительная сложность этой операции?
Более того, даже по этому описанию у вас не константа: в момент выполнения любого уровня рекурсии у вас задействовано как минимум O(n) дополнительной памяти — это та память, куда вы отобрали два меньших подсписка. И она удерживается, пока вы выполняете все вызовы рекурсии — а те тоже требуют дополнительную память.
Как вообще устроены списки в Эрланге с точки зрения модели операций? В частности, какова сложность операции "добавить один список в конец другого списка" (не зря же там
++вместо|)?go-prolog Автор
05.01.2019 02:46Списки рекурсивны и состоят из головы и хвоста, который список.
Операция "конкатенации", должна быть n сложности,
и генераторы списков тоже добавляют свое n.lair
05.01.2019 02:49Это по операциям (хотя вы уже радикально превысили константу, которая в quick sort, но мы же в рамках О-большого, так что закроем на это глаза). Меня больше волнует память. Вы, например, знаете, что
++создает еще одну копию? А сколько копий создается в list comprehension?go-prolog Автор
05.01.2019 02:59Каждый генератор сделает один список, который поступит на следующий уровень вызова, и конкатенация должна быть оптимизирована, это не просто новый список, это хотя бы второй список не обработан, а превращен в хвост…
lair
05.01.2019 11:24Ох. Ну вот давайте на примере. Вот входной список:
[8 7 6 5 4 3 2 1 9]. На него выделено kn памяти (где n равно 9, и, будем честными, k раза в два больше, чем если бы вы работали с массивами, как в оригинальной сортировке). Это "внешняя" по отношению к вызову память, мы ей не управляем, и ее не считаем.
qsort([H|T]) -> qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].
[H|T] = [8 7 6 5 4 3 2 1 9]
Здесь выделено констатное количество памяти на
H, аTпереиспользовано от входящего списка (слава иммутабельности).
[X||X<-T,X<H]
Результатом этого выражения будет
[7 6 5 4 3 2 1], это новый список (потому что его хвост отличается от хвостаT). Это еще минимум k(n-2) выделенной памяти (я пишу "минимум", потому что в реальности там рекурсивная функция, у которой свои накладные расходы еще есть).
qsort([7 6 5 4 3 2 1])
Результатом этого выражения будет
[1 2 3 4 5 6 7], и это ещеk(n-2)используемой памяти. Будем добрыми и предположим, что менеджер памяти Эрланга смог понять, что предыдущий список более не будет использоваться, деаллоцировал блок, и положил этот список на его место. Это добавило нам операций, но сократило добавленную память до одного k(n-2).
qsort([X||X<-T,X>=H])
Аналогично предыдущим шагам, мы получим здесь
[9]и еще k потраченной памяти (если мы добрые). Суммарные дополнительные накладные расходы по памяти, предсказуемо, k(n-1).
[8|[9]]
Выделили еще k памяти, потому что надо преобразовать
8в голову списка.
[1 2 3 4 5 6 7]++[8 9]
Здесь, в строгом соответствии с документацией, будет создана копия левого списка, на что выделено еще k(n-2) памяти.
Итого: накладные расходы на одном уровне — 2k(n-1). Это ну никак не константа, которая у типовой реализации, и даже не одинарный буфер, который у реализации с буфером. А дальше у вас начинается рекурсия, которая еще добавит вам расходов.
Иными словами, это решение ну никак не влезает в границы, которые у quick sort… то есть это не quick sort. Что, в общем-то, ожидаемо.
gorodnev
05.01.2019 04:14Есть целый класс алгоритмов и быстрая сортировка — один из самых ярких представителей этого класса. Повторяемость вполне себе гарантирована — алгоритм остановится, когда будет обработан/отсортирован весь алгоритм.
PS: А, вообще, за пролог спасибо!
go-prolog Автор
05.01.2019 02:40-1- Поместите все, что меньше пивота, до пивота, а все, что больше пивота — после пивота.
Не понятно в этой записи, а что с самим пивотом происходит, он на месте остался?
lair
05.01.2019 02:42Все, что меньше пивота — до пивота, все, что больше пивота — после пивота. Следовательно, пивот после этой операции должен быть в том месте, где это условие выполняется.
go-prolog Автор
05.01.2019 02:50Тогда, следовало бы писать:
разместите элементы списка так, чтобы пивот оказался на том месте в массиве, что бы все меньшие были слева, а большие справа.
Или, еще точнее:
нужно обменивать между собой элементы справа и слева, до тех пор, пока два индекса справа и слева не встретятся…lair
05.01.2019 10:52Тогда, следовало бы писать:
разместите элементы списка так, чтобы пивот оказался на том месте в массиве, что бы все меньшие были слева, а большие справа.Следовало бы писать "переместите элементы массива таким образом, чтобы все элементы, меньшие пивота, были слева от пивота, а все большие — справа".
Или, еще точнее:
нужно обменивать между собой элементы справа и слева, до тех пор, пока два индекса справа и слева не встретятся…А вот это — не "точнее", потому что "слева и справа" от чего? Я, конечно, понимаю, что вы намекаете на Хоаровскую схему выделения пивота, но, во-первых, она не единственная, а во-вторых, там еще есть опущенные вами нюансы.
go-prolog Автор
05.01.2019 13:12Это меня и интересует, много нюансов этого «алгоритма» упускаем, приводя его, а ведь алгоритм «должен быть» детерминирован. Когда же его можно назвать «быстрой сортировкой», если даже действия приведены не все, где операция swap().
Тут wiki.haskell.org/Introduction#Quicksort_in_Haskell — пишут о выражении быстрой сортировки, и это она же.
Для декларативного выражения, стоит вводить другой термин «схема», «принцип», а алгоритм это строгость и однозначность, вы ее не показали указав четыре шага.lair
05.01.2019 13:22Это меня и интересует, много нюансов этого «алгоритма» упускаем, приводя его, а ведь алгоритм «должен быть» детерминирован.
Ну так он детерминирован. Его результат определен.
Когда же его можно назвать «быстрой сортировкой», если даже действия приведены не все, где операция swap().
А зачем ее приводить? Для этого псевдокод есть.
Тут wiki.haskell.org/Introduction#Quicksort_in_Haskell — пишут о выражении быстрой сортировки, и это она же.
Нет, не она же. Сравните с "true quicksort" по той же ссылке.
Для декларативного выражения, стоит вводить другой термин «схема», «принцип»,
Нет, не стоит. Зачем?
а алгоритм это строгость и однозначность
Понятие "однозначность" субъективно. В частности, вы никогда не видели алгоритмов, в которых сказано "отсортируйте"?
go-prolog Автор
07.01.2019 00:15Хочу уточнить свой интерес, мне хотелось понять, а как именно у нас сохранен "в голове" тот алгоритм, или описание самой "быстрой сортировки". Мне интересно узнать, а как мы себе помним, что такое алгоритм.
Это последовательность императивность: 1,2,3,4:
- Выберите пивот.
- Поместите все, что меньше пивота, до пивота, а все, что больше пивота — после пивота.
- Повторите на участке до пивота
- Повторите на участке после пивота
Или мысль статична, декларативна:
Если у входного списка есть пивот и хвост [H|T], то
отсортированы он будет если ->
(отсортированы все элементы из Т меньшие пивота H) плюс сам пивот
плюс (отсортированы все большие пивота)
qsort()++[H]++qsort()
Ну, И Пустой [] список всегда отсортирован.
Это как вопрос, о сути субъективности, какой именно способ используем мы (мы как люди, наш мозг) для хранения этого алгоритма быстрой сортировки? )
lair
07.01.2019 01:56мне хотелось понять, а как именно у нас сохранен "в голове" тот алгоритм, или описание самой "быстрой сортировки".
Я не могу сказать за всех людей, но я помню алгоритмы в виде последовательности. Потому что они по определению последовательность, и дают их в виде последовательности, и курсы по анализу алгоритмов оперируют последовательностями. Последовательность — это то, по чему можно определять интересующие нас характеристики алгоритмов (а это, сразу после корректности, метрики производительности).
Если у входного списка есть пивот и хвост [H|T], то
отсортированы он будет еслиМассив считается отсортированным, если каждый последующий его элемент не меньше, чем текущий. Вот и всё. Только это не имеет отношения к алгоритмам.
Кстати,
H— это не пивот, это голова. Просто вы выбрали ту стратегию, где за пивот выбирается нулевой элемент (и это, заметим, не лучшая стратегия).go-prolog Автор
07.01.2019 02:07Это тот признак удобнее, понятнее, нам не нужно доказывать таблицу умножения, теорему Пифагора, они и так понятны, они истинны. Какие расчеты там делал Пифагор, мы не интересуемся, также как и Хоар предложил "делить на меньшие и большие", вот основная идея, в рекурсивности и разделении, если делить большую задачу на мелкие, получаем в среднем сложность логарифма — это основной принцип этого быстрого (так сказать) алгоритма.
Другой алгоритм сопоставимый с быстрой, это алгоритм, звучит вот так:
Не делить список на меньшие и большие, а делить РОВНО пополам, а потомmergeсливать отсортированные две части.
Это тоже алгоритм сортировки, и они очень похожи между собой. Но сложность последнего точно ровна log(n). И я только что не излагал последовательность сортировки слияниями))
Так какой способ представления, более доступен, понятен, и в каких областях? почему все понятно с SQL, HTML? а с алгоритмом в программе не так? Не про производительность, вычислительную сложность языка SQL, интересуются, людей привлекает абстракция, она заменяет собой большое количество деталей, о которых разработчику знать не нужно при решении задач...lair
07.01.2019 02:20нам не нужно доказывать таблицу умножения, теорему Пифагора, они и так понятны, они истинны
Я не знаю, кто эти "вы", кому не нужно доказывать теорему Пифагора. Меня в школе заставляли доказывать.
если делить большую задачу на мелкие, получаем в среднем сложность логарифма
Конечно, нет. Если делить большую задачу на мелкие, сложность в среднем не меняется. Она меняется только тогда, когда мы делим задачу определенным образом.
это основной принцип этого быстрого (так сказать) алгоритма.
Неа. Это вам кажется, что это его основной принцип. Но нет.
делить РОВНО пополам, а потом сливать отсортированные две части. Это тоже алгоритм сортировки
Это не алгоритм сортировки, потому что нет гарантии, что результат будет отсортирован. Потому что не определен термин "сливать".
Но сложность последнего точно ровна log(n)
Нет ни одного алгоритма сортировки (общего вида, конечно же) со сложностью log(n).
почему все понятно с SQL
А с ним "все понятно"? Или вы просто никогда не сталкивались со сложными его случаями?
Не про производительность, вычислительную сложность языка SQL, интересуются
Кто как. Меня вот сильно волнует производительность конкретной инструкции на SQL, когда я это строю. Потому что эта производительность в итоге влияет на то, могу я это выпустить в производство или нет.
большое количество деталей, о которых разработчику знать не нужно при решении задач...
Кому-то не надо. Кому-то надо. В этом как раз и крупное различие.
Так какой способ представления, более доступен, понятен, и в каких областях?
Это риторический вопрос, на него (очевидно) нет универсального ответа.
go-prolog Автор
07.01.2019 02:29-1Очевидно у меня травма )) детства, но я читал в этой книге (Мейер, Бертран; Бодуен, Клод Методы программирования В 2 томах 1982г) вот такое:
lair
07.01.2019 02:30Ну и что?
go-prolog Автор
07.01.2019 02:34Принцип описанный тут целиком отображен в программе на Эрланге — она и была быстрой сортировкой, в которой основа разделяй и рекурсивно сортируй ))
lair
07.01.2019 02:36Нет. Программа на Эрланге не реорганизует массив, она создает новый. И это ключевое отличие от "настоящего" quick sort.
Кстати, "разделяй и рекурсивно сортируй" — это заодно и сортировка слиянием, так что если вы хотите говорить именно о быстрой сортировке, вам нужен дополнительный определяющий признак.
go-prolog Автор
07.01.2019 02:52почему все понятно с SQL
А с ним "все понятно"? Или вы просто никогда не сталкивались со сложными его случаями?
Для "сложных случаев" стандарт SQL постоянно расширяют… И не решив сложный запрос переписывать на for в for-е, никто не берется.
Получилось основное отличие императивной мысли от декларативной в "реорганизует" в возможности делать swap(). Тут была статья о реализации сортировки слияниями на лентах, от Фон Неймана, там при отсутствие возможности изменять значения на ленте, переписывали всегда все значения на промежуточные ленты.
lair
07.01.2019 02:58+1Для "сложных случаев" стандарт SQL постоянно расширяют…
И что, остается "все понятно" после расширений?
Получилось основное отличие императивной мысли от декларативной в "реорганизует" в возможности делать swap().
Нет, совсем не в этом. Нет никакой проблемы записать перемену положений.
Другое дело, что те примеры, которые вы выдаете за "декларативную запись quick sort", ей не являются, вот и все.
Тут была статья о реализации сортировки слияниями на лентах, от Фон Неймана, там при отсутствие возможности изменять значения на ленте, переписывали всегда все значения на промежуточные ленты.
Эм. А вы точно вообще в курсе различий между сортировкой слиянием и быстрой сортировкой?
Начнем, что ли, с банального вопроса: какая вычислительная сложность у сортировки слиянием, и какая — у быстрой сортировки?
go-prolog Автор
07.01.2019 03:26Если это важно то вот, привожу из Википедии:
Время работы алгоритма порядка O(n log n) при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка O(n log n), но только для среднего случая). Расход памяти выше, чем для быстрой сортировки, при намного более благоприятном паттерне выделения памяти — возможно выделение одного региона памяти с самого начала и отсутствие выделения при дальнейшем исполнении.
У нас понятие "алгоритма" может быть независимо от исполнителя, механически можно решать эту задачу, карандашом. Как, там было, "имплементации" присуща память и ее расход, не зря у машины Тьюринга бесконечная лента.
lair
07.01.2019 03:33Важно не из википедии, важно из головы.
У нас понятие "алгоритма" может быть независимо от исполнителя, механически можно решать эту задачу, карандашом.
Ну да. Но для него все равно будут те же значения вычислительной сложности, что и для другого исполнителя, потому что вычислительная сложность считается в операциях.
Вот привели вы цитату из википедии, хорошо. Что из нее следует — mergesort лучше quicksort, или хуже? Когда надо применять один, а когда — другой?
И есть ли декларативная запись, содержащая ответы на эти вопросы? Или хотя бы просто позволяющая легко отличить один из этих алгоритмов от другого?
go-prolog Автор
07.01.2019 03:42По принципу слияний видно, что деление входного списка происходит пополам, что приведет к рекурсивным вызовам глубины log(n) вне зависимости от данных,
а для быстрой сортировки нужно учитывать, что "неудачный" пивот или отсортированный входной массив заставят ее углубляться n раз.
В общем эти
труслияния можно представить похожим декларативным выражением на Эрланге:
msort([])->[]; msort(X)->{L,R}=split(X), merg(msort(L),msort(R)).lair
07.01.2019 03:46По принципу слияний видно, что деление входного списка происходит пополам, что приведет к рекурсивным вызовам глубины log(n) вне зависимости от данных,
а для быстрой сортировки нужно учитывать, что "неудачный" пивот или отсортированный входной массив заставят ее углубляться n раз.Ну то есть quicksort хуже, чем mergesort, и надо всегда использовать mergesort?
В общем эти тру слияния можно представить похожим декларативным выражением на Эрланге:
Неа, нельзя. Я могу написать такие имплементации
splitиmerge, которые сделают из этого не merge sort, а quick sort. Или вообще случайный фильтр. Или сумматор. Или неизвестно что.
А еще это выражение ничем не отличается от сугубо императивного алгоритма:
- разбейте L на L и R
- отсортируйте L
- отсортируйте R
- слейте L и R
Так почему вы утверждаете, что оно декларативно, а не императивно?
go-prolog Автор
07.01.2019 03:55А еще это выражение ничем не отличается от сугубо императивного алгоритма:
Спасибо, это я и пробую описать, мое описание можно дополнить и будет рабочая программа:
split([])->{[],[]}; split([A])->{[A],[]}; split([A,B|T])->{L,R}=split(T),{[A|L],[B|R]}. Ну и merg: merg([],[])->[]; merg(X,[])->X; merg([],X)->X; merg([A|T],[B|T1]) when A<B->[A|merg(T,[B|T1])]; merg([A|T],[B|T1])-> [B|merg([A|T],T1)].
Сколько придется думать, чтобы реализовать "алгоритм" слияния на императивном языке?
Разве так не проще?lair
07.01.2019 04:04+1Нет, не проще. Я из вашей "рабочей программы" не понимаю как работает
split. А количество рекурсий, которые вы ввели, затрудняет анализ сложности алгоритма до невозможности.
merge(L,R): until L.atEnd and R.atEnd: if R.atEnd: yield L.pop() continue if L.atEnd: yield R.pop() continue if L.current < R.current: yield L.current else: yield R.current L.moveNext() R.moveNext()go-prolog Автор
07.01.2019 04:13-1Ну хорошо, вот об этом понимаю и речь, взгляд на алгоритм сортировки слияниями выраженный на С++ мне объяснит еще меньше, не знаю как кому…
Ну и, спасибо за беседу ))lair
07.01.2019 04:15взгляд на алгоритм сортировки слияниями выраженный на С++ мне объяснит еще меньше, не знаю как кому…
Вот именно поэтому в курсах обычно используют псевдокод. Если вы не умеете его читать...
go-prolog Автор
07.01.2019 04:19Ну давайте доводить псевдо-Питон до конца,
как там выглядят sort, split?lair
07.01.2019 11:41А в них нет смысла, весь алгоритм прекрасно выражается одной процедурой.
mergesort(X): N = X.length L = mergesort(X[0:N/2]) R = mergesort(X[N/2:N]) until L.atEnd and R.atEnd: if R.atEnd: yield L.pop() continue if L.atEnd: yield R.pop() continue if L.current < R.current: yield L.current else: yield R.current L.moveNext() R.moveNext()
Ну и я на всякий случай напомню вам, что ваша реализация на Эрланге — не декларативна.
lair
05.01.2019 02:11константного расхода памяти?
Тут я, конечно, не прав: надо еще добавить расход памяти на рекурсию, поэтому логарифмический после оптимизации. Правильнее сказать: константный на каждом уровне.
gorodnev
05.01.2019 04:09Подозреваю, что Ваше решение обладает той же проблемой, что и такое же решение на haskell
go-prolog Автор
05.01.2019 04:24Точно, можно сказать, что декларативная программа, выражает не алгоритм, а некий «принцип» быстрой сортировки, а детали выполнения зависят от решателя.
go-prolog Автор
05.01.2019 01:36Последовал совету, вот приведу решение, которое в комментариях приводят:
import heapq class Solution: def trapRainWater(self, heightMap): """ :type heightMap: List[List[int]] :rtype: int """ rows = len(heightMap) if rows < 3: return 0 cols = len(heightMap[0]) if cols < 3: return 0 heap = [] for i in range(rows): for j in (0, cols-1): heap.append((heightMap[i][j], i, j)) heightMap[i][j] = None for j in range(1, cols-1): for i in (0, rows-1): heap.append((heightMap[i][j], i, j)) heightMap[i][j] = None heapq.heapify(heap) water = 0 while heap: # iterate while heap has elements max_height, i, j = heapq.heappop(heap) for x, y in [(i, j + 1), (i + 1, j), (i, j - 1), (i - 1, j)]: if (0 <= x < rows) and (0 <= y < cols): height = heightMap[x][y] if height is None: continue if height >= max_height: heapq.heappush(heap, (height, x, y)) else: water += max_height - height heapq.heappush(heap, (max_height, x, y)) heightMap[x][y] = None return water
Это формализация, да тут одни heappush()… это разве понятно?
BMBM
07.01.2019 02:59Немного оффтоп.
Использование пролог в реальных системах натыкается на 2 основных проблемы:
1 нельзя предугадать дерево поиска решения
2 можно попасть в класс задач, которые эффективно вообще не решаются.
В связи с 1 к сожалению для реальных объемов данных шансов получить прогнозируемый ответ нет.
В связи с 2 есть интеграция пролога с правильными решателями?go-prolog Автор
07.01.2019 03:03К решателям можно относить вот такие
clp(fd) is one of several constraint solvers available in SWI-Prolog. The others are clp(b), clp(qr) and CHR. clp(b) handles booleans. clp(qr) handles rationals and reals. CHR approaches constraint programming differently, using rewrite rules.
А управление выводом доступно, это разная формулировка задачи...
mk2
Простите, «быстро»? Тут у вас максимальный тест — 10*10. А пробовали ли вы сгенерировать тест хотя бы 110*110, как написано в условии, и запустить на нем?
Хорошее решение такой задачи вообще должно выполняться до одной секунды при m*n около 200000, и высотах до 10^9 (дабы не требовалась длинная арифметика). И то потому что я пока не вижу, как выбросить сортировку. Без неё можно и до миллиона добраться.
Так что универсальный решатель зачастую не сможет эффективно найти решение, несмотря на ограничения. Конечно, можно попробовать решить им задачу, для которой вы уже сформировали хорошие ограничения, но не можете придумать эффективный алгоритм решения. Но такое работает только на маленьких данных.
go-prolog Автор
Спасибо, давайте еще предложения, охота выразить эту задачу именно без алгоритма
mk2
Без алгоритма — не могу вам помочь, я его уже придумал и написал. ))
А касательно ограничений, тут у нас имеется главное ограничение «мы можем налить в клетку воды до уровня n, если нет путей по другим клеткам с высотой не больше n-1 от данной клетки до края». И при этом высоты жидкости не зависят друг от друга, можно последовательно подбирать.
Осталось придумать, как выразить такое на Прологе?
go-prolog Автор
При представлении входных данных в виде списка из списков выразить понятие «путь» становиться не просто, без индексов очень громоздко.
Можно превратить этот массив в подобие графа и обрабатывать список из связей(переходов) — так реальнее, надо думать…