Dans les parties précédentes (, ) nous avons parlé des globaux comme des arbres, dans celui-ci, nous examinerons les globaux comme des tableaux clairsemés.
est un type de tableau dans lequel la plupart des valeurs prennent la même valeur.
En pratique, les tableaux clairsemés sont souvent si volumineux qu’il ne sert à rien d’occuper la mémoire avec des éléments identiques. Par conséquent, il est logique d’implémenter des tableaux clairsemés de telle manière que la mémoire ne soit pas gaspillée pour stocker des valeurs identiques.
Dans certains langages de programmation, les tableaux clairsemés sont inclus dans le langage lui-même, , . D'autres langages de programmation disposent de bibliothèques spéciales qui vous permettent de les implémenter. Pour C++ - etc
Les globaux sont de bons candidats pour implémenter des tableaux clairsemés car :
- Ils stockent les valeurs de certains nœuds uniquement et ne stockent pas les valeurs de ceux indéfinis ;
- L'interface pour accéder à la valeur d'un nœud est extrêmement similaire au nombre de langages de programmation implémentant l'accès à un élément de tableau multidimensionnel.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global est une structure de stockage de données d'assez bas niveau, elle présente donc des caractéristiques de vitesse exceptionnelles (de centaines de milliers à des dizaines de millions de transactions par seconde, selon le matériel, voir ci-dessous). )
Étant donné que le global est une structure persistante, il est logique de créer des tableaux clairsemés sur ceux-ci lorsqu'on sait à l'avance que la quantité de RAM ne sera pas suffisante.
L'une des propriétés des implémentations de tableaux clairsemés est de renvoyer une valeur par défaut si un accès est effectué à une cellule non définie.
Ceci peut être implémenté à l'aide de la fonction en COS. Cet exemple considère un tableau à 3 dimensions.
SET a = $GET(^a(x,y,z), defValue)Quelles tâches nécessitent des tableaux clairsemés et comment les variables globales peuvent-elles être utiles ?
Matrice de contiguïté (connectivité)
utilisé pour représenter des graphiques :
Évidemment, plus le graphique est grand, plus il y aura de zéros dans la matrice. Si, par exemple, nous prenons un graphique de réseau social et le présentons sous la forme d'une matrice similaire, alors il sera presque entièrement composé de zéros, c'est-à-dire sera un tableau clairsemé.
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
....
Dans cet exemple, nous économisons globalement ^m matrice de connectivité, ainsi que le nombre d'arêtes à chaque nœud (qui est ami avec qui et le nombre d'amis).
Si le nombre d'éléments dans le graphique n'est pas supérieur à 29 millions (ce nombre est pris comme le produit de 8 * ), c'est-à-dire qu'un moyen encore plus économique de stocker de telles matrices consiste à utiliser des chaînes de bits, car leur mise en œuvre optimise de manière particulière les grands espaces.
Les manipulations avec des chaînes de bits sont effectuées par la fonction .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Table de transition de machine à états
Puisque le graphe de transition d’un automate fini est un graphe ordinaire, alors la table de transition de l’automate fini est la même matrice de contiguïté discutée ci-dessus.
Automates cellulaires
L'automate cellulaire le plus célèbre est , qui, en raison de ses règles (quand une cellule a de nombreux voisins, elle meurt) est un tableau clairsemé.
Stephen Wolfram pense que les automates cellulaires sont . En 2002, il a publié un livre de 1280 XNUMX pages, A New Kind of Science, dans lequel il soutient largement que les progrès réalisés dans le domaine des automates cellulaires ne sont pas isolés, mais qu’ils sont durables et ont de grandes implications pour tous les domaines scientifiques.
Il a été prouvé que tout algorithme exécutable sur un ordinateur peut être implémenté à l'aide d'un automate cellulaire. Les automates cellulaires sont utilisés pour modéliser des environnements et des systèmes dynamiques, pour résoudre des problèmes algorithmiques et à d'autres fins.
Si nous avons un champ immense et que nous devons enregistrer tous les états intermédiaires d’un automate cellulaire, alors il est logique d’utiliser des variables globales.
Cartographie
La première chose qui me vient à l’esprit lorsqu’il s’agit d’utiliser des tableaux clairsemés est la cartographie des tâches.
En règle générale, il y a beaucoup d’espace vide sur les cartes. Si la carte est représentée sous forme de grands pixels, alors 71 % des pixels de la Terre seront occupés par l'océan. Tableau clairsemé. Et si vous utilisez uniquement des œuvres de mains humaines, l'espace vide sera supérieur à 95 %.
Bien entendu, personne ne stocke les cartes sous forme de tableaux raster ; une représentation vectorielle est utilisée.
Mais que sont les cartes vectorielles ? Il s'agit d'une sorte de cadre composé de polylignes et de polygones constitués de points.
Essentiellement une base de données de points et de connexions entre eux.
L’une des missions de cartographie les plus ambitieuses est la mission Gaia Telescope visant à cartographier notre galaxie. Au sens figuré, notre galaxie, comme l'univers entier, est un réseau continu et clairsemé : d'immenses espaces de vide dans lesquels se trouvent de rares petits points - des étoiles. L'espace vide est de 99,999999…….%. Pour stocker la carte de notre galaxie, une base de données mondiale a été choisie - Caché.
Je ne connais pas la structure exacte des globales dans ce projet, je peux supposer que c'est quelque chose de similaire à :
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
...
Où b, l, d sont et la distance au Soleil.
La structure flexible des globals vous permet de sauvegarder toutes les caractéristiques nécessaires des étoiles et des planètes, puisque les bases des globals sont sans schéma.
Pour stocker la carte de notre univers, Caché a été choisi non seulement pour sa flexibilité, mais aussi pour sa capacité à stocker un flux de données très rapidement, tout en créant simultanément des index globaux pour des recherches rapides.
Si nous revenons sur Terre, alors des projets cartographiques ont été créés sur des planètes et un fork d'OpenStreetMap - .
Récemment sur des index géospatiaux ont été mis en œuvre . Nous attendons un article des auteurs avec les détails de mise en œuvre.
Implémentation d'index spatiaux sur un global dans OpenStreetMap XAPI
Photos prises de .
Le globe entier est divisé en carrés, puis en sous-carrés, et les sous-carrés en sous-sous-carrés, et ainsi de suite. En général, nous obtenons une structure hiérarchique pour stocker les globaux créés.
À tout moment, nous pouvons demander presque instantanément le carré souhaité ou l'effacer, et tous les sous-carrés seront également restitués ou effacés.
Un schéma similaire sur les globals peut être mis en œuvre de plusieurs manières.
Option 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ВторойТочки
...Option 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Dans les deux cas, il n'est pas difficile d'utiliser COS/M pour demander des points situés dans une case de n'importe quel niveau. Il sera un peu plus facile de nettoyer des morceaux d'espace carrés à n'importe quel niveau dans la première option, mais cela est rarement nécessaire.
Un exemple d'un des carrés du niveau inférieur :
Et voici plusieurs globals du projet XAPI : représentation d'un index sur les globals :
global ^façon utilisé pour stocker des points (routes, petites rivières, etc.) et des polygones (zones fermées : bâtiments, forêts, etc.).
Classification approximative de l'utilisation de tableaux clairsemés sur les globaux.
- Nous stockons les coordonnées de certains objets et leurs états (cartographie, automates cellulaires)
- Nous stockons des matrices clairsemées.
Pour le cas 2) lors de la demande d'une coordonnée spécifique où aucune valeur n'est attribuée à l'élément, nous devons obtenir la valeur de l'élément de tableau clairsemé par défaut.
Bonus que nous recevons lors du stockage de matrices multidimensionnelles dans des globales
Supprimez et/ou sélectionnez rapidement des morceaux d'espace qui sont des multiples de lignes, de plans, de cubes, etc. Dans les cas où des index entiers sont utilisés, la possibilité de supprimer et/ou de récupérer rapidement des morceaux d'espace qui sont des multiples de lignes, de plans, de cubes, etc. peut être utile.
Équipe nous pouvons supprimer soit un seul élément, soit une ligne, voire un plan entier. Grâce aux propriétés des globales, cela se produit très rapidement - des milliers de fois plus rapide que la suppression élément par élément.
La figure montre un tableau tridimensionnel dans un environnement global ^a et différents types de suppressions.
Pour sélectionner des morceaux d'espace à l'aide d'index connus, vous pouvez utiliser la commande .
Sélection d'une colonne matricielle dans la variable Colonne :
; Зададим трёхмерный разреженный массив 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
Conclusion:
Column(0)=1
Column(2)=1
Ce qui est intéressant avec la variable Column, c'est que nous avons également un tableau clairsemé, auquel il faut également accéder via , puisque les valeurs par défaut n'y sont pas stockées.
La sélection de morceaux d'espace peut également être effectuée via un petit programme utilisant la fonction . Ceci est particulièrement pratique sur les espaces dont les indices ne sont pas quantifiés (cartographie).
Conclusion
Les temps actuels imposent de nouvelles tâches ambitieuses. Les graphiques peuvent être constitués de milliards de sommets, les cartes constituées de milliards de points, et certains pourraient même vouloir faire fonctionner leur propre univers sur des automates cellulaires (, ).
Lorsque le volume de données des tableaux clairsemés ne peut plus tenir dans la RAM, mais que vous devez travailler avec eux, il convient alors d'envisager la possibilité de mettre en œuvre des projets similaires sur les globaux et le COS.
Merci pour votre attention! Nous attendons vos questions et souhaits dans les commentaires.
Clause de non-responsabilité : Cet article et mes commentaires sont mon opinion et n'ont aucun rapport avec la position officielle d'InterSystems Corporation.
Source: habr.com