11 respuestas en este tema

[Delphius]

Hola a todos,
Estoy con la cabeza quemada... y pensé que quizá ustedes me podrían ayudar a restaurar neuronas.
Me está fallando la teoría y la práctica de Arquitecturas de Computadores  ... y debido a cierto proceso delicado (por la cantidad de memoria reservada final que voy a utilizar) que estoy llevando a mano sobre RAM es que me pregunto ¿Que es más delicado, en términos generales, leer o escribir de/sobre la RAM? ¿O considerarían dejarlo a lo salomónico y que es indiferente?

No digo Disco porque ese si que es más costoso y lo mio es operación directa sobre la RAM.
El proceso no viene al caso, después de todo se resume en lecturas y escrituras, y demás operaciones en el medio.

El asunto es que se le pueden concebir en el medio diversos algoritmos más o menos invasivos dependiendo de lo que se priorice (velocidad vs I/O e intercambios).

Esto les pregunto porque justamente tengo algoritmos que priorizan más la velocidad de las operaciones en general y que evitan en lo posible tener que estar intercambiando datos innecesariamente. Como así también que tengo otros que si bien hace más operaciones I/O para intercambiar y son menos lentos ofrecen más "estabilidad numérica" en los resultados finales que los otros.

La lectura obviamente se debe proceder y no se puede obviar. Más en términos de escritura es lo que afecta a la ecuación. Digamos que tenemos 2 tipos*:
Tipo 1: los que evitan lo más posible el intercambio de datos (escritura y/o reescritura) pero que no ofrecen total estabilidad numérica al final. Aunque esto de la "inestabilidad" no es demasiado problema ya que está controlado por un factor de tolerancia y precisión y a los resultados finales no le es gran cosa (teóricamente    )
Tipo 2: los que garantizan más estabilidad pero que tienden a ser menos lentos y en ocasiones hacen más intercambios.

*En realidad se podrían concebir más... hasta algunas intermedias o que de forma más o menos dinámica elijen uno u otro extremo en función de algunas cosas.

Tal intercambio no es más que el simple:

delphi

Auxiliar := V[PosA];
V[PosA] := V[PosB];
V[PosB] := Auxiliar;

y/o:

delphi

Auxiliar := M[PosiA, PosjA];
M[PosiA, PosjA] := M[PosiB, PosjB];
M[PosiB, PosjB] := Auxiliar;

A fin de "desempatarme" me preguntaba si es que ustedes me podrían aclarar. Comparando en términos generales (y si... se que esto también depende del tipo de RAM) ¿que es más costoso? ¿O podría asumir que son indiferentes?

Por ahora a la vista del ojo, y con pequeña cantidad no distingo gran cosa... me pregunto si para grandes cantidades las cosas cambian (o si deberían cambiar).
Lo que hago es trabajar con varios vectores y matrices. Los someto a muchas operaciones, y de las más variadas. Y la parte delicada, al momento es justamente equilibrar tanto la rapidez de mis algoritmos no sólo en notación-O sino en que también sea lo más "amigable" con el hardware y que garantice buenos resultados obviamente. En otras partes de todo el proceso no tengo la "dicha" de debatirme. Se hace de una manera o esa... Más se llega al punto en donde ahora, para el momento de ordenar o clasificar la información hay variadas técnicas y todo se resume en si intercambiar al máximo, al mínimo, "a lo medio"... en fin.

La otra posibilidad, también salomónica, que estuve barajando es disponer de ambos tipos y dejar que se elija el tipo de algoritmo más apropiado según alguna configuración del sistema. Pero antes que nada, quisiera escuchar sus opiniones.

Saludos,

[santiago14]

Recuerdo que para mi tesis en la Universidad tuve un dilema parecido, había que mostrar gráficas y hacer muchos cálculos y la máquina sacaba la lengua.
En mi caso, luego de muchos golpes contra la RAM y los discos, fue optar por optimizar los códigos fuente (Álgebra lineal de por medio) y quedarme con la velocidad y arriesgar un poco de estabilidad en lugar de los mas lentos y estables. La cosa salió bien, me dieron el título.

Hacer intercambios y movimientos como esos era poco mas que la muerte. Me iba a tomar algo y lo dejaba al programa en lo suyo y, cuando volvía, podía ver la matriz de MJoules que necesitaba.

