Хабрахабр

Занимательный пролог #2

Привет, сообщество разработчиков, надо довести дело до конца.

Превратить это в упражнение. В предыдущем моем опусе был вызов показать как можно использовать язык Пролог, да и показать что бы это было забавно.

Попробую продолжить выпендриваться демонстрировать.

Коротко напомню задачу:

Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and ''.
'?' Matches any single character.
'
' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

На сайте, который предоставляет задание есть 1808 тестов, которые сразу увидеть нельзя, нужно написать программу и получить как ошибку очередной тест. Доказать полноту решения не удалось.

Но не может быть все так просто. Хардкорно я получил от него 66 и проверил свое решение — пока все работало.

Зачем было делать так много тестов, хочу проверить дальше...

Попробую переписать данное решение на языке понятном доступном в этой системе (они отражают популярность языков программирования современности).

Итак, выбираю Питон.

Проще говоря, в него встроен механизм унификации и поиска с возвратом. Мощь Пролога в процедуре поиска, корни которой в методах доказательства теорем. Это еще проще говоря сопоставление плюс поиск в глубину по дереву решений.

А Питон это современный Паскаль (что-то уже три языка на букву "П")), писать на нем программы доступно и школьникам.

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

Далее запущу его в систему тестирования, и увижу верен ли был ход(код).

На входе тестируемая строка и шаблон:

def test(st,pat): if st=="" and pat=="": yield True if pat>"" and pat[0]=='*':yield test(st,pat[1:]) if st>"" and pat>"": if st[0]==pat[0] or pat[0]=='?': yield test(st[1:],pat[1:]) if pat[0]=='*':yield test(st[1:],pat) yield False

Вроде получилось очень похоже на реализацию Пролога:

test_pattrn([],[]). test_pattrn([Ch|UnpTail],[Ch|PatTail]):-test_pattrn(UnpTail,PatTail).
test_pattrn([Ch|UnpTail],['?'|PatTail]):-test_pattrn(UnpTail,PatTail).
test_pattrn([Ch|UnpTail],['*'|PatTail]):-test_pattrn(UnpTail,['*'|PatTail]).
test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail).

Пять вариантов решения, иначе ложь.

Но как сделать поиск с возвратом?, для этого использую yield, как его там называют, неоконченные(ленивые) вычисления, замыкание, элемент функционального подхода, подскажите… Он будет возвращать что-то, из чего можно будет выудить следующее решение, но если оно не приведет к правильному ответу, то перейдем на ветку программы со следующим yield, в этом и отличие от return.

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

Вот, тут уже конкретно нужен return:

def run(r): if type(r)==bool: if r==True: return True else: for nr in r: if run(nr):return True return False

Прозрачная формулировка это не быстрая формулировка. Ого, вот это результат, "939 / 1808 test cases passed." и "Status: Time Limit Exceeded".
Именно этого я и ждал, декларативное решение не всегда приводит к эффективной по времени выполнения реализации.

Но, тут результат питона, опробуем открывшийся тест в реализации из первой статьи, и замерим время:

import time
pt=time.time()
print(run(test("babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab","***bba**a*bbba**aab**b")))
print(time.time()-pt)

10963249206543 сек., да-а многовато. Время выполнения Питоном 11.

Усовершенствованный механизм тестирования для Пролога:

%unit-tests framework
assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is Fin-St,writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is Fin-St,writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). :-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true).

И вот такой результат Пролога (запуская не в онлайн-редакторе, локально, на одном железе с предыдущим):

isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,*ab***ba**b*b*aaab*b)->ok:2.208951950073242/sec

