8 replies to this topic

[Delphius]

¡Hola a todos!

He estado un tanto alejado. Ya no me es tan fácil sentarme y darle el tiempo para pasarme por aquí.

No es un tema urgente, de hecho, no es para ahora... no tiene fecha ni urgencias. He estado debatiendo en mi tiempo libre sobre algunas maneras de como almacenar información que debe ser representada y abstraída en un array tridimensional en un archivo (no se requiere de base de datos).
Bien sabido es que para un array-1 lo directo es tener una lista así:

delphi

elemento1
elemento2
...
elementoN

En un array-2 las cosas se ponen un poquito más complicadas, pero igualmente el principio sigue siendo válido:

delphi

elemento11 elemento12 ... elemento1N
elemento21 elemento22 ... elemento2N
...
elementoM1 elementoM2 ... elementoMN

Naturalmente que deben hacerse los debidos controles que aseguren una correcta lectura de cada elemento y poder posicionarse en el lugar correcto. Este ejemplo es lo más breve y elemental. Se pueden dotar de ciertos mecanismos que permitan controlar el fin e inicio de item, como hasta incluso se puede preveer el inicio/fin de fila.

La pregunta es, como puede entenderse del título, ¿Y para un array-3?
¿Que propuestas considerarían?

He estado pensando en repetir el esquema array-2. Si entendemos por [coord1 >> P, coord2 >> M, coord3 >> N] entonces:

delphi

//Coord1 = 1
elemento111 ... elemento11N
...
elemento1M1 ... elemento1MN
//Coord1 = 2
elemento211 ... elemento21N
...
elemento2M1 ... elemento2MN
//Coord1 = P
elementoP11 ... elementoP1N
...
elementoPM1 ... elementoPMN

Aunque también he llegado a pensar que también podría ser válido disponer de tantos archivos como P tenga de modo que en cada archivo se tenga separada la información para cada coordenada.

El asunto es que lo que me preocupa son las reiteradas lecturas/escrituras al disco que se requerirán. Los valores P, M y N no serán muy chicos que digamos  (Aunque no necesariamente se cargue TODO el array tridimensional, sino que sería cargado por bloques. El asunto es que de por si cada bloque/sub-bloque es algo grande.

¿Que enfoques podrían concebir?
Otra posibilidad que estuve deliberando es, pensando en lo que es el rendimiento sobre I/O en disco, emplear otra estructura de datos (como intermedia quizá) que al parecer, y que supuestamente en teoría está pensada para trabajar de forma más amigable con el disco: árboles balanceados... concretamente BTree. Lo malo es que ahora me complicaría las cosas para ir de un enfoque árbol a un enfoque array-3.

Estoy aquí para escuchar sus alternativas y propuestas.

Saludos,

[Sergio]

Usa firebird -hay una version embeded sin instalacion y sin acceso por red, igual te sirve si no quieres instalar firebird- y una tabla con c1, c2, c3: integer; valor: double y le pones la clave primeria a c1,c2,c3 así evitas duplicados, y lo mas importante, zonas de ceros de tu matriz, si las hay, no ocupan espacio (matrices por bloques, diagonales, etc.)!

Luego puedes leer cubos dentro de la matriz a tu gusto, una auna con una SQL simple o todas de golpe con sqls mas trabajadas, y firebird se las arreglara para optimizar la busqueda en disco y usar sus caches, es buena en eso!

Si prefieres texto plano y suponiendo matrices muy grandes, haz un fichero por cada c1-c2 y dentro pones esa linea completa, eso deberia bastar si no tienes tamaños excesivos y es relativamente sencillo luego de leer.

Otro truco es usar un gran fichero de texto donde los numeros vayan siempre en un formato fijo, digamos 10 cifras significativas mas el punto, de forma que una posicion dada c1, c2, c3 se pueda calcular su posicion exacta en el fichero sabiendo los valores maximos en cada dimension (el tamaño de la matriz, vamos), de esa forma puedes abrir el fichero como stream y saltar al byte exacto donde empieza el valor a leer.

El problema es como se comporte esto con tamaños grandes, aqui dependes de las caches que use el sistema de ficheros, nada buenas por cierto, o bien pasar todo el stream de fichero a uno de memoria y usar este, siempre que tengas ram sera 1000 veces mas rapido que tratar con ficheros.

Yo de cabeza tiraria para firebird, te permite incluso hacer uso de los datos desde varios pc simultaneamente y esas cosas.

[Delphius]

Hola Sergio,
¡Muchas gracias por tu aporte!
En principio el tema de usar base de datos, aún cuando fuera la versión embeded de Firebird, estaría descartado. No porque no sea bueno sino para no complicar y estar cargando de más cosas al proyecto. La intención es hacerlo de la forma más directa posible y no tener que recurrir a intermediarios.
La opción de almacenar en cada fichero la información para el plano (c1, c2) y de ese modo tener tantos como la dimensión de c3 hayan es similar a una de las que estuve barajando.
Lo de hacer de tamaño fijo es un plus que no había considerado... no al menos de esa forma. Si estuve pensando en que si se puede definir alguna estructura propia que limite donde comienza cada fila/columna1/columna2 se podría hacer un especie de lectura al estilo "Buffer".
Este tema se que lo debo ir puliendo... aún me queda por ver otras cuestiones técnicas de otras partes del proyecto que condicionarán en mayor o menor medida a esto.
En la medida en que avance sobre cada parte podría ir refinando mis ideas... mientras, creo que necesito ir viendo cada cosa por separado y no de forma integral porque sino se me hace mucho lio.

Saludos,

[poliburro]

¿Amigo mio, has considerado usar archivos binarios? ya sabes archivos donde se hace el volcado de un record.

[Delphius]

¿Amigo mio, has considerado usar archivos binarios? ya sabes archivos donde se hace el volcado de un record.

Hola Poli,
¿Te refieres a algo como esto?:

delphi

type
  TCelda = record
    X, Y, Z: integer;
    Valor: TValorCelda;
  end;
 
var
  Archivo: file of TCelda;

Pues... la verdad es que no lo pensé de esa forma.
En lo máximo que he considerado es la posibilidad de que se aplique una especie de compresión. Es decir que en lugar de almacenar todos los valores uno a uno, comprimirlos... algo parecido a la compresión básica de imagen pero a una escala 3D. De este modo se podría reducir el tamaño de los archivos... aunque el proceso de compresión/descompresión podría jugar en contra y tener una merma en el rendimiento.

Saludos,

[Sergio]

En general tratar con matrices grandes tiene sus "trucos", yo tengo cierta esperiencia, y creo que estas son las cuestiones a plantearse:

1) ¿Te cabe la matriz completa en memoria?

Si cabe, fin del problema, un array de doubles y listo, a fichero de una tacada.

2) ¿Que "forma" tienen las zonas que vas a necesitar cargar de un golpe? (zonas cuadradas, perdón cúbicas, o bien planos completos, o lineas completas... ).

3) ¿Tiene alguna estructura especial esa matriz? Es decir, si tienes amplias zonas en blanco (a cero), o si solo está rellena la diagonal, o una banda alrededor de la diagonal, o si tiene alguna simetría (M(i,j) = M(j,i)), etc.

4) Si no tiene estructura especial, pasamos a la siguiente: ¿Es muy densa o muy poco densa? Si fuese al azar (sin estructura) pero tienes con valor solo el 1% de las posiciones, no te interesa guardar todos esos ceros, es mejor un fichero donde solo se hable de casillas con valore y se suponga que el resto está vació.

En función de estas cuestiones te vendrá mejor una forma u otra de tratar con la matriz, en el peor de los casos solo te quedaría usar FireBird, pero eso es en el peor de los casos solamente!

[Delphius]

En general tratar con matrices grandes tiene sus "trucos", yo tengo cierta esperiencia, y creo que estas son las cuestiones a plantearse:

1) ¿Te cabe la matriz completa en memoria?

Si cabe, fin del problema, un array de doubles y listo, a fichero de una tacada.

El arreglo tridimensional completo, y real, no. Pero como necesito ir trabajando por bloques de éste es que si es posible manejarlo de esta manera reservando cierta cantidad de bloques y reusurlos para cargar en él otras las otras partes o bloques "no visibles" cuando requiera.

Justamente el dilema está en como llevar cada bloque a archivos. Por diseño necesariamente voy a requerir de varios archivos.

2) ¿Que "forma" tienen las zonas que vas a necesitar cargar de un golpe? (zonas cuadradas, perdón cúbicas, o bien planos completos, o lineas completas... ).

No se si entiendo totalmente tu pregunta. Cada bloque ha de ser un cubo, y creería que la manera más fácil de administrar el arreglo es justamente verlo como un cubo formado por cubos. De esta forma podría obtener la representación tridimensional de cada uno para poder trabajar.

3) ¿Tiene alguna estructura especial esa matriz? Es decir, si tienes amplias zonas en blanco (a cero), o si solo está rellena la diagonal, o una banda alrededor de la diagonal, o si tiene alguna simetría (M(i,j) = M(j,i)), etc.

4) Si no tiene estructura especial, pasamos a la siguiente: ¿Es muy densa o muy poco densa? Si fuese al azar (sin estructura) pero tienes con valor solo el 1% de las posiciones, no te interesa guardar todos esos ceros, es mejor un fichero donde solo se hable de casillas con valore y se suponga que el resto está vació.

Si y no. En buena parte no tiene estructura sino que es generada por azar pero si se detectarán ciertas áreas en blanco. En ciertos lugares será más o menos denso.
Pero en una escala macro, si se examinara la matriz en su totalidad y entendiéramos al cubo formado por cubos (como si fuera el cubo de rubik pero con lados de miles de cubos), se vería que las caras superiores estarían un 50% densas, y perdiendo la densidad en la medida que se acerca a la "superficie".
Por otra parte las caras inferiores estarían entre un 75 a 100% densas, aumentando la densidad en la medida en que baja al fondo.

¿Conoces algo sobre el ruido Perlin? Pues yo lo llevaré al plano 3D, y si sabes para que se lo suele usar a dicho ruido seguramente ya te haces una idea de mis objetivos

Justamente por esto es que me he estado pensando en que es posible generar cierta compresión ya que habrá muchas posiciones en donde será "nulo" o vacio y por tanto no habría necesidad de llenar o almacenar en disco esto.
Además estuve pensando en que se podría complementar también con una compresión sencilla que se utiliza(ba) en imagen: básicamente se cuenta la secuencia de un valor hasta llegar a uno diferente, luego en lugar de almacenar toda las secuencias se almacena el par (cantidad, valor). Es decir que si leemos algo como 1110001101 queda como 3130211011 aunque no se hasta que punto podría ser rentable (y viable) este nivel de compresión a una escala tridimensional.

El punto es que el valor para la posición (x,y,z) de por si ya posee su propia estructura y diseño. Básicamente dicha posición (x,y,z) hace a un objeto. Por tanto debo tener especial cuidado en tratar la estructura que hace al objeto en cuestión. Estoy deliberando que tan amplia será la rama de jerarquía de clases para esta hipotética clase T3DMapObject para ver que impacto tendrá en dicho archivo.
La última que estuve pensando es en separar por un lado los archivos que dan forma al modelo tridimensional y por el otro lado los archivos que almacenen los datos de cada objeto respetando su estructura. De este modo tendría en estos el "identificador" del objeto.

Muchas gracias Sergio por darme un poco más de luz. El escribir esto me está ayudando a repasar algunas cosas.

Saludos,

[Sergio]

Tu necesitas esto para "comprimir" esa niebla usando que hay grandes "vacios" dentro: http://en.wikipedia.org/wiki/Octree

De hace tiempo se usa en 3D para por ejemplo detectar qué objetos intersectan con un rayo o con otro objeto: primero divides tu espacio cubico grande en 8 subcubos, numerados del 1 al 8, como un cubo de rubik de 2x2, y marcas aquellos por los que pasa tu rayo o bien intersecta tu objeto o lo que sea que andes haciendo, serán 3 de los 8 subcubos a los sumo, y en esos 2 o 3 repites y obtienes 2 o 3 sub-sub-cubos aún mas pequeños, etc... al final tienes N cubos de un cierto tamaño minimo (la distancia de Planck?) donde realmente guardas el valor de ese ruido.

Es una manera eficiente de empaquetar informacion 3D ahorrandote los ceros de las zonas vacias, aunque estas tengan formas raras, y te vale para grabar incluso en XML: Empiezas con una seccion con 8 sub-secciones numeradas del 1 al 8, de esas 8 no das de alta en tu fichero las que esten vacias, y en cada una no-vacia repites y tienes otras 8 sub-sub-secciones, algunas vacias que no mencionas (no les abres seccion en tu XML) etc... y al final, encuentras una seccion que dentro no tiene mas sub-secciones... en ese caso llegaste al cubito menor, que en lugar de más cubitos tiene un valor con tu "ruido" pero SIN coordenadas, porque la secuencia de indices de cada sub-cubo te da la posición: si empiezaste saltando el sub-cubo 5, de aquí el 3, luego al 1... esa secuencia te da las coordenadas finales del cubo.

Otra manera de sacarle provecoh a esta estructura de arbol es poner en cada nodo la media de ruido de sus 8 subnodos, lo cual rellenarias recorriendo el arbol "marcha atras" o recursivamente. Esto te perimte estudiar la nube a diferentes escalas, podrias dibujar la nube aproximada, y al hacer zoom refinar la representacion llegando mas profundo en la estructura de nodos y subnodos.

[Delphius]

Hola Sergio,
Hace un tiempo ya estuve investigando sobre el uso de Octree 
Si bien es una técnica muy empleada, y entre sus usos como indicas, permite determinar si hay colisión entre los objetos móviles no siempre puede resultar en lo más viable.
La estructura tridimensional que estuve evaluando se la conoce como damero. En este caso de 3 dimensiones.
Todavía estoy recabando información sobre octree vs damero. Y todos los factores que hacen al proyecto tienen sus indicendias a favor o en contra para ambos tipos de planteos.
Lo difícil del tema es lograr trasladar ya sea cualquiera de estas estructuras lógicas a algo físico.

No he considerado el uso de XML (más que nada debido a que no me he interiorizado lo suficiente en el área y sabiendo que hoy en día a un XML lo abres hasta con cualquier cosa y se lo podría violar o meter la pata enormemente), aunque admito que por su diseño puede ser útil y ofrecer ciertas ventajas al momento de almacenar información del tipo árbol.

Saludos,