[bcn-pm] Complejidad de algoritmos

[Joaquin Ferrero]

El mié, 13-06-2007 a las 15:48 +0200, Enrique Nell escribió:
> ¿Conocéis alguna manera de realizar una estimación del tiempo que
> tardará en ejecutarse un algoritmo basada en la memoria requerida por
> las estructuras de datos de partida, la memoria RAM disponible y la
> velocidad del procesador? Sería algo así como hacer un benchmark
> aproximado a priori que permita, por ejemplo, dar al usuario de un
> programa la posibilidad de elegir ejecutar o no una función según el
> tiempo de ejecución estimado para los datos en cuestión.

Te falta una pata para formar la mesa: el sistema operativo.

Mira aquí, vete a la parte del programa de prueba y sorpréndete:
http://perlenespanol.baboonsoftware.com/foro/viewtopic.php?t=1645

Donde yo estoy manejamos grandes estructuras de datos (hashes y arrays a
múltiples niveles). Bueno, pues llega un momento en que Perl devora toda
la memoria y Windows comienza el swap, y de allí podemos irnos a tomar
el café, etc.

Yo sospecho que el problema es que, aunque yo le pido continuamente a
Perl que libere la memoria de las estructuras de datos temporales, esa
memoria no es devuelta al sistema por estar compuesta de millones de
pequeñas zonas de memoria reservada, y el sistema renuncia a
recuperarlas por ser un proceso costoso (creo que en Linux hay algo
parecido).

Al final, en algunas situaciones hemos tenido que usar DBM::Deep. Más
lento (no nos importa), pero el espacio ya es el del disco duro.

En procesos largos solemos poner barras de progreso basadas en
Smart::Comments (pero con mucha moderación, porque el cálculo de la
propia barra consume muchos recursos) Así al menos el usuario sabe más o
menos cuánto tiempo va a tardar en terminarse.

Yo creo que podrías resolver el problema guardando un histórico de
tiempos... y siempre y cuando las condiciones externas sean las mismas
(otros programas ejecutándose, otros usuarios trabajando en la máquina,
interrupciones externas del hardware, etc. etc).

En mi anterior trabajo en la universidad tardábamos 140 minutos en
procesar una imagen vía satélite. El jefe compró una máquina con dos
procesadores. Bueno, pues lanzando dos imágenes a la vez tardaba entre 4
o 5 horas. El problema estaba en que los procesos "competían" por el
acceso a la memoria y a los discos. Al final, se creo una cola de
procesado, y se bajó a 100 minutos. Más tarde se compró un cluster de 8
nodos y se consiguió bajar a menos de 20 minutos, pero porque cada nodo
procesaba una parte de la imagen (se dividió el problema).

-- 
JoaquinFerrero.com                 Linux User #109802
msn/jab explorer en jab.pucela.net    GPG/PGP 0x42DDB1FE