[pyar] ¿Volvemos a empezar?

[Roberto Alsina]

On 30/04/14 21:37, Fernando Pelliccioni wrote:
>
>>     Ahora, que "conozco" algo sobre la semantica de Slice.
>>     ¿Que implica, a nivel complejidad, hacer lo siguiente?
>>
>>     s == s[::-1]
>>
>>     Donde s es una secuencia (o un tipo "Slice-able").
>>
>
>     Depende.
>
>
>>     Por las dudas claro:
>>     Se la respuesta, lo pregunto para que veamos si podemos mejorar
>>     el algoritmo)
>
>     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.

Infinita.

class X(object):
     def __getitem__(self, *a, **kw):
         while True:
             pass

¿En el mejor de los casos? Constante:

 >>> class X(object):
...     def __getitem__(self, *a, **kw):
...          return 42
...
 >>> x=X()
 >>> x[1:34]
42


> 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

En general si, van a ser distintas. No veo como podrían ser la misma en 
el caso general. Claro, si fuera una lista podrías reordenarla in-place.

>
>  2.  Para la comparacion de igualdad ==
>               - Iterar sobre la secuencia, realizando...
>               - N comparaciones
>

Supongo.

> ¿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?

En todo esto estás abstrayéndote de qué es s. En un lenguaje dinámico, 
eso es lo más importante. Si decís "s es de clase str" es otra cosa.
pero estás tratando todo en abstracto. Si s es "un iterable" entonces 
imaginate que pasa si es de la clase X que puse arriba.


>
> (Para el mejor de los casos tendría que explorar la semántica de  s == 
> s, que me estimo que luego de ser optimizado es NO-OP.)
>
>
> Ahora, realmente no quiero seguir rompiendo las bolas si estos temas 
> no interesan en la lista o piensan que no son importantes.
> Podemos someterlo a votación o puedo seguir y cada cual es libre de 
> leer u omitir.


No empecemos otro thread infinito acerca de la votación :-)
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20140430/a47ed62f/attachment.html>