[pyar] ¿Volvemos a empezar?

[Roberto Alsina]

On 30/04/14 22:37, Fernando Pelliccioni wrote:
>
>
>
> 2014-04-30 21:45 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:
>>
>>>         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
>
>
> Vos podés calcular la complejidad del algoritmo a pesar de casos con 
> side-effects como estos.
> Para no concentrarnos en estas cosas por ahora, entonces, digamos que 
> vamos a operar con las secuencias built-in de Python.

No, no podés. Pero bueno, como decís vamos a las secuencias built-in. 
¿Cual? Porque no es lo mismo una lista que un string.

>
>
>     ¿En el mejor de los casos? Constante:
>
>     >>> class X(object):
>     ...     def __getitem__(self, *a, **kw):
>     ...          return 42
>     ...
>     >>> x=X()
>     >>> x[1:34]
>     42
>
>
> Por mas que __getitem__ sea constant-time no modifica la complejidad 
> de mi algoritmo, ejemplo
>
> # Pseudo-Codigo, no se exasperen, se que no es el estilo de 
> programacion usado en python, es un ejemplo
>         sum = 0
>         x = X()            # x es del tipo X
>         for ( i  from 0 to size(x) )
>              sum = sum + x[i]                      # x[i] es constant 
> time, y retorna siempre 42
>
> Cual es la complejidad de mi algoritmo?
>

Es que ahí estás calculando la complejidad de ese loop, no de lo que 
hace __getitem__ que es lo que hacía tu ejemplo anterior.
Cuando haces un slice, lo que hacés es una simple llamada a __getitem__. 
La complejidad de __getitem__ es arbitraria, depende de la clase.

>
>
>
>>     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.
>
>
>
> En C++, que no es un lenguaje dinamico, los algoritmos son programados 
> usando programacion generica, donde también abstraerse del tipo 
> concreto es lo mas importante.
> En programacion generica (Python es un lenguaje que soporta 
> perfectamente el paradigma), el algoritmo es el que debe imponer 
> (implicita o explicitamente) la sintaxis y la semantica a los tipos.
> Las imposiciones se pueden hacer usando sintaxis del lenguaje (si el 
> lenguaje esta preparado) o bien especificandolas en forma de 
> documentacion.
>

Ok, no tengo ganas de discutir. Como vos quieras. Si para vos la 
complejidad de s[::-1] no depende de la implementación de s.__getitem__ 
simplemente no tenemos un terreno en común para charlar.


> Ejemplo:
>
> #Pseudo python
>      def palindrome( s ) requires s is NonSideEffectsIterable
>          # ...
>
>   Donde en este hipotetico lenguaje, NonSideEffectsIterablees una 
> especializacion de Iterable que define que __getitem__ debe terminar y 
> no tener side-effects (supongamos)
>
> Entonces, solo puedo usar mi algoritmo palindrome con tipos acordes a 
> la especificacion del mismo.
> Si intento usarlo con tipos no soportados, bueno, si el lenguaje fuera 
> estatido, daria un error de compilacion, sino, imagino, algun runtime 
> error.
>
> No quería llegar tan lejos todavía. Me obligaste :)

Y si mi abuela tuviera ruedas, sería bicicleta. Si querés discutir lo 
que haría un hipotético algoritmo en un hipotético lenguage... no 
gracias :-)


>
>>
>>     (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 :-)
>
>
> Entonces sigo? O estoy siendo denso?

Seguí lo que quieras, pero a mí se me fueron las ganas de continuarla.
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20140430/2ed53be8/attachment.html>