Tableaux tridimensionnels efficaces en C en C

Question

J'essaie de résoudre numériquement un ensemble d'équations aux dérivées partielles en trois dimensions. Dans chacune des équations, la valeur suivante de l'inconnue dans un point dépend de la valeur actuelle de chaque inconnue dans les points les plus proches.

Pour écrire un code efficace, je dois garder les points proches des trois dimensions dans l'espace mémoire (unidimensionnel), afin que chaque valeur ne soit appelée qu'une seule fois depuis la mémoire.

Je pensais utiliser des octtrees, mais je me demandais si quelqu'un connaissait une meilleure méthode.

Answer 1

Les octtrees sont la voie à suivre. Vous subdivisez le tableau en 8 octants:

1 2
3 4

---

5 6
7 8

Ensuite, disposez-les en mémoire dans l’ordre 1, 2, 3, 4, 5, 6, 7, 8 comme ci-dessus. Vous répétez cela de manière récursive dans chaque octant jusqu'à ce que vous obteniez une taille de base, probablement autour de 128 octets (c'est une supposition - assurez-vous de profiler pour déterminer le point de coupure optimal). La cohérence du cache et la localité de référence sont bien meilleures que celles du modèle naïf.

Answer 2

Une alternative à la méthode tree: utilisez le Morton-Order pour encoder vos données.

En trois dimensions, cela ressemble à ceci: Prenez les composantes de coordonnées et entrelacez chaque bit deux bits nuls. Ici en binaire: 11111b devient 1001001001b

Une fonction C pour faire ceci ressemble à ceci (montré par souci de clarté et seulement pour 11 bits):

int morton3 (int a)
{
  int result = 0;
  int i;
  for (i=0; i<11; i++)
  {
     // check if the i'th bit is set.
     int bit = a&(1<<i);
     if (bit)
     {
       // if so set the 3*i'th bit in the result:
       result |= 1<<(i*3);
     }
  }
  return result;
}

Vous pouvez utiliser cette fonction pour combiner vos positions comme ceci:

index = morton3 (position.x) + 
        morton3 (position.y)*2 +
        morton3 (position.z)*4;

Ceci transforme votre index tridimensionnel en un unidimensionnel. Meilleur atout: les valeurs proches dans l’espace 3D le sont également dans l’espace 1D. Si vous accédez fréquemment à des valeurs proches les unes des autres, vous obtiendrez également une très bonne accélération, car le codage par ordre morton est optimal en termes de localité de cache.

Pour morton3, vous feriez mieux de ne pas utiliser le code ci-dessus. Utilisez une petite table pour rechercher 4 ou 8 bits à la fois et combinez-les.

J'espère que ça aide,   Nils

Answer 3

Le livre Fondements de structures de données multidimensionnelles et métriques peut vous aider à décider. quelle structure de données est la plus rapide pour les requêtes de plage: octrees, kd-trees, R-trees, ... Il décrit également les dispositions de données permettant de conserver les points ensemble en mémoire.