Donc, communauté, je vous demande de me donner une chance de vous surprendre la troisième fois, dans la décision précédente j'ai utilisé du python, je pensais attirer l'attention des experts ici et ils me diraient immédiatement pourquoi faire cela, en général il y a des expressions régulières - je l'ai fait et tout est sûr fonctionnera, ce que notre python peut donner et plus de vitesse.
Le prochain sujet de l'article devrait être une autre tâche à son tour, mais non, le premier ne m'a pas quitté, que peut-on faire pour obtenir une solution encore plus rapide, puisque la victoire sur le site a été couronnée par une autre compétition.
J'ai écrit une implémentation qui, en moyenne, était de ce type de vitesse, cela signifie qu'il y a encore 90% de solutions que je n'ai pas remarqué que quelqu'un sait comment le résoudre encore plus rapidement et il est silencieux , et après avoir regardé les deux articles précédents, je n'ai pas dit: oh, si cela problème de performance, alors tout est clair - ici le prologue ne correspond pas. Mais maintenant tout est normal avec les performances, il n'est pas possible d'imaginer un programme qui fonctionnera sur un matériel faible, "au final, pourquoi y penser?"
Défi
Pour résoudre le problème encore plus rapidement, il y avait un python et il y avait du temps, et y a-t-il une solution plus rapide sur python?
Je suis informé "Runtime: 2504 ms, plus rapide que 1,55% des soumissions en ligne Python3 pour Wildcard Matching."
Je vous préviens, il y a en outre un flux de pensées en ligne.
1 régulier?
Voici peut-être la possibilité d'écrire un programme plus rapide simplement en utilisant une expression régulière.
De toute évidence, python peut créer un objet d'expression régulière qui vérifiera la ligne d'entrée et il se révélera s'exécuter juste là, dans le bac à sable sur le site pour tester les programmes.
Il suffit d' importer , je peux importer un tel module, c'est intéressant, je dois essayer.
Il n'est pas facile de comprendre que la création d'une solution rapide n'est pas facile. Nous devrons rechercher, essayer et créer une implémentation similaire à celle-ci:
1. faire un objet de cette régularité,
2. lui remettre un modèle corrigé par les règles des règles de bibliothèque sélectionnées,
3. Comparez et la réponse est prête
Voila:
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
voici une solution très courte, comme si elle était correcte.
J'essaie de courir, mais ce n'était pas là, ce n'est pas tout à fait raison, une option ne convient pas, vous devez tester la conversion vers le modèle.
La vérité est drôle, j'ai mélangé le modèle et la chaîne, mais la solution est venue, j'ai passé 1058 tests et échoué, seulement ici.
Je répète encore une fois, sur ce site, ils travaillent soigneusement sur les tests, comme c'est arrivé, tous les précédents sont bons, mais ici deux paramètres principaux sont mélangés et cela s'est révélé, voici les avantages du TDD ...
Et sur un texte si merveilleux, je reçois toujours une erreur
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
Dur
Il semble que cette tâche ait été spécialement surchargée de tests afin que ceux qui veulent utiliser des expressions régulières aient plus de difficultés, j'avais avant cette solution, il n'y avait pas d'erreurs logiques dans le programme, mais ici nous devons tenir compte de tant de choses.
Ainsi, l'expression régulière correspond et le premier résultat doit être égal à notre ligne.
Victoire
Ce n'était pas facile de lui faire utiliser l'expression régulière, mais la tentative a échoué, ce n'est pas une décision aussi simple de tromper les habitués. La première solution de recherche a fonctionné plus rapidement.
Voici une telle implémentation,
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
conduit à ceci:
Appel
Chers résidents, essayez de vérifier cela, et cela fait du python trois , il ne peut pas terminer rapidement cette tâche:
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 "***** b * aba *** Babaa * bbaba *** a * b * aaba * aa ** a * b ** ba *** a * a *") 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
Vous pouvez l'essayer à la maison. Miracles, cela ne prend pas seulement beaucoup de temps à résoudre, ça se fige, oooh.
Les expressions régulières sont-elles un sous-ensemble de l'aspect déclaratif des performances?
La déclaration est étrange, ils sont présents dans toutes les langues à la mode, donc la productivité devrait être impressionnante, mais ici, ce n'est pas du tout réaliste qu'il n'y ait pas de machine à états finis en eux?, Que se passe-t-il dans un cycle sans fin ??
Allez
J'ai lu dans un livre, mais c'était il y a longtemps ... La nouvelle langue de Go fonctionne très rapidement, mais qu'en est-il de l'expression régulière?
Je vais le tester:
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) }
J'avoue, ce n'était pas facile d'obtenir un texte aussi concis, là la syntaxe n'est pas banale, même avec la connaissance de si, ce n'est pas facile de le comprendre ...
C'est un résultat merveilleux, la vitesse est vraiment de retour, totalisant ~ 60 millisecondes, mais il est surprenant que cette solution soit plus rapide que seulement 15% des réponses sur le même site.
Et où est le prologue
Je trouve que ce langage oublié pour travailler avec des expressions régulières nous fournit une bibliothèque basée sur l'expression régulière compatible Perl.
C'est ainsi qu'il peut être implémenté, mais prétraitez la chaîne de modèle avec un prédicat distinct.
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)]).
Et le temps d'exécution est très bien:
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
MAIS, il y a quelques limitations, le prochain test a apporté:
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)
En conclusion
Il ne restait que des questions. Tout peut être implémenté, mais la vitesse est boiteuse.
Les solutions transparentes ne sont pas efficaces?
Quelqu'un a implémenté des expressions régulières déclaratives, quels types de mécanismes existe-t-il?
Et comment aimez-vous ces défis, y a-t-il un problème qui peut être résolu, mais où est la solution parfaite?