Also, Community, ich bitte Sie, mir die Chance zu geben, Sie das dritte Mal zu überraschen. In der vorherigen Entscheidung, in der ich Python verwendet habe, dachte ich, ich würde die Aufmerksamkeit von Experten auf mich ziehen und sie würden mir sofort sagen, warum dies so ist. Im Allgemeinen gibt es reguläre Ausdrücke - ich habe es getan und alles ist sicher wird funktionieren, dies kann unsere Python geben und mehr Geschwindigkeit.
Das nächste Thema des Artikels sollte wiederum eine andere Aufgabe sein, aber nein, das erste hat mich nicht verlassen, was getan werden kann, um eine noch schnellere Lösung zu erhalten, da der Sieg auf der Website mit einem anderen Wettbewerb gekrönt wurde.
Ich habe eine Implementierung geschrieben, die im Durchschnitt so schnell war, das heißt, es gibt immer noch 90 Prozent der Lösungen, bei denen ich nicht bemerkt habe, dass jemand weiß, wie man sie noch schneller löst, und er schweigt , und nachdem ich mir die beiden vorherigen Artikel angesehen habe, habe ich nicht gesagt: Oh, wenn ja Leistungsproblem, dann ist alles klar - hier passt der Prolog nicht. Aber jetzt ist bei der Leistung alles normal. Man kann sich kein Programm vorstellen, das auf schwacher Hardware läuft. "Warum sollte man am Ende darüber nachdenken?"
Herausforderung
Um das Problem noch schneller zu lösen, gab es eine Python und es gab Zeit, und gibt es eine schnellere Lösung für Python?
Ich werde informiert "Laufzeit: 2504 ms, schneller als 1,55% der Python3-Online-Einreichungen für Wildcard Matching."
Ich warne Sie, weiter ist ein Strom von Gedanken online.
1 Normal?
Vielleicht besteht hier die Möglichkeit, ein schnelleres Programm einfach mit einem regulären Ausdruck zu schreiben.
Offensichtlich kann Python ein Objekt mit regulären Ausdrücken erstellen, das die Eingabezeile überprüft und direkt dort in der Sandbox auf der Site ausgeführt wird, um Programme zu testen.
Einfach wieder importieren , ich kann so ein Modul importieren, es ist interessant, ich muss es versuchen.
Es ist nicht leicht zu verstehen, dass das Erstellen einer schnellen Lösung nicht einfach ist. Wir müssen eine ähnliche Implementierung suchen, versuchen und erstellen:
1. ein Objekt dieser Regelmäßigkeit machen,
2. Legen Sie eine Vorlage auf sie, die durch die Regeln der ausgewählten Bibliotheksregeln korrigiert wurde.
3. Vergleichen und die Antwort ist fertig
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
Hier ist eine sehr kurze Lösung, als ob richtig.
Ich versuche zu laufen, aber es war nicht hier, es ist nicht ganz richtig. Einige Optionen passen nicht. Sie müssen die Konvertierung in die Vorlage testen.
Die Wahrheit ist lustig, ich habe die Vorlage und die Zeichenfolge verwechselt, aber die Lösung kam zusammen, ich habe 1058 Tests bestanden und bin nur hier gescheitert.
Ich wiederhole noch einmal, auf dieser Seite arbeiten sie sorgfältig an Tests, da alles passiert ist, aber hier sind zwei Hauptparameter verwechselt und dies hat sich gezeigt, hier sind die Vorteile von TDD ...
Und bei so einem wunderbaren Text bekomme ich immer noch einen Fehler
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
Schwer
Es scheint, dass diese Aufgabe speziell mit Tests überlagert wurde, damit diejenigen, die reguläre Ausdrücke verwenden möchten, mehr Schwierigkeiten bekommen. Ich hatte vor dieser Lösung keine logischen Fehler im Programm, aber hier müssen wir so viele Dinge berücksichtigen.
Der reguläre Ausdruck stimmt also überein und das erste Ergebnis sollte unserer Zeile entsprechen.
Sieg
Es war nicht einfach, ihn dazu zu bringen, den regulären Ausdruck zu verwenden, aber der Versuch schlug fehl. Es ist keine so einfache Entscheidung, die Stammgäste zu chemisieren. Die Breitensuchlösung funktionierte schneller.
Hier ist eine solche Implementierung,
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
führt dazu:
Berufung
Liebe Bewohner, versuchen Sie dies zu überprüfen, und es macht Python drei , er kann diese Aufgabe nicht schnell erledigen:
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
Sie können es zu Hause versuchen. Wunder, die Lösung dauert nicht nur lange, sie friert ein, oooh.
Sind reguläre Ausdrücke eine Teilmenge des deklarativen Aussehens in der Leistung?
Die Aussage ist seltsam, sie sind in allen modischen Sprachen vorhanden, daher sollte die Produktivität überwältigend sein, aber hier ist es überhaupt nicht realistisch, dass sie keine endliche Zustandsmaschine enthalten? Was passiert dort in einem endlosen Zyklus?
Geh
Ich habe in einem Buch gelesen, aber es ist lange her ... Go's neueste Sprache funktioniert sehr schnell, aber was ist mit regulären Ausdrücken?
Ich werde ihn testen:
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) }
Ich gebe zu, es war nicht einfach, einen so prägnanten Text zu erhalten, da die Syntax nicht trivial ist, selbst wenn man Si kennt, ist es nicht einfach, es herauszufinden ...
Dies ist ein wunderbares Ergebnis, die Geschwindigkeit rollt wirklich über, insgesamt ~ 60 Millisekunden, aber es ist überraschend, dass diese Lösung schneller ist als nur 15% der Antworten auf derselben Site.
Und wo ist der Prolog?
Ich finde, dass diese vergessene Sprache für die Arbeit mit regulären Ausdrücken uns eine Bibliothek bietet, die auf Perl-kompatiblen regulären Ausdrücken basiert.
Auf diese Weise kann es implementiert werden, aber verarbeiten Sie die Vorlagenzeichenfolge mit einem separaten Prädikat vor.
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)]).
Und die Laufzeit ist in Ordnung:
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
ABER es gibt einige Einschränkungen, der nächste Test brachte:
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)
Als Fazit
Es blieben nur Fragen. Alles kann implementiert werden, aber Geschwindigkeit ist lahm.
Transparente Lösungen sind nicht effektiv?
Jemand hat deklarative reguläre Ausdrücke implementiert. Welche Mechanismen gibt es?
Und wie gefällt Ihnen diese Herausforderung? Gibt es ein Problem, das gelöst werden kann, aber wo ist die perfekte Lösung?