En partes anteriores (, ) hablamos de los globales como árboles, en este los veremos como matrices dispersas.
Es un tipo de matriz en el que la mayoría de los valores toman el mismo valor.
En la práctica, las matrices dispersas suelen ser tan grandes que no tiene sentido ocupar la memoria con elementos idénticos. Por lo tanto, tiene sentido implementar matrices dispersas de tal manera que no se desperdicie memoria almacenando valores idénticos.
En algunos lenguajes de programación, se incluyen matrices dispersas en el propio lenguaje, , . Otros lenguajes de programación tienen bibliotecas especiales que permiten implementarlos. Para C++- et al.
Los globales son buenos candidatos para implementar matrices dispersas porque:
- Almacenan los valores de solo ciertos nodos y no almacenan los valores de los indefinidos;
- La interfaz para acceder al valor de un nodo es extremadamente similar a la cantidad de lenguajes de programación que implementan el acceso a un elemento de matriz multidimensional.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global es una estructura de almacenamiento de datos de nivel bastante bajo, por lo que tiene características de velocidad sobresalientes (de cientos de miles a decenas de millones de transacciones por segundo, según el hardware, ver más abajo). )
Dado que el global es una estructura persistente, tiene sentido crear matrices dispersas en ellos cuando se sabe de antemano que la cantidad de RAM no será suficiente.
Una de las propiedades de las implementaciones de matrices dispersas es devolver algún valor predeterminado si se accede a una celda no definida.
Esto se puede implementar usando la función en COS. Este ejemplo considera una matriz tridimensional.
SET a = $GET(^a(x,y,z), defValue)¿Qué tareas requieren matrices dispersas y cómo pueden ayudar los globales?
Matriz de adyacencia (conectividad)
utilizado para representar gráficos:
Obviamente, cuanto más grande sea la gráfica, más ceros habrá en la matriz. Si, por ejemplo, tomamos el gráfico de una red social y lo presentamos en forma de una matriz similar, entonces estará compuesto casi en su totalidad de ceros, es decir, será una matriz escasa.
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, ahorramos globalmente. ^m 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 * ), es decir, una forma aún más económica de almacenar dichas matrices son las cadenas de bits, ya que su implementación optimiza de forma especial los espacios grandes.
Las manipulaciones con cadenas de bits las realiza la función .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabla de transición de la máquina de estados
Dado que el gráfico de transición de un autómata finito es un gráfico ordinario, entonces la tabla de transición del autómata finito es la misma matriz de adyacencia discutida anteriormente.
Autómata celular
El autómata celular más famoso es , que, debido a sus reglas (cuando una célula tiene muchos vecinos, muere) es una matriz dispersa.
Stephen Wolfram cree que los autómatas celulares son . En 2002, publicó un libro de 1280 páginas, Un nuevo tipo de ciencia, en el que sostiene en términos generales que los avances en los autómatas celulares no son aislados, sino que son duraderos y tienen grandes implicaciones para todas las áreas de la ciencia.
Se ha comprobado que cualquier algoritmo ejecutable en una computadora puede implementarse utilizando 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 campo enorme y necesitamos registrar todos los estados intermedios de un autómata celular, entonces tiene sentido utilizar valores globales.
Cartografía
Lo primero que me viene a la mente cuando se trata de utilizar matrices dispersas son las tareas de mapeo.
Como regla general, hay mucho espacio vacío en los mapas. Si el mapa se representa como píxeles grandes, entonces el 71% de los píxeles de la Tierra estarán ocupados por el océano. Conjunto escaso. Y si aplica solo obras de manos humanas, entonces el espacio vacío será más del 95%.
Por supuesto, nadie almacena mapas en forma de matrices ráster; se utiliza una representación vectorial.
Pero ¿qué son los mapas vectoriales? Se trata de una especie de marco, polilíneas y polígonos formados por puntos.
Esencialmente una base de datos de puntos y conexiones entre ellos.
Una de las misiones cartográficas más ambiciosas es la misión del Telescopio Gaia para mapear nuestra galaxia. En sentido figurado, nuestra galaxia, como todo el universo, es un conjunto continuo y disperso: enormes espacios vacíos en los que hay pequeños puntos raros: las estrellas. El espacio vacío es 99,999999…….%. Para almacenar el mapa de nuestra galaxia, se eligió una base de datos global: Caché.
No conozco la estructura exacta de los globales en este proyecto, puedo suponer que es algo similar a:
Set ^galaxy(b, l, d) = 1; Номер звезды по каталогу, если есть
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal" ; варианты blackhole, quazar, red_dwarf и т.д.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Donde b, l, d son y distancia al Sol.
La estructura flexible de los globales le permite guardar cualquier característica necesaria de estrellas y planetas, ya que las bases de los globales no tienen esquemas.
Para almacenar el mapa de nuestro universo, se eligió Caché no solo por su flexibilidad, sino también por su capacidad de almacenar un flujo de datos muy rápidamente, al mismo tiempo que crea índices globales para búsquedas rápidas.
Si regresamos a la Tierra, entonces se crearon proyectos cartográficos en los globales. y una bifurcación de OpenStreetMap - .
Recientemente en Se implementaron índices geoespaciales. . Estamos esperando un artículo de los autores con detalles de implementación.
Implementación de índices espaciales a nivel global en OpenStreetMap XAPI
Fotografías tomadas de .
Todo el globo se divide en cuadrados, luego en subcuadrados, y los subcuadrados en subsubcuadrados, y así sucesivamente. En general, obtenemos una estructura jerárquica para almacenar qué globales se crean.
En cualquier momento, podemos solicitar casi instantáneamente el cuadrado deseado o borrarlo, y todos los subcuadrados también serán devueltos o borrados.
Un esquema similar sobre globales 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) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...Opción 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...En ambos casos no resulta complicado utilizar COS/M para solicitar puntos situados en un cuadrado de cualquier nivel. Será algo más fácil limpiar espacios cuadrados en cualquier nivel en la primera opción, pero esto rara vez es necesario.
Un ejemplo de uno de los cuadrados del nivel inferior:
Y aquí hay varios globales del proyecto XAPI: representación de un índice sobre globales:
global ^camino utilizado para almacenar puntos (carreteras, pequeños ríos, etc.) y polígonos (áreas cerradas: edificios, bosques, etc.).
Clasificación aproximada del uso de matrices dispersas en globales.
- Almacenamos las coordenadas de determinados objetos y sus estados (mapeo, autómatas celulares)
- Almacenamos matrices dispersas.
Para el caso 2) al solicitar una coordenada específica donde al elemento no se le asigna un valor, debemos obtener el valor del elemento de matriz dispersa predeterminado.
Bonificaciones que recibimos al almacenar matrices multidimensionales en globales
Elimina y/o selecciona rápidamente piezas de espacio que sean múltiples filas, planos, cubos, etc. Para los casos en los que se utilizan índices enteros, puede resultar útil la capacidad de eliminar y/o recuperar rápidamente fragmentos de espacio que sean múltiplos de filas, planos, cubos, etc.
equipo podemos eliminar un solo elemento o una fila, o incluso un plano completo. Gracias a las propiedades de los globales, esto sucede muy rápidamente, miles de veces más rápido que la eliminación elemento por elemento.
La figura muestra una matriz tridimensional en un global ^a y diferentes tipos de eliminaciones.
Para seleccionar piezas de espacio usando índices conocidos, puede usar el comando .
Seleccionar una columna de matriz en la variable Columna:
; Зададим трёхмерный разреженный массив 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
Merge Column = ^a(2,2)
; Выведем переменную Column
Zwrite Column
Conclusión:
Column(0)=1
Column(2)=1
Lo interesante de la variable Columna es que también tenemos una matriz dispersa, a la que también se debe acceder a través de , ya que en él no se almacenan los valores predeterminados.
La selección de piezas de espacio también se puede realizar a través de un pequeño programa usando la función . Esto es especialmente conveniente en espacios cuyos índices no están cuantificados (cartografía).
Conclusión
Los tiempos actuales plantean nuevas tareas ambiciosas. Los gráficos pueden estar formados por miles de millones de vértices, los mapas por miles de millones de puntos y algunos incluso podrían querer ejecutar su propio universo en autómatas celulares (, ).
Cuando el volumen de datos de matrices dispersas ya no cabe en la RAM, pero es necesario trabajar con ellos, entonces vale la pena considerar la posibilidad de implementar proyectos similares en globales y COS.
¡Gracias por su atención! Estamos esperando sus preguntas y deseos en los comentarios.
Observación: Este artículo y mis comentarios son mi opinión y no tienen relación con la posición oficial de InterSystems Corporation.
Fuente: habr.com