Entonces, comunidad, le pido que me dé la oportunidad de sorprenderlo por tercera vez, en la decisión anterior que usé python, pensé que llamaría la atención de los expertos aquí e inmediatamente me dirían por qué hacer esto, en general hay expresiones regulares: lo hice y todo es seguro funcionará, esto nuestro python puede dar y más velocidad.
El siguiente tema del artículo debería ser otra tarea, pero no, el primero no me dejó, qué se puede hacer para obtener una solución aún más rápida, ya que la victoria en el sitio se coronó con otra competencia.
Escribí una implementación que, en promedio, era de este tipo de velocidad, lo que significa que todavía hay un 90 por ciento de soluciones que no noté que alguien sabe cómo resolverlo aún más rápido y él está en silencio , y después de mirar los dos artículos anteriores no dije: oh, si problema de rendimiento, entonces todo está claro: aquí el prólogo no encaja. Pero ahora todo es normal con el rendimiento, no es posible imaginar un programa que se ejecute en hardware débil, "al final, ¿por qué pensarlo?"
Desafío
Para resolver el problema aún más rápido, hubo una python y hubo tiempo, ¿y hay una solución más rápida en python?
Me informan "Tiempo de ejecución: 2504 ms, más rápido que el 1.55% de los envíos en línea de Python3 para Wildcard Matching".
Te advierto, además hay una corriente de pensamientos en línea.
1 regular?
Tal vez aquí está la opción de escribir un programa más rápido simplemente usando una expresión regular.
Obviamente, Python puede crear un objeto de expresión regular que verificará la línea de entrada y se ejecutará allí mismo, en el entorno limitado del sitio para probar programas.
Solo importa re , puedo importar dicho módulo, es interesante, tengo que intentarlo.
No es fácil entender que crear una solución rápida no es fácil. Tendremos que buscar, probar y crear una implementación similar a esta:
1. Haz un objeto de esta regularidad,
2. entregarle una plantilla corregida por las reglas de la biblioteca regular de la biblioteca seleccionada,
3. Compara y la respuesta está lista
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
Aquí hay una solución muy breve, como correcta.
Estoy intentando ejecutar, pero no estaba aquí, no es del todo correcto, alguna opción no encaja, debe probar la conversión a la plantilla.
La verdad es graciosa, mezclé la plantilla y la cadena, pero la solución se unió, pasé 1058 pruebas y fallé, solo aquí.
Repito una vez más, en este sitio están trabajando cuidadosamente en las pruebas, como sucedió, todas las anteriores son buenas, pero aquí se mezclan dos parámetros principales y esto apareció, aquí están las ventajas de TDD ...
Y en un texto tan maravilloso, sigo teniendo un error
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
Duro
Parece que esta tarea se superpuso especialmente con las pruebas para que aquellos que quieran usar expresiones regulares tengan más dificultades, tuve antes de esta solución, no hubo errores lógicos en el programa, pero aquí tenemos que tener en cuenta tantas cosas.
Entonces, la expresión regular coincide y el primer resultado debe ser igual a nuestra línea.
Victoria
No fue fácil lograr que usara la expresión regular, pero el intento falló, no es una decisión tan simple quimiar a los clientes habituales. La primera solución de búsqueda funcionó más rápido.
Aquí hay tal implementación,
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
lleva a esto:
Apelar
Estimados residentes, intenten verificar esto, y hace que Python tres , no puede completar rápidamente esta tarea:
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
Puedes probarlo en casa. Milagros, no solo lleva mucho tiempo resolverlos, se congela, oooh.
¿Son las expresiones regulares un subconjunto del aspecto declarativo poco convincente en el rendimiento?
La afirmación es extraña, están presentes en todos los idiomas de moda, por lo que la productividad debería ser asombrosa, pero aquí no es del todo realista que no haya una máquina de estados finitos en ellos, ¿qué sucede allí en un ciclo sin fin?
Ir
Leí en un libro, pero fue hace mucho tiempo ... El lenguaje más nuevo de Go funciona muy rápido, pero ¿qué pasa con la expresión regular?
Lo pondré a prueba:
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) }
Admito que no fue fácil obtener un texto tan conciso, allí la sintaxis no es trivial, incluso con el conocimiento de si, no es fácil entenderlo ...
Este es un resultado maravilloso, la velocidad realmente aumenta, un total de ~ 60 milisegundos, pero es sorprendente que esta solución sea más rápida que solo el 15% de las respuestas en el mismo sitio.
¿Y dónde está el prólogo?
Me parece que este lenguaje olvidado para trabajar con expresiones regulares nos proporciona una biblioteca basada en Expresión regular compatible con Perl.
Así es como se puede implementar, pero preprocese la cadena de plantilla con un predicado separado.
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)]).
Y el tiempo de ejecución está 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
PERO, hay algunas limitaciones, la siguiente prueba trajo:
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)
Como conclusión
Solo quedaban preguntas. Todo se puede implementar, pero la velocidad es escasa.
¿Las soluciones transparentes no son efectivas?
Alguien implementó expresiones regulares declarativas, ¿qué tipo de mecanismos existen?
¿Y cómo le gustan estos desafíos? ¿Hay algún problema que pueda resolverse, pero dónde está la solución perfecta?