Dans les parties précédentes (, ) nous avons parlé des globales comme des arbres, dans celle-ci nous allons considérer les globales comme des tableaux clairsemés.
est un type de tableau dans lequel la plupart des valeurs prennent la même valeur.
Dans la pratique, il existe souvent des tableaux clairsemés si énormes qu'il n'y a aucun sens à occuper de la mémoire avec des éléments identiques. Par conséquent, il est judicieux de mettre en œuvre des tableaux clairsemés de manière à ne pas gaspiller de mémoire pour stocker des valeurs identiques.
Dans certains langages de programmation, les tableaux clairsemés sont intégrés dans le langage lui-même, , Dans d'autres langages de programmation, il existe des bibliothèques spéciales qui permettent de les implémenter. Pour C++, et autres.
Les globales sont de bons candidats pour la mise en œuvre de tableaux clairsemés, car :
- Ils stockent uniquement les valeurs de certains nœuds et ne stockent pas les valeurs indéfinies ;
- L'interface d'accès à la valeur d'un nœud est très similaire à la manière dont l'accès à un élément d'un tableau multidimensionnel est réalisé dans de nombreux langages de programmation.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - La globale est une structure suffisamment bas niveau pour le stockage de données, donc elle offre des performances exceptionnelles (de centaines de milliers à des dizaines de millions de transactions par seconde en fonction du matériel, voir. )
Comme la globale est une structure persistante, il est sensé d'appliquer des tableaux clairsemés sur elle lorsque l'on sait à l'avance que le volume de mémoire vive sera insuffisant.
Une des caractéristiques des implémentations de tableaux clairsemés est le retour d'une certaine valeur par défaut si l'accès se fait à une cellule indéfinie.
Cela peut être réalisé en utilisant la fonction dans COS. Dans cet exemple, un tableau tridimensionnel est traité.
SET a = $GET(^a(x,y,z), defValue)Dans quelles tâches les tableaux clairsemés sont-ils nécessaires et comment les globales peuvent-elles être utiles ?
La matrice d'adjacence (connectivité)
sont utilisées pour représenter des graphes :
Il est évident que plus le graphe est grand, plus il y aura de zéros dans la matrice. Si, par exemple, on prend un graphe de réseau social et on le représente sous la forme d'une telle matrice, il sera presque entièrement constitué de zéros, c'est-à-dire qu'il s'agira d'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 stockons dans la globale ^m la matrice de connectivité, ainsi que le nombre de liens de chaque nœud (qui est ami avec qui et le nombre d'amis).
Si le nombre d'éléments dans le graphe ne dépasse pas 29 millions (ce nombre est pris comme produit de 8 * ), il existe une méthode de stockage encore plus économique pour de telles matrices : les chaînes de bits, car leur implémentation optimise de manière spéciale les grands intervalles.
Les manipulations avec les chaînes de bits sont effectuées par la fonction .
; définir un bit
SET $BIT(rowID, positionID) = 1
; obtenir un bit
Write $BIT(rowID, positionID)
Table des transitions de l'automate fini
Étant donné que le graphe des transitions de l'automate fini est un graphe ordinaire, la table des transitions de l'automate fini est également la même matrice d'adjacence mentionnée ci-dessus.
Automates cellulaires
L'automate cellulaire le plus connu est , qui, en raison de ses règles (quand une cellule a trop de voisins, elle meurt), représente un tableau clairsemé.
Stephen Wolfram estime que les automates cellulaires sont En 2002, il publie un livre de 1280 pages intitulé « A New Kind of Science », où il argumente largement que les réalisations dans le domaine des automates cellulaires ne sont pas isolées, mais très robustes et ont une grande importance pour tous les domaines de la science.
Il a été prouvé que tout algorithme exécutable sur un ordinateur peut être réalisé par le biais 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 objectifs.
Si nous avons un champ immense et que nous devons enregistrer tous les états intermédiaires de l'automate cellulaire, il est tout à fait raisonnable d'utiliser des globales.
Cartographie
La première chose qui me vient à l'esprit lorsqu'on parle de l'utilisation des tableaux clairsemés est les tâches cartographiques.
En règle générale, les cartes contiennent beaucoup d'espace vide. Si une carte est représentée sous forme de grands pixels, 71 % des pixels de la Terre seront occupés par l'océan. Tableau clairsemé. Et si nous ne représentons que les œuvres des mains humaines, alors l'espace vide représentera plus de 95 %.
Bien sûr, personne ne conserve des cartes sous forme de tableaux raster, une représentation vectorielle est utilisée.
Mais que sont les cartes vectorielles ? C'est un cadre contenant des polylignes et des polygones constitués de points.
En fait, c'est une base de données de points et des relations entre eux.
Une des missions cartographiques les plus ambitieuses est la mission de cartographie de notre galaxie avec le télescope Gaia. En d'autres termes, notre galaxie, comme tout l'univers, est une vaste matrice diffuse : d'énormes espaces vides, où se trouvent de rares petits points — des étoiles. L'espace vide représente 99,999999…….%. Pour stocker la carte de notre galaxie, une base de données sur des globals a été choisie — Caché.
Je ne connais pas la structure exacte des globals dans ce projet, je peux supposer que c'est quelque chose comme :
Set ^galaxy(b, l, d) = 1; Numéro de l'étoile dans le catalogue, si disponible
Set ^galaxy(b, l, d, "name") = "Soleil"
Set ^galaxy(b, l, d, "type") = "normal" ; options blackhole, quasar, red_dwarf, etc.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercure"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Où b, l, d sont et la distance au soleil.
La structure flexible des globals permet de sauvegarder toutes les caractéristiques nécessaires des étoiles et des planètes, car les bases sur des globals sont sans schéma (scheme-less).
Pour stocker la carte de notre univers, Caché a été choisie non seulement pour sa flexibilité, mais aussi pour sa capacité à sauvegarder très rapidement des flux de données, tout en créant en parallèle des globals indexés pour une recherche rapide.
En revenant à la Terre, des projets cartographiques ont été créés sur des globals et un fork d'OpenStreetMap — .
Récemment, lors du des index géospatiaux ont été implémentés . Nous attendons des auteurs de l'article les détails de l'implémentation.
Mise en œuvre des index spatiaux sur un global dans OpenStreetMap XAPI
Les images proviennent de .
L'ensemble de la planète est découpé 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, on obtient une structure hiérarchique pour le stockage de laquelle des globals ont été créés.
À tout moment, nous pouvons demander presque instantanément le carré dont nous avons besoin ou l'effacer, les sous-carrés seront également retournés ou effacés.
Une telle schéma sur des globals peut être réalisé 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) = idPremièrePoint
Set ^m(a, b, a, c, d, a, b, c, d, a, b, a, c, d, a, b, c, d, a, 2) = idDeuxièmePoint
...Option 2 :
Set ^m('abacdabcdabacdabcda', 1) = idPremièrePoint
Set ^m('abacdabcdabacdabcda', 2) = idDeuxièmePoint
...Dans les deux cas, il est facile sur COS/M de réclamer des points situés dans le carré de n'importe quel niveau. Il sera un peu plus facile de nettoyer les morceaux carrés d'espace de n'importe quel niveau dans la première variante, mais cela est rarement nécessaire.
Exemple d'un des petits carrés de niveau inférieur :
Voici quelques globales du projet XAPI : présentation de l'index sur les globales :
Généralité ^way est utilisé pour stocker des points (routes, petites rivières, etc.) et des polygones (zones fermées : bâtiments, forêts, etc.).
Classification grossière de l'utilisation des matrices creuses sur les globales.
- Nous stockons les coordonnées de certains objets et leurs états (cartographie, automates cellulaires)
- Nous stockons des matrices creuses.
Dans le cas 2), lors de la demande d'une certaine coordonnée où l'élément n'a pas de valeur assignée, nous devons obtenir la valeur de l'élément de la matrice creuse par défaut.
Les avantages que nous obtenons en stockant des matrices multidimensionnelles dans les globales
Suppression rapide et/ou échantillonnage de morceaux d'espace, multiples de lignes, plans, cubes, etc. Pour les cas où des indices entiers sont utilisés, il peut être utile d'avoir la possibilité de supprimer rapidement et/ou d'échantillonner des morceaux d'espace, multiples de lignes, plans, cubes, etc.
Avec la commande nous pouvons supprimer à la fois un élément individuel, une ligne, et même tout un plan. Grâce aux propriétés des globales, cela se fait très rapidement - des milliers de fois plus vite qu'une suppression élément par élément.
La figure montre un tableau tridimensionnel dans la globale ^a et différents types de suppressions.
Pour l'échantillonnage de morceaux d'espace par indices connus, la commande peut être utilisée .
Échantillonnage d'une colonne de la matrice dans la variable Column :
; Définissons un tableau creux tridimensionnel 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)
; Affichons la variable Column
Zwrite Column
Conclusion :
Column(0)=1
Column(2)=1
Ce qui est intéressant, c'est que dans la variable Column, nous avons également obtenu une matrice creuse, à laquelle il faut accéder aussi via , car les valeurs par défaut ne sont pas stockées en elle.
L'échantillonnage de morceaux d'espace peut également se faire via un petit programme utilisant la fonction . C'est particulièrement pratique dans des espaces dont les indices ne sont pas quantifiés (cartographie).
Conclusion
Les temps actuels posent de nouveaux défis ambitieux. Les graphes peuvent contenir des milliards de sommets, les cartes des milliards de points, et certains pourraient même vouloir lancer leur propre univers sur des automates cellulaires (, ).
Lorsque le volume de données des matrices éparses ne peut plus être contenu dans la mémoire vive, mais qu'il est nécessaire de travailler avec, il est judicieux d'envisager la réalisation de tels projets sur des Global et COS.
Merci de votre attention ! Nous attendons vos questions et suggestions dans les commentaires.
Avertissement: Cet article et mes commentaires à son sujet représentent mon avis et ne reflètent pas la position officielle de l'entreprise InterSystems.
Source : habr.com