Cuando empecé a cambiar las cosas y buscar mas velocidad, los resultados fueron mejores. Solamente tenía tiempo para ir hasta el baño  y volver y la matriz estaba lista. Eso sí, el uso de la RAM era a full.

Como corolario debo decir que alguna que otra vez me dió un error de I/O de RAM (intentar pisar partes reservadas, gastarme toda la memoria, etc.) pero esa "es otra historia..."

Un saludo.

[Delphius]

Hola Santiago,

Te agradezco que hayas compartido tu experiencia conmigo.
Hasta ahora no me he visto con problemas en la memoria. Afortunadamente. Espero no tenerlos.

Si recuerdo que en un trabajo para Sistemas Expertos, hace ya años, tuve algunos inconvenientes con memoria reservada... mientras implementaba A*. Manejé la lista a la vieja escuela... con punteros y todo. El problema estaba en que mi algoritmo se ejecutaba tan rápido que no daba respiro al equipo a que ante un New() me reservara la memoria para el nodo a utilizar. En ese entonces la solución pasó por añadirle un ProcessMessages y listo. La maravilla de Delphi y su compilador tan excelente que optimiza todo para hacerlo ultra veloz.

Desde entonces tomo la precaución de que a las partes críticas de mis algoritmos de añadirle un ProcessMessages para darle algo de tiempo y respiro ante la duda.

Actualmente tengo un algoritmo de base cuya complejidad en notación-O es constante de O(n²). Me dí una muy buena alegría al ver que al adaptarlo al esquema matricial aún conserva el mismo orden. Este algoritmo reduce al mínimo los intercambios. En cambio tengo otro algoritmo de base que también es O(n²) (en el mejor caso O(n)) que al adaptarlo se va hacia O(n³). Éste no me garantiza mínimos intercambios, en promedio hace n² ,pero los resultados son estables.

Mi primera intuición me dice que me incline por la rapidez y mínimo intercambio. Aún me falta analizar otros posibles algoritmos adaptados al esquema matricial. Lo que si me estoy diciendo de que aquellos algoritmos que requieran de memoria extra descartarlos. Por naturaleza del problema la memoria es un recurso vital que no puedo desperdiciar.

Saludos,

[escafandra]

La wficiencia de los intercambios de datos en RAM dependen de la naturaleza de los datos intercambiados. Para ordenar datos, por ejemplo, cadenas, ¿qué es mas rápido, ordenarlas intercambiandolas u ordenar los punteros que las apuntan?  Evidentemente, lo segundo.


Saludos.

[Delphius]

La wficiencia de los intercambios de datos en RAM dependen de la naturaleza de los datos intercambiados. Para ordenar datos, por ejemplo, cadenas, ¿qué es mas rápido, ordenarlas intercambiandolas u ordenar los punteros que las apuntan?  Evidentemente, lo segundo.


Saludos.

Gracias Escafandra por traer de tu sabiduría.
Los datos son del tipo double e integer.
Los mismos están almacenados en matrices y/o vectores dinámicos. Lo de siempre:

delphi

type
  IntVector = array of integer;
  DblVector = array of double;
 
  IntMatrix = array of IntVector;
  DblMatrix = array of DblVector;

¿Tu sugieres que en lo posible trate de aprovechar el uso de punteros?

Saludos,

[escafandra]

¿Tu sugieres que en lo posible trate de aprovechar el uso de punteros?

Mover un puntero es mover un dato de 32 ó 64 bits. Si eso supone un movimiento menor, es preferible. Por otro lado, los punteros te permiten varios órdenes al mismo tiempo sin tocar los datos ni el orden original, pero añaden cierta complejidad.

Todo depende. Pero, en general, la aritmética de punteros es mas rápida que la de índices y por supuesto que los grandes intercambios de datos.


Saludos.

[Delphius]

Mover un puntero es mover un dato de 32 ó 64 bits. Si eso supone un movimiento menor, es preferible. Por otro lado, los punteros te permiten varios órdenes al mismo tiempo sin tocar los datos ni el orden original, pero añaden cierta complejidad.

Todo depende. Pero, en general, la aritmética de punteros es mas rápida que la de índices y por supuesto que los grandes intercambios de datos.


Saludos.

Ummm...
¿Lo que comentas llegaría a algo parecido a lo que hemos hablado en aquella ocasión que preguntaba por el uso de GetMem?

