[pyar] ¿Volvemos a empezar?

[Fernando Pelliccioni]

2014-04-30 21:54 GMT-03:00 Roberto Alsina <ralsina en netmanagers.com.ar>:

>  On 30/04/14 21:37, Fernando Pelliccioni wrote:
>
> No, no creo que la sepas :-)
>
>>  La complejidad es la que sea que tenga s.__getitem__
>>
>
>  Tengo que leer todavia el link que me pasaste acerca de s.__getitem__
> Bueno, en realidad me refería a suponer el peor de los casos.
> Suponiendo el peor de los casos, que significa hacer? ( no solo
> complejidad asintótica, sino, operaciones concretas )
>
>   s == s[::-1]
>
>
>  La respondo yo.
>
>  En el peor de los casos:
> 1.    Para s[::-1]
>                     - Memory allocation para la nueva secuencia, ya que
> como vimos antes, no podemos asegurar que id(s) == id(s[::-1])
>                     - Cargar la nueva lista con las referencias de la
> lista original
>
>   2.  Para la comparacion de igualdad ==
>                - Iterar sobre la secuencia, realizando...
>               - N comparaciones
>
> ¿Es necesaria esta complejidad para un algoritmo de palindromos? (no
> perder de vista que tengo en mente otra cosa)
>   ¿Es el optimizer tan inteligente para darse cuenta de esto? ¿seguro?
> ¿como lo podemos verificar?
>
>
> Quien dice que hay que generar toda la lista invertida?
>
> all(a[-i-1]==a[i]  for i in range(len(a)))
>
> Sin embargo, si alguien me da ese código, en vez de a == a[::-1] es obvio
> que a menos que me dé una excelente razón, está simplemente mal.
>
>
Por ahora, el ejercicio es un caso simple, que quiero extenderlo a algo mas
complicado, donde si vamos a necesitar optimizar. Prometo que es un caso
mucho mas interesante!

Pero que opinas si, como usuario del algoritmo, en vez de escribir

      a == a[::-1]

escribis

    is_palindrome(a)

?

Como usuario no te importa como implementado, (si con "la lista invertida"
o usando "Slice") solo te importa como se usa y la complejidad del mismo.




> _______________________________________________
> 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/20140430/ca5fe94a/attachment-0001.html>