Discussion :

[Grasshoper]

Bonjour à toutes et à tous,

Je souhaiterais avoir des opinions sur une question de programmation en C. Le problème est le suivant: j'ai une série temporelle qui décrit le déplacement d'une particule dans un espace bidimensionnel. Je calcule le nombre de passages de cette particule dans chaque cellule d'un grand maillage en 2D pour estimer une espèce de densité (je ne rentre pas dans les détails). J'ai choisi de me placer localement dans une portion du maillage pour chaque couple de position de la particule entre 2 temps, afin de ne pas avoir à parcourir tous les nœuds du maillage pour savoir s'ils ont 'vu' la particule passer ou non (long!).
Du coup, je me retrouve à sélectionner les nœuds qui sont voisins immédiats des observations que je traite et à stocker ces nœuds (ou 'sous-maillage') pour faire un calcul sur chacun d'eux. Il y a donc autant de sous-maillages que de positions de la particule. J'ai une contrainte de temps, l'algorithme doit être rapide car calculé sur un grand nombre de particules. Je ne connais pas la taille à priori de chaque sous-maillage, mais j'ai un indice: les déplacements sont rarement grands.

Est-ce qu'il est préférable de :

1. stocker ce 'sous-maillage' dans un tableau dynamique (la taille de chaque sous-maillage étant différente) contenant exactement les nœuds d'intérêt et que je libère après chaque utilisation (ce qui suppose de récréer ce tableau à chaque position),
2. d'avoir un grand et unique tableau statique ou je mets les nœuds d'intérêt et que je n'aurais qu'à vider/réinitialiser à chaque utilisation après calcul de la stat qui m'intéresse,
3. travailler directement sur le maillage d'origine avec des pointeurs qui définiront/contiendront mon sous-maillage,
4. ne pas s'embêter avec un 'sous-maillage' et parcourir brutalement pour toutes les positions tous les nœuds du maillage et estimer ma stat (sachant que bcp de nœuds ne serviront à rien pour de petits déplacements de la particule, ce qui arrive souvent)
5. opter pour une autre alternative ?

Sachant que:

• Dans tous les cas, chaque sous-maillage doit être réinitialisé (ou ses valeurs remises à zéro) pour chaque position de la particule
• Les calculs sont effectués sur un serveur, pas de problème de mémoire (pour l'instant),
• Les calculs sont déjà parallélisés,
• Quelques chiffres: Il y a environ 30000 positions pour chaque particule, le maillage contient 1 à plusieurs millions de nœuds

Merci par avance!

[foetus]

Ton "truc" me fait penser aux BSP (les niveaux de Doom) (ou à l'algo "clustering" de la radiosité):
en gros, on va travailler soit avec des arbres soit avec des pondérations pour savoir où travailler (même s'il y a des approximations).

Si ton point va vers la droite, ce n'est pas la peine d'aller voir ce qui se passe à gauche

[Grasshoper]

Merci pour ce retour rapide.
Je ne connaissais pas mais ca a l'air effectivement intéressant.
Et par curiosité personnelle, quelle méthode parmi celles que je proposais aurait été la plus rapide?
Merci!

[Bktero]

Quel est l'intérêt de recopier une partie de ton maillage ? Si tu cherches la performance, cette copie va te coûter forcément un peu. Si cette copie ne sert pas de changer le format des données pour avoir en "local" une structure plus pratique pour faire tes calculs, je pense que tu as intérêt à aller directement travailler sur le maillage complet, en utilisant des bornes pour limiter les calculs inutiles.

[Grasshoper]

Merci cette réponse est pleine de bon sens.
Je vais effectivement récupérer seulement les bornes et travailler localement sur le maillage, sans stocker.
L'idée du BSP me plait bien aussi, je trouve ca rapide et original.

Cependant, par pure curiosité, j'ai lu différents topics sur les tableaux resizés dynamiquement et je me pose encore la question de savoir ce qui est le plus efficient.

Merci pour vos retours en tous cas!

G

[foetus]

Le problème de ta question ce sont des questions de mesure de temps

Qui est le plus rapide: des allocations/ réallocations? des déférencements? des parcours arbres (*)? Autres?

Bien cela se mesure sur plusieurs machines, sur la machine de production/ finale pour savoir comment et où optimiser

Nous on ne peut pas trop répondre, juste donner des pistes de réflexion.

Mais si tu as peur du temps des allocations/ réallocations, tu peux utiliser des techniques comme des memory pool


* -> pour faire écho à ma remarque, extraire de ton maillage des informations qui vont permettent de trouver le point plus rapidement.