Комментарии 39
def isMatch(s,p):
res=re.match(pat_format(p),s)
return res is not None
def pat_format(pat):
pat = re.sub("[*]{2,}", "*", pat)
pat = re.sub("[?]", ".", pat)
pat = re.sub("[*]", "(?:.)*?", pat)
return "^" + pat + "$"
func isMatch(s string, p string) bool {
res:=strings.Replace(p, "**", "*", -1)
res1:=strings.Replace(res, "?", ".", -1)
res2:=strings.Replace(res1, "*", "(?:.)*?", -1)
r := regexp.MustCompile("^" + res2 + "$")
return r.MatchString(s)
}
Хм. сперва нарисовало 40ms, потом 68ms, то есть времена нестабильны.
Мне интересно, а зачем вам вообще какая‐либо группировка? *
применяется к предыдущему атому, точка — сама по себе атом. Поэтому .*
должно нормально зайти. Если добавить ?
, то такое решение выдаёт превышение time limit (на моей системе — 8,7 секунд) значительно позже, на тесте 1614:
#!/usr/bin/env python3
import re
class Solution(object):
@staticmethod
def isMatch(s,p):
r = "^"
for ch in p:
if ch == '*':
r += ".*?"
elif ch=='?':
r += "."
else:
r += ch
r += "$"
return bool(re.match(r, s))
# Test 1614
from time import monotonic
start = monotonic()
print(Solution.isMatch("aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba", "a*******b"))
print(monotonic() - start)
# ##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)
как вывод — Питон неожиданно медленный…
Кстати, что с жадным, что с нежадным, и в обоих случаях максимально оптимизированном регулярным выражением Python виснет на тесте 1708, хотя тест 1614 уже на моей машине проходит за примерно 0,2 мс независимо от жадности. Вот, собственно, код:
#!/usr/bin/env python3
import re
START = 0
LITERAL = 1
ANY = 2
SOME = 3
MANY = 4
END = 5
class Solution(object):
@staticmethod
def isMatch(s, p):
atoms = [(START,)]
for ch in p:
last_atom_typ = atoms[-1][0]
if ch == '*':
if last_atom_typ == ANY:
atoms[-1] = [MANY, 1]
elif last_atom_typ == MANY:
pass
elif last_atom_typ == SOME:
atoms[-1] = [MANY, atoms[-1][1]]
else:
atoms.append([MANY, 0])
elif ch=='?':
if last_atom_typ == MANY:
atoms[-1][1] += 1
elif last_atom_typ == SOME:
atoms[-1][1] += 1
elif last_atom_typ == ANY:
atoms[-1] = [SOME, 2]
else:
atoms.append((ANY,))
else:
if last_atom_typ == LITERAL:
atoms[-1][1] += ch
else:
atoms.append([LITERAL, ch])
atoms.append((END,))
atom_to_str_funcs = (
lambda x: '^',
lambda x: x[1],
lambda x: '.',
lambda x: '.{{{}}}'.format(x[1]),
lambda x: '.{{{},}}?'.format(x[1]),
lambda x: '$',
)
r = ''.join((
atom_to_str_funcs[i[0]](i)
for i in atoms
))
return bool(re.match(r, s))
from time import monotonic
# Test 1614
start = monotonic()
print(Solution.isMatch("aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba", "a*******b"))
print(monotonic() - start)
# Test 1708
start = monotonic()
print(Solution.isMatch("abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb", "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"))
print(monotonic() - start)
# Test
# ##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)
(Для нежадной версии убейте второй вопросительный знак, их здесь всего два.) Я не думаю, что можно сделать что‐то лучше на регулярных выражениях. Вот, кстати, что мой код генерирует для данного теста:
^.{0,}?aa.{0,}?ba.{0,}?a.{0,}?bb.{0,}?aa.{0,}?ab.{0,}?a.{0,}?aaaaaa.{0,}?a.{0,}?aaaa.{0,}?bbabb.{0,}?b.{0,}?b.{0,}?aaaaaaaaa.{0,}?a.{0,}?ba.{0,}?bbb.{0,}?a.{0,}?ba.{0,}?bb.{0,}?bb.{0,}?a.{0,}?b.{0,}?bb$
Регулярные выражения только в самом простом варианте эквивалентны FSM, не помню где там грань проходит, но нежадные квантификаторы уже добавляют backtracking и это может привксти к очень долгой работе. Да и регулярные выражения это не декларативный подход, просто мини-язык.
это описание задачи, которую нужно решать, отсюда и производительность может хромать, посмотрите как пример с Го летает
import re
import time
def isMatch(s, p):
m = re.match(pat_format(p), s)
if not m:
return False
else:
return m.group() == s
def pat_format(pat):
pat = re.sub("[*]{2,}", "*", pat)
pat = re.sub("[?]", ".", pat)
pat = re.sub("[*]", "(.)*", pat)
return pat
pt=time.time()
print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*"))
print(time.time()-pt)
Не проходит тест далее:
1708 / 1808 test cases passed.
Status: Time Limit Exceeded
Submitted: 0 minutes ago
Last executed input:
«abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb»
"**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
В нем нет сочетания такого большого количества `aaaaaaaaa` (хотя и не в нем наверно суть) и нет финишной кавычки.
Дополнительный вопрос: данные в группировках нужны? Они замедляют работу в ~2.5 раза.
Можно заменить:
def pat_format(pat):
pat = re.sub("\*{2,}", "*", pat)
pat = re.sub("\?", ".", pat)
pat = re.sub("\*", ".*", pat)
return pat
Просто не отображается вся строка в тексте комментария по длине.
class Solution:
start_p = re.compile("\*+")
q_p = re.compile("\?")
def isMatch(self, s: str, p: str):
test_s = s
pattern_list = list(filter(None, self.pat_format(p).replace('.*?', '\n.*?').split('\n')))
pattern_len = len(pattern_list)
last_index = pattern_len - 1
for index, pattern in enumerate(pattern_list):
if index == last_index:
pattern = pattern + '$'
m = re.match(pattern, test_s)
if not m:
return False
test_s = test_s[m.span()[1]:]
return not bool(test_s)
def pat_format(self, pat: str):
pat = self.q_p.sub(".", pat)
pat = self.start_p.sub(".*?", pat)
return pat
Вроде получился неплохой результат, лучший прогон: 108 Runtime (ms).
Your runtime beats 87.06 % of python3 submissions.
Если интересны подробности — habr.com/post/56765
а если в скобки завернуть (.*)+ — «Time Limit Exceeded» еще раньше
re не поддерживает их (regex да, но он недоступен).
можно поиграться с negative lookahead's чтоб избавиться от отката назад.
AI-Vadim выше реализовал их отдельными запросами, что не совсем спортивно :D
>>> import time
>>> start = time.time(); fnmatch.fnmatch('aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba', '*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*'); time.time() - start
True
816.2632331848145
>>>
Time Limit Exceeded
«abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb»
"**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
Если вы наберёте в iPython import fnmatch
, затем fnmatch??
, то увидите, что fnmatch
делает ровно то же самое, что и ряд людей выше, включая меня: преобразует шаблон в регулярное выражение.
Хотел бы про скобки сказать.
Скобки нужны как для описания регекспа, так и для разметки групп.
Движок не знает, что вы от него хотите тупо проверить "матчится или нет", а не "что с чем матчится".
Поэтому лучше использовать non-capturing group (?: sub-expression-goes-here )
— как посоветовали в первом комментарии (без объяснений, правда).
А в случае со звёздочкой .*
— вообще непонятно, зачем было вводить группу. Квантификатор же относится ровно к предшествующему терму.
Регекспы с кучей звёздочек внутри не могут не тупить на "плохих" строках, если только не приложить специальные усилия.
Потому что:
1) там работают откаты
2) регекспы — детерминированные, там не просто "что-то с чем-то сматчилось", а "сматчилось лексикографически первое в рамках жадности/ленивости квантификаторов".
Поэтому накаты и откаты там последовательные.
Как, кстати, и в наивной реализации матчилки на прологе.
Как можно оптимизировать матчилку?
Ну, например, сделать очевидную проверку:
набор_букв(строки) ⊇ набор_букв(образца без глоб-символов)
% первый аргумент - надпоследовательность второго
is_supersequence(_, []).
is_supersequence([C|S], [C|P]) :- is_supersequence(S, P).
is_supersequence([_|S], P) :- is_supersequence(S, P).
% (вроде бы не налажал...)
% слабое условие: если fail, то наверняка test_pattern провалится
can_match(S, P) :- filter(is_letter, P, LP), is_supersequence(S, LP).
test_whole_pattern(S, P) :- can_match(S, P), test_pattern(S, P).
% а дальше как с гусём
Теоретически, такую проверку можно было бы втыкать на каждом рекурсивном вызове test_pattern после того, как звёздочка или вопросик откусили символ строки.
Но тогда мы на ровном месте поднимем квадратичную сложность по заветам маляра Шлемюэля. А оно надо?
Значит, требуется перейти к каким-то структурам и проверкам, которые инкрементно сохраняют проверку на надпоследовательность.
Тут мне надо подумать, я этот труд ещё не проделал. Поэтому — только наброски.
- построить мультимножества букв строки и образца; при откусывании буквы из строки — декрементировать счётчик вхождений в строку и смотреть, что он не стал меньше счётчика вхождений в образец; при откусывании буквы из образца — просто декрементировать счётчик вхождений в образец. Это будет быстро работать, если в прологе есть структура данных "вектор / хештаблица". Если нет — то сперва велосипедить…
test_pattern(S, MultisetOfS, P, MultisetOfP)
- параллельно сопоставлению с образцом выполнять сопоставление с набором букв образца
test_pattern(S, P, LettersOfP)
то есть, мы знаем, какая буква будет следующей в образце, и соответственно делать более агрессивные проверки и/или предпочтительные ветвления
«вектор / хештаблица» в прологе только как динамические факты,
типа:
:-dynamic hash/2. - объявление в начале
assert(hash(Key,Value)) - добавление
hash(Key,Value) - проверка
retract(hash(Key,Value)), assert(hash(Key,NewValue)) - замена значения (в реализации Visual Prolog есть особые single факты их можно не удалять)
Но assert() это побочный эффект, использование глобального контекста, не очень чисто…
В этой попытке решения интересный результат получился с Го, при одинаковых условиях скорость порядочна.
Занимательный пролог #3