Хабрахабр

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

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

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

Но с производительностью сейчас все нормально, представить себе программу, которая будет запущена на слабом железе не возможно, "в конце концов, зачем об этом думать?" Я написал реализацию которая в среднем была вот такого вида скорости, значит есть еще 90 процентов решений, которых я не заметил, что кто-то знает как ее решить еще быстрее и он молчит, и посмотрев две предыдущие статьи не сказал: ах, если это вопрос производительности, тогда все понятно — тут пролог не подходит.

Решить задачу еще быстрее, там был питон и было время, и есть на питоне более быстрое решение?

55% of Python3 online submissions for Wildcard Matching."
Мне сообщают "Runtime: 2504 ms, faster than 1.

Предупреждаю, далее происходит поток мысли онлайн.

Может тут вариант написать более быструю программу просто воспользовавшись регулярным выражением.

Явно питон может создать объект регулярного выражения, который проверит входную строку и это получится запустить прямо там, в той песочнице, что на сайте для тестирования программ.
Всего лишь import re, смогу сделать импорт такого модуля, это интересно, надо попробовать.

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

1.сделать объект этой регулярки,
2.подсунуть ей шаблон подправленный по правилам регулярок выбранной библиотеки,
3.сравнить и ответ готов
Вуаля:

import re
def isMatch(s,p): return re.match(s,pat_format(p))!=None def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" if ch=='?':res+="." else: res+=ch return res

вот очень короткое решение, как будто правильное.

Пробую запустить, но не тут то было, не совсем правильно, какой-то вариант не подходит, надо тестировать преобразование в шаблон.

Правда забавно, я перепутал шаблон и строку, а решения сошлось, я прошел 1058 тестов и провалился, только тут.

Еще раз повторюсь, на этом сайте работают внимательно над тестами, как так получилось, все предыдущее хорошо, а тут перепутаны два основных параметра и это проявилось, вот вам преимущества TDD...

И на вот такой замечательный текст, я все равно получаю ошибку

import re
def isMatch(s,p): return re.match(pat_format(p),s)==None def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res

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

Значит так — регулярное выражение матчится и первый же результат должен равняться нашей строке.

Решение поиском в ширину срабатывало быстрее. Победа?
Не просто было заставить его использовать регулярное выражение, но попытка не удалась, не такое это и простое решение химичить регулярки.

Вот такая реализация,

import re
def isMatch(s,p): res=re.match(pat_format(p),s) if res is None: return False else: return res.group(0)==s def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res

приводит к вот этому:

Дорогие жители, попробуйте проверить вот это, и это делает питон три, он не может быстро выполнить вот такое задание:

import re
def isMatch(s,p): res=re.match(pat_format(p),s) if res is None: return False else: return res[0]==s def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res
##test 940
import time
pt=time.time()
print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*"))
print(time.time()-pt)

Чудеса, оно не просто долго решается, оно зависает, оооо. Можно попробовать дома.

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

Я читал в одной книге, но это было давно… новейший язык Го работает очень быстро, а как там с регулярным выражением?

Испытаю-ка и его:

func isMatch(s string, p string) bool { res:=strings.Replace(p, "*", "(.)*", -1) res2:=strings.Replace(res, "?", ".", -1) r, _ := regexp.Compile(res2) fr:=r.FindAllString(s,1) return !(len(fr)==0 || len(fr)!=0 && fr[0]!=s)
}

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

Это замечательный результат, скорость действительно зашкаливает, итого ~60 милисек, но удивительно, что это решение быстрее только 15% ответов на этом же сайте.

Найду, что нам предоставляет этот забытый язык для работы с регулярными выражениями, есть библиотека на базе Perl Compatible Regular Expression.

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

pat([],[]).
pat(['*'|T],['.*'|Tpat]):-pat(T,Tpat),!.
pat(['?'|T],['.'|Tpat]):-pat(T,Tpat),!.
pat([Ch|T],[Ch|Tpat]):-pat(T,Tpat). isMatch(S,P):- atom_chars(P,Pstr),pat(Pstr,PatStr),!, atomics_to_string(PatStr,Pat), term_string(S,Str), re_matchsub(Pat, Str, re_match,[bol(true),anchored(true)]).

И время выполнения отлично:

isMatch(aa,a)->ok:0.08794403076171875/sec
isMatch(aa,*)->ok:0.0/sec
isMatch(cb,?a)->ok:0.0/sec
isMatch(adceb,*a*b)->ok:0.0/sec
isMatch(acdcb,a*c?b)->ok:0.0/sec
isMatch(aab,c*a*b)->ok:0.0/sec
isMatch(mississippi,m??*ss*?i*pi)->ok:0.0/sec
isMatch(abefcdgiescdfimde,ab*cd?i*de)->ok:0.0/sec
isMatch(zacabz,*a?b*)->ok:0.0/sec
isMatch(leetcode,*e*t?d*)->ok:0.0009980201721191406/sec
isMatch(aaaa,***a)->ok:0.0/sec
isMatch(b,*?*?*)->ok:0.0/sec
isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,*ab***ba**b*b*aaab*b)->ok:0.26383304595947266/sec
isMatch(abbbbbbbaabbabaabaa,*****a*ab)->ok:0.0009961128234863281/sec
isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab,***bba**a*bbba**aab**b)->ok:0.20287489891052246/sec

НО, есть какие-то ограничения, очередной тест вывел:

Not enough resources: match_limit
Goal (directive) failed: user:assert_are_equal(isMatch(aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba,'*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*'),false)

Можно реализовать все, но скорость хромает.
Прозрачные решения не бывают эффективны? Итого остались только вопросы.

Декларативные регулярные выражения кто-то реализовал, что там за механизмы?

И как вам такие вызовы, есть задача, которую можно решать, а где оно идеальное решение?

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

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

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

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

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