[pyar] [JUEGO] Búsqueda de strings

[Roberto Alsina]

Lo movemos a optimizacion-prematura en python.org.ar? Tiene un alias 
la-raiz-de-todos-los-males en python.org.ar ;-)



On 03/05/14 06:10, Angel Java Lopez wrote:
> Jajaja! Alguna vez tenia que aparece Boyer-Moore ;-)
>
> #soytanviejo que vi nacer a ese algoritmo. Debio aparecer en mi radar 
> en alguna Scientific American de los ochenta. Eramos tan pobres. ... ;-)
>
> No sabia que CPython se habia tomado la molestia de implementar todo 
> eso, buen dato!
>
> Ahora bien, sea S lo que  buscamos. Lo que yo haria es que a cada S 
> distinta, le asignaria un numero natural distinto
>
> f(S) = n
>
> Para cada elemento de L, L[i], prepararia una sarta de bits. El bit n 
> estaria prendido, si el S correspondiente a ese n (los S tales que 
> f(S) = n) esta contenido en L[i]. (bien podriamos poner que  S = 
> "com", S = "Com", S = "COM", ... todos den el mismo n)
>
> Luego, ante cada S que se presente, calcularia f(S) = n
> Y me fijaria en cada L[i] si su sarta de bits tiene el n bit prendido
>
> Me imagino que lo de arriba es O(n) (dependiente de la longitud L, 
> llamemosla n, como en los anteriores corroes, pero no dependiente de 
> m, la maxima longitud de los L[i])
>
> Si no quiero llegar a esos extremos... .hmmm... recuerdo algo que 
> implemente a principio de los ochenta, antes de la guerra de las 
> Malvinas, aca en Argentina.
>
> Varias variantes. Primero la sencilla. A cada letra del alfabeto que 
> estemos usando, le asignamos el numero n, distinto para cada letra que 
> consideramos distinta. Por cada L[i], mantengo una serie de bits. El 
> bit n esta prendido si la letra A correspondiente a n, esta en L[i] 
> (uno a varias veces). Luego, por cada S que se presente, calculo la 
> sarta de bits que le corresponde (que letras contiene). Hago AND 
> logico de esa sarta de bits con los de cada L[i]. Solo me mato 
> haciendo el "in" en los L[i] que tengan todos los bits de S
>
> Segundo, en vez de bits por letra, tener un lugar que diga: la 
> cantidad de veces que esta esta letra en el texto T. Idem que antes
>
> Tercera, la que implemente en los ochenta: tener bits de presencia de 
> letras por cada subsarta de L[i]. Digamos, tengo bits de presencia de 
> letras para los caracteres 0 a 15 de L[i], de 8 a 23, de 16 a 31, 
> etc... Por cada S que se presenta, calculo su presencia de letras. Si 
> S tiene longitud <= 16, solo busco en las subsartas de L[i] 
> CONSECUTIVAS que entre ambas tengan todas las letras de S, o en las 
> subsartas de L[i] que tengan todas las letras de S (algunos ajustes, 
> pero es la idea). Si S tiene longitud <= 32, se modifica un poco, y asi
>
> Creo recordar que esta tercera variante es la que implemente para una 
> especie de full-text search de entrecasa de aquel entonces. El tener 
> un bit prendido o apagado en una sarta larguisima, debio ser sugerido 
> por el numero omega del bueno de Chaitin (al que finalmente conoci 
> personalmente en MathBA 2009)
>
> Nos leemos!
>
> Angel "Java" Lopez
> @ajlopez
>
>
>
> 2014-05-02 17:18 GMT-03:00 Alejandro Santos <listas en alejolp.com 
> <mailto:listas en alejolp.com>>:
>
>     2014-05-02 20:59 GMT+02:00 Natalia Bidart <nataliabidart en gmail.com
>     <mailto:nataliabidart en gmail.com>>:
>     > 2014-05-02 15:16 GMT-03:00 fisa <fisadev en gmail.com
>     <mailto:fisadev en gmail.com>>:
>     >
>     >> Buen punto, tomé el in como una operación más básica de lo que es.
>     >>
>     >> Sería un O(n . O-del-in), no?
>     >
>     > Esto está muy interesante, es exactamente la pregunta de la
>     complejidad del
>     > "in" para strings en Python:
>     >
>     >
>     http://stackoverflow.com/questions/18139660/python-string-in-operator-implementation-algorithm-and-time-complexity
>     >
>
>     Ya casi lo bajaste a O(n) :)
>
>
>
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de Argentina - http://www.usla.org.ar

------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20140505/a4efff25/attachment.html>