Représentation de données multidimensionnelles clairsemées

Question

Je travaille sur un outil de simulation cardiaque qui utilise des données en 4 dimensions, c'est-à-dire plusieurs (3-30) variables à des emplacements dans l'espace 3D. J'ajoute maintenant une géométrie de tissu qui laissera plus de 2/3 des points dans la boîte 3D contenant à l'extérieur du tissu à simuler, donc j'ai besoin d'un moyen de stocker efficacement les points actifs et pas les autres .

Fondamentalement, je dois être en mesure de:

• itérer sur tous les points actifs dans une boîte 3D contrainte (iterator, peut-être?)
• Après avoir accédé un point, trouver ses voisins orthogonaux (x, y, z) +/- 1.

C'est probablement plus d'une question! Ma principale préoccupation est de savoir comment représenter efficacement les données éparses.

J'utilise C.

Answer 1

À quelle fréquence vous ajoutez le tissu, et combien de temps peut-elle prendre?

Une solution simple utilise une liste chaînée + hachage avec des pointeurs de l'un à l'autre.

Signification:

1. Enregistrer une liste chaînée contenant tous les points pertinents et leurs données
2. Enregistrer un hachage pour obtenir facilement à ces données: coordonnées clés =, data = pointeur sur la liste chaînée.

La mise en œuvre des opérations serait:
Ajouter une boîte: Go sur la liste chaînée complète, et ne prendre que les éléments pertinents dans la liste chaînée « travail »
Itérer: Revoyez le "travail" liste liée
Rechercher des voisins: Cherchez chacun des voisins dans le hachage.

Complexité:
Ajouter: O (n), Iterate O (1) pour trouver l'élément suivant, moyenne du voisin O (1) (due au hachage).

Answer 2

Si vous voulez utiliser l'indexation de tableau simple, vous pouvez créer un tableau clairsemé sur les systèmes POSIX utilisant mmap():

float (*a)[500][500]; 

a = mmap(0, (size_t)500 * sizeof a[0], PROT_READ | PROT_WRITE, 
    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); 

if (a && (void *)a != MAP_FAILED) 
{ 
    /* a is now 500 x 500 x 500 sparse array of floats */ 

Vous pouvez alors accéder juste un [x] [y] [z] comme vous aimez, et il n'allouera réellement la mémoire réelle pour chaque page qui a été touchée. Le tableau sera initialisé à zéro octet.

Si votre système n'a pas MAP_ANONYMOUS, vous pouvez obtenir le même effet en mappant depuis/dev/zero.

Notez que sur de nombreux systèmes, l'espace de swap sera réservé (bien que non utilisé) pour l'ensemble du tableau.

Answer 3

Tout d'abord, je pense que cela vaut la peine de considérer ce que sont vos besoins réels.Je pense que ce n'est pas seulement "stocker les points actifs et aucun des autres d'une manière aussi efficace que possible", mais aussi "stocker des points adjacents dans des emplacements mémoire proches afin d'avoir un bon comportement de mise en cache". "stocker les points d'une manière pour laquelle les recherches peuvent être effectuées efficacement".

Cela dit, voici ce que je suggère. Divisez la région 3D complète en blocs cubiques, tous de la même taille. Pour chaque bloc, stockez tous les points du bloc dans des tableaux denses, y compris un tableau isTissue booléen pour savoir si chaque point est dans la région tissulaire ou non. Allouer seulement les blocs qui ont des points en eux. Faire un tableau (dense) de pointeurs vers des blocs, avec des pointeurs NULL pour les blocs non alloués. Ainsi, pour trouver le point en (i, j), vous devez d'abord calculer ii = i/bloc, jj = j/blocksize, puis chercher dans la table pointeur à bloc en (ii, jj) trouvez le bloc qui contient votre point. Si ce pointeur est NULL, votre point n'est pas dans le tissu. Si elle est non nulle, vous regardez (i mod blocksize, j mod blocksize) dans ce bloc, et il y a votre point (i, j). Vous pouvez vérifier son indicateur isTissue pour voir s'il s'agit d'un point "présent" ou non. Vous voudrez choisir la taille de bloc comme un équilibre entre la minimisation du nombre de fois que vous faites des calculs de points adjacents qui traversent les limites de blocs, et la minimisation du nombre de points qui sont dans les blocs mais pas dans la région de tissu. Je suppose qu'au minimum, vous voulez qu'une ligne du bloc soit longue. Probablement l'optimum est plutôt plus grand que cela, même si cela dépendra au moins un peu de votre géométrie. Pour parcourir tous les points d'une boîte 3D, vous effectuez simplement des recherches pour chaque point, ou (plus efficacement) déterminez les blocs qui touchent la boîte et parcourez les régions dans les blocs qui se trouvent dans votre boîte. case, en ignorant celles où isTissue est false. Si vous faites beaucoup de désallocation et de réallocation de blocs, vous voulez probablement "libérer" les blocs en les déposant dans un pool "inutilisé", puis en extrayant des blocs de ce pool plutôt que de les réaffecter . Cela a aussi l'avantage que tous ces points auront déjà tous leurs points sur "non présents" (parce que c'est pour cela que vous avez libéré le bloc), donc vous n'avez pas besoin de les initialiser.

Le lecteur expérimenté reconnaîtra probablement les similitudes entre ceci et les façons de disposer des données pour les calculs parallèles; Si vous avez une très grande simulation, vous pouvez facilement répartir les blocs sur plusieurs nœuds, et vous n'avez besoin que d'une communication entre nœuds pour les calculs de blocs croisés. Pour ce genre d'application, vous pouvez trouver utile de faire des niveaux imbriqués de blocs, où vous avez des méta-blocs (pour la communication entre nœuds) contenant des blocs plus petits (pour la géométrie).