Porque al final he estado directamente inclinado por trabajar con SetLength y no pelearme con los punteros.
Ese ejercicio me resultú muy esclarecedor y como tu decías al final lo debía considerar para algo más crítico y donde la velocidad era algo más primordial.

En esta ocasión los procesos que he estado llevando mantienen una buena estabilidad y no me ha parecido necesario llegar a más bajo nivel. La mayor parte del proceso las operaciones son relativamente sencillas, fáciles y no se observa gran uso intenso, salgo una que es más intensiva y en verdad crítica para asegurar que se tenga mucha aproximación numérica. Esto me ha llevado a que opte por una vía que si bien no es la más rápida garantiza absoluta precisión numérica y excelentes resultados.

Hasta ahora lo que me viene dando resultados es que si hago rápido una parte, en otra le quito un poco. Voy compensando ambos factores a medida que entro y salgo de cada subproceso. El punto es que el siguiente subproceso al que me enfrento es ordenar dicha información. Y como sabemos, la memoria en este escenario es un bien escaso y hay variadas maneras de encararlo.
A la vista de este escenario ¿que sugieres tu?

Saludos,

[escafandra]

Una parte estaría en optimizar los procesos matemáticos y la precisión que pretendes alcanzar. Recuerdo una aplicación que escribí hace años sobre el famoso "Ojo Mágico". Se trataba de escanear una imagen renderizada para profundidades 3D "Z".  Debía solucionar un sistema de 2 ecuaciones trigonométricas por cada punto de imagen, algo tremendamente lento. Lo suntituí por un algoritmo repetitivo aproximativo al estilo "cuenta de la vieja". El cambio de rendimiento fue espectacular. Aquella aplicación usaba asm para optimizar el acceso a la memoria de pantalla y el resto era "C".

La otra parte, la del ordenamiento de datos depende del número de órdenes distintos y del tamaño de datos. Ten en cuenta que en un sistema de 32bits el dato ideal es de 32bits, así como en uno de 64 bits será su homólogo. Los punteros siguen esa norma, pero no son los únicos.
Si requieres varios órdenes al tiempo los punteros te darán ventaja y ahorraran memoria al no requerir copias de todos los datos.

Al final te tocará probar varias opciones y tomar tiempos para poder decidirte. No vas a tener una regla de oro. O complicarte el código pata ganar velocidad a bajo nivel o conformarte si la anterior opción no ofrece grandes ventajas.

Finalmente, ten en cuenta que en windows una app dispone del 100% de la memoria del sistema real o virtual. Los procesos que agotan la RAM física disponible, tiran de memoria virtualizada en disco, al fin y al cabo, toda la memoria está virtualizada por windows. Quiero decir que depende de la RAM total del sistema y de procesos abiertos junto con tu programa.

Saludos.

[Delphius]

Hola,
De por sí mis algoritmos ya están optimizados. Al menos los que ya los tengo hecho. El último proceso como dije no es del todo el más veloz pero lo que lo caracteriza es que ofrece resultados muy exactos. Hay algoritmos más "avanzados" pero tras algunas revisiones y análisis que se estuvieron llevando demuestran que no tienen tanta precisión. Y todas las fuentes que estuve consultando se inclinan hacia el algoritmo que utilizo.
El algoritmo que uso es de naturaleza iterativa y está programado para aceptar y manejar tolerancia de error. Todo esto lo tengo controlado.
Se que se lo puede optimizar más, por medio de computación paralela, pero ya es demasiado para mi.
Mis pruebas me tienen muy satisfecho... llega a una muy buena convergencia y más rápido de lo que me imaginaba.

Lo que comenta de órdenes no comprendo. ¿A que te refieres?

Lo de ir probando opciones lo estoy haciendo. Voy a probar entre 4 o 5 algoritmos. El asunto es que los algoritmos bases están pensados para listas o arrays simples. En mi caso debo ampliarlos para llevarlo a cabo tanto a vectores y matrices ¡en simultáneo!. Con lo cual se aumenta la complejidad en un grado más (en promedio). Aunque también depende del tipo de algoritmo... por ejemplo, uno de base que tengo que minimiza los intercambios posee un O(n²) constante y mi adaptación al esquema matricial también. Otro algoritmo que también es O(n²) (un poco más lento en términos T(n) que el anterior) al adaptarlo se va a O(n³).
Los que me quedan por evaluar son los de órdenes inferior... O(n log n) a ver a cuanto se van. El asunto es que algunos ya requieren de más memoria, son recursivos y no garantizan intercambios mínimos. Y no si se vale demasiado la pena arriesgarme a más uso de memoria y pasar recursivamente matrices (aunque creo que he logrado ver el modo de que esto se haga in-place).

