[pyar] ¿Volvemos a empezar?

[Fernando Pelliccioni]

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

>  On 30/04/14 22:37, Fernando Pelliccioni wrote:
>
>
>
>
> 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.
>
>
> 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.
>
>
>
Lei hasta aca nada mas, me tengo que ir.

Creo que alguno de los dos no entiende cual es la relacion entre Slice y
GetItem. Lo mas probable es que sea yo :)
Concentrandonos solo en Secuencias (dejando de lado mapping types) asumo
que GetItem sirve para acceder a un indice dado por una secuencia.
Como implementarias Slice con GetItem? (Suponiendo que Slice sea una
funcion)

 Lo dejo aca por ahora! realmente no puedo seguir!

Saludos!

>
>
>>
>>
>>   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.
>
> _______________________________________________
> 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/272a9ba2/attachment-0001.html>