Contar digitos en un string

[Chema Cortes]

El día 18 de diciembre de 2008 15:35, Vicent <vginer en gmail.com> escribió:

> Tengo una pregunta un poco "de novato"; mi objetivo es entender mejor el
> manejo que hace Python de la memoria del ordenador:
>
> Centrándonos en la velocidad de ejecución de la que habláis, ¿todos las
> variantes propuestas consumen "el mismo tipo de memoria"?  Quiero decir,
> ¿todas hacen uso de la memoria "RAM", o alguna escribe algún valor en disco?
> Entiendo que sólo se usa la RAM, en ambos casos. El hecho de crear variables
> o listas intermedias, supone reservar un espacio de memoria RAM que luego se
> libera, ¿no? ¿Es eso peor (en términos de uso de memoria / velocidad) que
> hacerlo todo de modo "implícito", en una sola línea de código?

No te creas que se sabe mucho de la cantidad de memoria empleada.
Cuando le decía a Francesc que faltaba saber la memoria consumida
sabía de antemano que era difícil. Como mucho se podría estresar al
sistema para ver cómo se comporta ante la escasez de memoria.

La ejecución de python se hace sobre una máquina virtual, con memoria
que podemos presuponer inagotable. Esta máquina virtual, por su lado,
está implementada en C (CPython), aunque también la hay para JVM, CLR,
Parrot,... Estas implementaciones delegan (casi siempre) en el sistema
operativo, que es quien se apaña con el hardware para paginar y
resituar la memoria (grabar en disco depende de la gestión de la
memoria virtual que haga el sistema operativo).

Sin entrar en más detalles, el intérprete python no tiene ninguna
gestión de memoria propia. Para python, todo son objetos que pupulan
por ahí y de los cuales sólo contamos con una referencia para acceder
a ellos. En cuanto desaparece la referencia, el objeto deja de
existir. En cuanto a las funciones, se crea para ellas un "entorno de
ejecución" que sería el mundo restringido que sólo es visible desde
dentro de la función.

La máquina virtual mantiene estructuras de datos para almacenar los
objetos. Cuando el intérprete deja de referenciar un objeto, la
máquina virtual procede a liberar la memoria que ocupaba.

Por poner un caso, cuando creamos un generador/iterador se crea un
entorno de ejecución de modo similar a lo que sería crear una
instancia de una clase (llamadas "clausuras"). Los entornos de
ejecución se van intercambiando con el principal a medida que se va
ejecutando el código.

Entrando a analizar los algoritmos:

1) len([x for x in a if x.isdigit()])

Se crea una lista por compresión, Lo más costoso es el tiempo que se
tarda en obtener cada caráter de la cadena (for x in a). La
comprobación .isdigit() es bastante rápida ya que se realiza en C. El
cálculo de la longitud de la lista es instantáneo.

Estamos creando una lista intermedia que desaparecerá una vez obtenido
el resultado. Con memoria suficiente no hay problemas.

2) sum(1 for c in a if c.isdigit())

Se crea un iterador que recorre la cadena carácter a carácter, sin
necesitar almacenaje temporal. La suma se hace en C, por lo que es muy
rápida.

No emplea más memoria, pero tiene el incoveniente de estar conmutando
entre el entorno de ejecución principal y el del iterador. Este tipo
de conmutaciones es bastante dependiente del procesador, pero es
generalmente muy costosa en tiempo. Con muticore/multiprocesador
debería ir más rápido ejecutando en paralelo cada entorno en un
procesador; pero está demostrado que no suele ser así, gastando más
tiempo en sincronizar procesos que si se hubiera ejecutado
secuencialmente. Además en python se añade la problemática del GIL
(Global Interpreter Lock) que impide la ejecución en paralelo.

3) sum(a.count(c) for c in "0123456789")

Se parece bastante a la segunda solución. El .count() se hace en C,
por lo que es bastante rápido. La ventaja es que el iterador sólo se
ejecuta 10 veces, indepedientemente de la longitud de la cadena.


El hacerlo o no en una sóla línea de código es por prevenirse en
salud. Nunca se suele usar el comando 'del' para borrar una
referencia, por lo que es frecuente dejar que la referencia
desaparezca sola al retornar de la función o al acabar el programa.
Tal como dije, los objetos existen mientras sean referenciados, por lo
estos objetos están ocupan espacio incluso muchos después de que ya no
nos son útiles. Se puede decir que ya es casi una regla de estilo no
usar variables intermedias siempre que sea posible; pero en verdad que
no debería notarse mucho en cuestión de velocidad, ya que el código
bytecode a ejecutar será prácticamente el mismo.


> También está el uso de CPU, supongo que muy relacionado. ¿Son dos variables
> diferentes a controlar, el % uso de CPU y la cantidad de memoria RAM usada,
> o es lo mismo? ¿Puede ser que una de las soluciones propuestas en el hilo
> sea mejor en cuanto a uso de RAM pero peor en cuanto a uso de CPU?

"Siempre es más fácil optimizar código correcto que corregir código optimizado".

Cuando programes en python nunca pienses al principio en la velocidad;
ya habrá tiempo luego para optimizar. En cambio, la escalabilidad es
siempre un factor a tener en cuenta desde el principio. Muchas veces
no sabes la cantidad de datos que vas a tener que procesar, ni la
memoria o potencia disponibles. Ser conservador en el gasto de memoria
puede ayudar a crear aplicaciones más robustas.


Aún así, a pesar de todo lo dicho, python tiene sus propias
optimizaciones que pueden volverte un poco loco. Por ejemplo, el id de
los objetos de python los identifica como entidades únicas (es como si
fuera la posición de memoria que ocupa cada objeto en el intérprete).
Cuanta más memoria gastas, más grandes serán los ids que se van
asignando a los objetos. Es una forma de ver cómo vas de consumo de
memoria; pero te puedes encontrar con sorpresas como ésta:

>>> a=256
>>> b=256
>>> id(a)==id(b)
True
>>> a=257
>>> b=257
>>> id(a)==id(b)
False


Lo que aquí pasa es que python tiene creados siempre los enteros desde
el -5 al 256, independientemente de si se van a usar o no. Sería
memoria desperdiciada, pero ésta argucia ayuda a mejorar bastante el
rendimiento de bucles cortos así como el acceso a los elementos de una
lista. Por otro lado, la listas de enteros en este rango ocuparán
bastante menos memoria que si se usaran otros enteros. Esto da idea
que cuando se discute sobre la ventajas de usar xrange() frente a
range() no tenga ya tanto sentido si se van a usar rangos cortos.

Como ves, no es fácil dar una consigna a seguir. Si realmente tienes
un algoritmo que necesitas optimizar hazlo en C o pyrex.
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes