[pyar] ¿Volvemos a empezar?

[Roberto Alsina]

On 30/04/14 22:43, Fernando Pelliccioni wrote:
>
>
>
> 2014-04-30 21:54 GMT-03:00 Roberto Alsina <ralsina en netmanagers.com.ar 
> <mailto: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!
>
Sospecho que no entendés lo que hace el ejemplo que te dí recién.

> 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.
>
>

Si no te importa la implementación, no te importa la complejidad. La 
complejidad es una característica de la implementación.
Es como decir que la complejidad de sort() no depende de la implementación.


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