Похоже я плохо пользуюсь питоном ((, надо усовершенствовать, уже не так наглядно:

def test(st,pat): if st==pat: return True if pat>"" and pat[0]=='*': if test(st,pat[1:]):return True if st>"" and pat>"": if st[0]==pat[0] or pat[0]=='?': if test(st[1:],pat[1:]):return True if pat[0]=='*': if test(st[1:],pat):return True return False import time
pt=time.time()
print(test("babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab","***bba**a*bbba**aab**b"))
print(time.time()-pt)

921879768371582 сек. Вот результат: 3. Возвращаемся к арбитру: (это уже ближе к исходному).

И еще раз.

Делаю вывод, что за временные рамки выходит суммарное прохождение тестов, потому как последние два варианта решаются очень быстро.

Нужна оптимизация на порядок.

Что напрашивается, точно — поиск в ширину.

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

Попробую сделать это питоном, а потом продемонстрирую пролог.

def test(st,pat): if st==pat: return True res=[] #буду собирать все варианты перехода вглубь, это уровни дерева if pat>"" and pat[0]=='*':res+=[(st,pat[1:])] if st>"" and pat>"": stt=st[1:] if st[0]==pat[0] or pat[0]=='?':res+=[(stt,pat[1:])] if pat[0]=='*':res+=[(stt,pat)] return res def run(st,pat): lev=[(st,pat)] while len(lev)!=0: nxt=set() ##все нижележащие решения соберем в множество без дублей for s,p in lev: one=test(s,p) if one==True:return True else:nxt.update(set(one)) lev=nxt return False

01585698127746582 сек.
и..., УРА это решение принимается Тут уже результат для теста 939, всего 0.

Для этого есть специальные предикаты второго порядка, которые могут собрать решения в список, например bagof, setof, findall. Попробую показать, как реализовать поиск в ширину, в декларативной реализации.

If Goal has free variables besides the one sharing with Template, bagof/3 will backtrack over the alternatives of these free variables, unifying Bag with the corresponding alternatives of Template. bagof(+Template, :Goal, -Bag)
Unify Bag with the alternatives of Template. bagof/3 fails if Goal has no solutions.
setof(+Template, +Goal, -Set)
Equivalent to bagof/3, but sorts the result using sort/2 to get a sorted list of alternatives without duplicates. The construct +Var^Goal tells bagof/3 not to bind Var in Goal.

он уже умеет удалять дубли (в питоне для этого пришлось узнать о множествах). Хорошо подходит предикат setof т.к.

Итак, сделаю предикат который получает решение одного уровня, далее собираем это другим предикатом и углубляемся, вот полное решение:

atom_to_list(Str,[Ch|T]) :- atom_concat(Ch,Rest,Str),atom_length(Ch,1), atom_to_list(Rest,T). %варианты переходов
pattrn(X:X,true). %- все хорошо когда оба одинаковые
pattrn([Ch|UnpTail]:[Ch|PatTail],UnpTail:PatTail).
pattrn([_|UnpTail]:['?'|PatTail],UnpTail:PatTail).
pattrn([_|UnpTail]:['*'|PatTail],UnpTail:['*'|PatTail]).
pattrn(Str:['*'|PatTail],Str:PatTail). %если попался true, значит более искать не надо, иначе проверка уровня ниже
next_level(Lev):-member(true,Lev),!.
next_level(Lev):-setof(One,SP^(member(SP,Lev),pattrn(SP,One)),Next),!, next_level(Next). test_pattrn(Str,Pat):-next_level([Str:Pat]). isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!, test_pattrn(SL,PL),!. %unit-tests framework
assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is Fin-St, writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is Fin-St, writeln(Goal->ok:Per/sec).
assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %all test
:-assert_are_equal(isMatch(aa,a),false).
:-assert_are_equal(isMatch(aa,'*'),true).
:-assert_are_equal(isMatch(cb,'?a'),false).
:-assert_are_equal(isMatch(adceb,'*a*b'),true).
:-assert_are_equal(isMatch(acdcb,'a*c?b'),false).
:-assert_are_equal(isMatch(aab,'c*a*b'),false).
:-assert_are_equal(isMatch(mississippi,'m??*ss*?i*pi'),false).
:-assert_are_equal(isMatch(abefcdgiescdfimde,'ab*cd?i*de'),true).
:-assert_are_equal(isMatch(zacabz,'*a?b*'),false).
:-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false).
:-assert_are_equal(isMatch(aaaa,'***a'),true).
:-assert_are_equal(isMatch(b,'*?*?*'),false).
:-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true).
:-assert_are_equal(isMatch(abbbbbbbaabbabaabaa,'*****a*ab'),false).
:-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true).
:-assert_are_equal(isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab,'***bba**a*bbba**aab**b'),false).

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

И результаты выполнения с временем в сек.:

isMatch(aa, a)->ok:0.00010013580322265625/sec
isMatch(aa, *)->ok:4.00543212890625e-5/sec
isMatch(cb, ?a)->ok:3.981590270996094e-5/sec
isMatch(adceb, *a*b)->ok:0.0001399517059326172/sec
isMatch(acdcb, a*c?b)->ok:9.989738464355469e-5/sec
isMatch(aab, c*a*b)->ok:4.00543212890625e-5/sec
isMatch(mississippi, m??*ss*?i*pi)->ok:0.0003399848937988281/sec
isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok:0.0003600120544433594/sec
isMatch(zacabz, *a?b*)->ok:9.989738464355469e-5/sec
isMatch(leetcode, *e*t?d*)->ok:0.00020003318786621094/sec
isMatch(aaaa, ***a)->ok:9.989738464355469e-5/sec
isMatch(b, *?*?*)->ok:6.008148193359375e-5/sec
isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab, *ab***ba**b*b*aaab*b)->ok:0.0040400028228759766/sec
isMatch(abbbbbbbaabbabaabaa, *****a*ab)->ok:0.0006201267242431641/sec
isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab, *ab***ba**b*b*aaab*b)->ok:0.003679990768432617/sec
isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab, ***bba**a*bbba**aab**b)->ok:0.002460002899169922/sec

И это уже успешное решение не только логически но и по времени.

Тема "ниасилил такой подход" сразу открылась, все же интерес проявить можно. В предыдущей статье, я хотел увидеть интерес к теме декларативного подхода. Попытки создать параллельный пролог успешностью не завершились. Тут я показал, что есть проблема производительности, то что написано ясно не работает быстро. Может тут вопрос будущего, квантовый компьютер сможет??
Итого используем задачки, на вышеуказанном сайте, для приятного времяпровождения с умом.

Ну и в следующий раз, будет попытка сразу решить эффективно еще одну из хард-задач.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть