En partes anteriores (, ) hablamos de los globales como árboles, en esta parte examinaremos los globales como arreglos dispersos.
es una variedad de arreglo en la cual la mayoría de los valores toma el mismo valor.
En la práctica, a menudo se encuentran arreglos dispersos tan grandes que no tiene sentido ocupar memoria con elementos idénticos. Por lo tanto, tiene sentido implementar arreglos dispersos de manera que no se gaste memoria en el almacenamiento de valores idénticos.
En algunos lenguajes de programación, los arreglos dispersos están incluidos en el propio lenguaje, , . En otros lenguajes de programación, hay bibliotecas especiales que permiten implementarlos. Para C++ — y otros.
Los globales son buenos candidatos para la implementación de arreglos dispersos porque:
- Almacenan valores solo de nodos específicos y no almacenan valores indefinidos;
- La interfaz de acceso al valor de un nodo es extremadamente similar a cómo se implementa el acceso a un elemento de un arreglo multidimensional en muchos lenguajes de programación.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global es una estructura bastante de bajo nivel para almacenar datos, por lo tanto, tiene características de velocidad excepcionales (desde cientos de miles hasta decenas de millones de transacciones por segundo, dependiendo del hardware, véase )
Dado que el global es una estructura persistente, tiene sentido hacer arreglos dispersos sobre ellos cuando se sabe de antemano que el volumen de memoria RAM será insuficiente.
Una de las propiedades de las implementaciones de arreglos dispersos es la devolución de algún valor por defecto si se accede a una celda indefinida.
Esto se puede implementar utilizando la función en COS. En este ejemplo se considera un arreglo tridimensional.
SET a = $GET(^a(x,y,z), defValue)¿En qué tareas se requieren arreglos dispersos y cómo pueden ayudar los globales?
Matriz de adyacencia (conectividad)
se utilizan para representar grafos:
Es evidente que cuanto más grande es el grafo, más ceros habrá en la matriz. Si, por ejemplo, tomamos un grafo de red social y lo representamos en forma de matriz similar, casi completamente consistirá en ceros, es decir, será un arreglo disperso.
Set ^m(id1, id2) = 1
Set ^m(id1, id3) = 1
Set ^m(id1, id4) = 1
Set ^m(id1) = 3
Set ^m(id2, id4) = 1
Set ^m(id2, id5) = 1
Set ^m(id2) = 2
....
En este ejemplo, almacenamos en el global ^m la matriz de conectividad, así como el número de aristas en cada nodo (quién es amigo de quién y el número de amigos).
Si el número de elementos en el gráfico no supera los 29 millones (este número se toma como el producto de 8 * ), hay una forma aún más económica de almacenar tales matrices: las cadenas de bits, ya que en su implementación se optimizan de manera especial los grandes espacios vacíos.
Las manipulaciones con cadenas de bits se realizan mediante la función .
; establecer un bit
SET $BIT(rowID, positionID) = 1
; obtener un bit
Write $BIT(rowID, positionID)
Tabla de transiciones de autómata finito
Dado que el gráfico de transiciones de un autómata finito es un gráfico ordinario, la tabla de transiciones de un autómata finito es la misma matriz de adyacencia de la que se habló anteriormente.
Autómatas celulares
El autómata celular más conocido es , que debido a sus reglas (cuando una célula tiene muchos vecinos, muere) representa un arreglo disperso.
Stephen Wolfram considera que los autómatas celulares son una En 2002 publicó un libro de 1280 páginas titulado "A New Kind of Science", donde argumenta ampliamente que los logros en el campo de los autómatas celulares no son aislados, sino bastante robustos y tienen gran relevancia para todas las ramas de la ciencia.
Se ha demostrado que cualquier algoritmo que sea ejecutable en una computadora se puede realizar mediante un autómata celular. Los autómatas celulares se utilizan para modelar entornos y sistemas dinámicos, para resolver problemas algorítmicos y para otros fines.
Si tenemos un inmenso campo y necesitamos registrar todos los estados intermedios de un autómata celular, tiene mucho sentido utilizar globales.
Cartografía
Lo primero que me viene a la mente cuando se habla de utilizar arreglos dispersos son las tareas cartográficas.
Por lo general, hay mucho espacio vacío en los mapas. Si se representa el mapa como grandes píxeles, el 71% de los píxeles de la Tierra estarán ocupados por el océano. Arreglo disperso. Y si solo se representan las obras de manos humanas, habrá más del 95% de espacio vacío.
Por supuesto, nadie guarda mapas en forma de arreglos rasterizados; se utiliza representación vectorial.
Pero, ¿qué son los mapas vectoriales? Es un marco que consiste en puntos, polilíneas y polígonos.
De hecho, una base de datos de puntos y las conexiones entre ellos.
Una de las tareas más ambiciosas de mapeo es la misión de mapeo de nuestra galaxia con el telescopio Gaia. En términos figurativos, nuestra galaxia, al igual que todo el universo, es un vasto y escaso array: enormes espacios vacíos, donde hay pequeños puntos raros: estrellas. El espacio vacío constituye el 99,999999…….%. Para almacenar el mapa de nuestra galaxia, se eligió una base de datos en globals: Caché.
No sé la estructura exacta de los globals en este proyecto, pero puedo suponer que es algo como esto:
Set ^galaxy(b, l, d) = 1; Número de estrella en el catálogo, si existe
Set ^galaxy(b, l, d, "name") = "Sol"
Set ^galaxy(b, l, d, "type") = "normal"; opciones blackhole, quazar, red_dwarf, etc.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercurio"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Donde b, l, d son y distancia al Sol.
La estructura flexible de los globals permite almacenar cualquier característica necesaria de las estrellas y planetas, ya que las bases en globals son sin esquema (scheme-less).
Para almacenar el mapa de nuestro universo, Caché fue elegida no solo por su flexibilidad, sino también por su capacidad para guardar rápidamente un flujo de datos, al tiempo que crea globals indexados para búsquedas rápidas.
Por volver a la Tierra, se crearon proyectos cartográficos en globals y el fork de OpenStreetMap — .
Recientemente en se implementaron índices geoespaciales . Esperamos detalles de implementación de los autores del artículo.
Implementación de índices espaciales en globals en OpenStreetMap XAPI
Las imágenes fueron tomadas de .
Toda la superficie terrestre se divide en cuadros, luego en subcuadrados, y los subcuadrados en sub-subcuadrados, y así sucesivamente. En general, obtenemos una estructura jerárquica para cuya almacenamiento se crearon globals.
En cualquier momento, podemos solicitar prácticamente instantáneamente el cuadrado necesario o limpiarlo, y todos los subcuadrados también serán devueltos o limpiados.
Un esquema similar en globals se puede implementar de varias maneras.
Opción 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idDelPrimero
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idDelSegundo
...Opción 2:
Set ^m('abacdabcdabacdabcda', 1) = idDelPrimero
Set ^m('abacdabcdabacdabcda', 2) = idDelSegundo
...En ambos casos, no es difícil en COS/M solicitar puntos que se encuentren en un cuadrado de cualquier nivel. Limpiar las secciones cuadradas del espacio de cualquier nivel será un poco más fácil en la primera opción, aunque esto rara vez es necesario.
Ejemplo de uno de los cuadrados de nivel inferior:
Aquí hay algunos globales del proyecto XAPI: representación del índice en los globales:
Global ^way se utiliza para almacenar puntos (caminos, ríos pequeños, etc.) y polígonos (áreas cerradas: edificios, bosques, etc.).
Clasificación grosera del uso de matrices dispersas en globales.
- Almacenamos las coordenadas de ciertos objetos y sus estados (mapeo, autómatas celulares)
- Almacenamos matrices dispersas.
Para el caso 2) al solicitar una coordenada específica donde no se ha asignado un valor al elemento, debemos obtener el valor del elemento de la matriz dispersa por defecto.
Bonos que obtenemos al almacenar matrices multidimensionales en globales
Eliminación rápida y/o selección de secciones del espacio que son múltiplos de filas, planos, cubos, etc. Para casos donde se utilizan índices enteros, puede ser útil la capacidad de eliminar y/o seleccionar rápidamente secciones del espacio que son múltiplos de filas, planos, cubos, etc.
Con el comando podemos eliminar tanto un elemento individual como una fila, e incluso un plano entero. Debido a las propiedades de los globales, esto ocurre muy rápidamente, miles de veces más rápido que la eliminación elemento por elemento.
En la imagen se muestra una matriz tridimensional en un global ^a y diferentes tipos de eliminaciones.
Para seleccionar secciones del espacio por índices conocidos, se puede utilizar el comando .
Selección de una columna de la matriz en la variable Column:
; Definamos una matriz dispersa tridimensional 3x3x3
Set ^a(0,0,0)=1,^a(2,2,0)=1,^a(2,0,1)=1,^a(0,2,1)=1,^a(2,2,2)=1,^a(2,1,2)=1
Fusionar Column = ^a(2,2)
; Mostremos la variable Column
Zwrite Column
Salida:
Column(0)=1
Column(2)=1
Lo interesante es que en la variable Column también obtuvimos una matriz dispersa, a la que también necesitamos acceder a través de , dado que los valores por defecto no se almacenan en ella.
La selección de secciones del espacio también se puede hacer a través de un pequeño programa utilizando la función . Esto es especialmente conveniente en espacios cuyos índices no están cuantizados (cartografía).
Conclusión
Los tiempos actuales plantean nuevas y ambiciosas tareas. Los grafos pueden consistir en miles de millones de vértices, los mapas en miles de millones de puntos, y alguien incluso podría querer lanzar su propio universo en autómatas celulares (, ).
Cuando el volumen de datos de matrices dispersas ya no puede ser contenido en la memoria RAM y es necesario trabajar con ellos, se debe considerar la posibilidad de implementar proyectos similares en globales y COS.
¡Gracias por su atención! Esperamos sus preguntas y comentarios.
Descargo de responsabilidad: Este artículo y mis comentarios al respecto son mi opinión personal y no representan la posición oficial de la corporación InterSystems.
Fuente: habr.com