Estuve buscando fuentes al respecto y no encontré algo que me aclare el punto. Sólo una vaga referencia a una parte de una biblioteca científica de GNU que implementa justamenta el algoritmo que minimiza intercambios, el que ya tengo implementado.

Mi idea con este hilo es llegar a una mejor visión de que es más costoso, si leer o escribir en RAM para ver si vale la pena en una de esas probar algo más rápido sabiendo que haga mayores intercambios.

No me he preocupado en los procesos anteriores sobre este punto porque precisamente no puede evitarse el estar leyendo y escribiendo. La operatoria o se hace de esa forma o no se hace. Sos pasos precisos.
Es justo ahora cuando ya los datos están procesados donde puedo jugar con la clasificación y decidirme.

EDITO:
Dispongo de 2GB de RAM; bueno...  en la práctica un poco menos debido a lo que se come el SO. Creo que me aguanta para en promedio 2 o 3 matrices... y el resto (si me hace falta) que se vaya a la virtual.

Saludos,

[escafandra]

Por supuesto que tus algoritmos de ordenación deben ser en RAM y optimozando las lecturas/escrituras. Pero partiendo de que eso ya está conseguido el uso de punteros es una opcion a valorar y es la que yo tomaría, pero con los determinantes que te comenté.

Lo de los varios órdenes es en el caso que requieras ordenar los datos de forma diferente para a acceder a ellos de forma simultánea.

Los algoritmos recursivos pueden enlentecer.

Piensa la posibilidad de usar threads.

Perdona mi torpeza a la hora de escribir, lo hago desde mi smart pues estoy de vacaciones y no dispongo de PC.

Saludos.

[Delphius]

Gracias Escafandra por tus sabias palabras.
Seguiré viendo mis algoritmos y determinaré la viabilidad de ir a por un diseño basado en punteros.

Se que en parte los algoritmos recursivos pueden elentecer un poco las cosas. Algo se come por la pila y las llamadas. Se que no en todas las ocasiones es viable meterse en estos métodos.
Ahorita estoy estudiándolos y ver cómo llevarlos a un diseño matricial y en como se comportarán.

¡Lo de utilizar Threads se me olvidó! Quizá sea una buena alternativa para este caso. Y ahora que recuerdo creo que había un ejemplo justo en la carpeta demos.
Muy posiblemente me decante por esta vía.

¡Que tengas unas muy buenas vacaciones amigo! ¡Disfrútalas!

Saludos,

[Delphius]

Hola a todos,
Vengo a actualizar este hilo.
Después ya de un buen tiempo de prueba y análisis estoy en condiciones de decirles que a mitad de camino ya estuve viendo que algoritmo era el ganador.

Como les comenté anteriormente estoy implementando algoritmos de ordenamiento o clasificación. El primer pensamiento por el que cualquiera se iría es emplear QuickSort y pasar por caja. Para el contexto al que estoy sometido no es tan sencillo... no se trata de un vector de tamaño n simplemente. En mi contexto tengo un vector de tamaño n y además una matriz de orden n (o tamaño nxn) ¿Para qué? Pues elemental: almacenar autovalores y autovectores. Existe por tanto una correspondencia 1 a 1. Esto implica que cuando se ordene los autovalores también debe hacerse sobre los autovectores.
Si en el esquema tradicional pensábamos en un arreglo de tamaño n, ahora estamos ante una dupla {n, n x n}. Se podría verlo como si fuera una lista de n³ elementos.
Viendo esa potencia con más razón dirían que se vaya por QuickSort, pero saben que... ¡No es una buena idea! ¿Porqué?
Porque si bien la elegancia de QuickSort radica en tener un O(n log n), en este nuevo esquema al tener que estar desplazando tanto el vector como la matriz en simultáneo hace que se pierda la bondad del log(n) que tiene el haber "partido" a ambas.

Les dejo una tabla que resume todo lo que he probado:

delphi

