Занимательный Пролог №3

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

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

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

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

Мне сказали: «Время выполнения: 2504 мс, быстрее, чем 1,55% онлайн-заявок Python3 для сопоставления с подстановочными знаками».

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

1 Обычный? Возможно, есть возможность написать более быструю программу, просто используя регулярное выражение.

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

Только импортировать повторно , могу импортировать такой модуль, интересно, надо будет попробовать.

Нелегко понять, что создать быстрое решение непросто.

Вам придется немного поискать, попробовать создать реализацию, подобную этой: 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

Вот очень короткое решение, которое кажется правильным.

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

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

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

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

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

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

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

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

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

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

Победа? Заставить его использовать регулярное выражение было непросто, но попытка не удалась, а изменить регулярные выражения – не такое уж и простое решение.

Решение поиска в ширину работало быстрее.

Это реализация

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

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

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

Обращаться Уважаемые жители, попробуйте это проверить, и это так.

питон три , он не может быстро выполнить следующую задачу:

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)

Вы можете попробовать это дома.

Чудеса, не просто долго решаются, а зависают, ох.

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

новейший язык Go очень быстрый, а как насчет регулярных выражений? Я тоже попробую:

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) }

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

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

15% ответы на том же сайте.

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

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

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{0:Str},[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)

В заключение В общем, остаются только вопросы.

Всё можно реализовать, но скорость хромает. Прозрачные решения не эффективны? Кто-нибудь реализовал декларативные регулярные выражения, какие там механизмы? А как вам такие вызовы? Есть проблема, которую можно решить, но где идеальное решение? Теги: #python #Go #Занимательные головоломки #Prolog