[pyar] ¿Volvemos a empezar?

[Fernando Pelliccioni]

2014-04-30 21:45 GMT-03:00 Roberto Alsina <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.


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



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

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 :)


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


>
> _______________________________________________
> 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/4a8c3425/attachment.html>