+---------------+-----------+-----------+-----------+-----+-----+------------------+-------+
|               | Complejidad                       | Me- | Es- |                  |       |
| Algoritmo     +-----------+-----------+-----------| mo- | ta- | Intercambios     | T(n)  |
|               | Mejor     | Prom      | Peor      | ria | ble |(promedios)       |       |
+---------------+-----------+-----------+-----------+-----+-----+------------------+-------+
| BubbleSort    | n^2       | n^3       | n^3       | 1   | si  | aprox (n^3)/4    | 7n^3  |
| HeapSort      |(n^2)log(n)|(n^2)log(n)|(n^2)log(n)| 1   | no  | aprox (n^2)log(n)| -     |
| InsertionSort | n^2       | n^3       | n^3       | n+1 | si  | aprox (n^3)/4    | 36n^3 |
| QuickSort     | n^2       | n^2       | n^3       | 1   | no  | aprox (n^2)log(n)| -     |
| SelectionSort | n^2       | n^2       | n^2       | 1   | no  | = n^2            | 14n^2 |
+---------------+-----------+-----------+-----------+-----+-----+------------------+-------+

Como puede verse se destaca fuertemente un campeón: SelectionSort, aún cuando QuickSort demuestra tener un valor de c*O() inferior las pruebas indican que se degrada y no vale la pena arriesgarse a que se den las mejores condiciones siempre como para que le gane.
Y en vista a que si bien pueda ser poco frecuente que se diera el peor caso en QuickSort, SelectionSort en cambio se mantiene constante y reduce al mínimo posible (y por tanto un valor exacto y conocido) la cantidad de intercambios.
Los valores de T(n) que se ven aquí ilustran a modo de estimación una posible mejor comparación (algo cercana para hallar los posibles valores de c) de los algoritmos de órdenes cuadráticos (en su versión tradicional).
A todos los tengo en su versión in-place. No he probado los algoritmos que requerían de más memoria o que necesitaban de explícita recursión.
HeapSort me ha costado analizarlo. Pensé en un primer momento que podría llegar a igualar en O() a QuickSort y mantenerse en O(n^2) pero al ver que ya dentro del SiftDown no había modo de bajarlo de un O(n*log(n)), al repetirse n veces si o si se llegaba al n²log(n).
A pesar de que HeapSort resultase tener un leve peor desempeño que QuickSort me ha encantado como una segunda alternativa (a futuro, cuando amplie mi biblioteca científica)... para cuando (en algún caso extremo) en que se pretendiese aumentar n a valores más grandes.
HeapSort tiene una complejidad computacional uniforme, y está en el "medio" de entre los O(n²) y los O(n³). El otro motivo por el cual lo usaría es que con unas pocas modificaciones debido a su diseño HeapSort es capaz de extraer a velocidades cercanas a O(n²) los k (para todo k < n) autovalores y sus autovectores mayores. Algo muy útil en ciertas operaciones relacionadas con la estadísticas.

Si bien SelectionSort en la dupla {autovalor, autovector} quizá tiene una menor perfomance (casi del 50% de deterioro) que si fuera solamente en un vector, lo mismo o en forma casi similiar les sucede al resto de los algoritmos. Con lo cual cada algoritmo conserva sus ratios de pérdida. Por ejemplo, es lo que le sucede a QuickSort... su pérdida del 50% y su bondad de rapidez para el caso lleva a que se acerque en forma asíntota a los de SelectionSort.

También he pensado (en esta última semana) en una variante de no hace el ordenamiento en simultáneo y en su lugar hacer el ordenamiento de los autovalores y almacenar temporalmente la posición a las que les correspondían y en base a este índice adicional poder realizar el intercambio definitivo. Algo similar a lo que hace CountingSort. Pero me he dado cuenta de que esto llegaría a los mismos valores de asíntota que si lo hiciera todo junto:

1) Ordenar el vector de autovalores: O(n*log(n)) y almacenar en un vector adicional los índices para hacer la correspondencia.
2) Por cada autovalor mover su autovector a la posición correcta: O(n²)

La complejidad computacional del algoritmo es Max( O(n*log(n)), O(n²)) = O(n²)

Por tanto la mínima expresión posible a la solución tiene esta asíntota y por tanto no tiene sentido intentarle ganarle. No se porqué no he sido capaz de aplicar este razonamiento desde el principio.   

Puedo dar por concluído el tema.

Saludos,