Bonjour tout le monde,
 
Je suis entrain d'écrire un programme en c++ qui manipule un grand nombre de donnée, j'utilise std::vector pour insérer et supprimer les donnée dynamiquement , mais malheureusement le temps d'exécution et trop lent.
 
Est ce que quelqu'un connais une autre méthode autre que les stl pour améliorer le temps d'exécution ?
 
Merci d'avance

- std::vector n'est pas fait pour avoir des insertions/effacement ailleurs que pour le dernier elements efficacement
- std::deque le permet en tete et en queue
- std::list n'importe ou
 
A part ces generalites, tu donnes tellement peu d'information que t'aiguiller est difficile.

Merci  un programmeur pour votre réponse, si j'ai bien compris, en utilisant std::list l'insertion et la suppression des données ira plus vite ^^
 
PS:  j'essaye d'épargner les détailles  et donner juste l'essentiel ^^

 
Si les perfs sont vraiment importantes, il est bien souvent plus performant de coder soi même sa classe comportant moins de fonctionnalités mais n'exécutant que le code nécessaire.

 
Souvent?  Pas d'accord.  Je l'ai deja fait mais c'est quand meme relativement peu frequent (et plus souvent pour des questions d'occupation memoire que de rapidite d'ailleurs).

Voila je viens de tester le code avec std::list mais le temps est encore plus long !!  
 
existe t il une autre solution ?

vector::reserve par burst popur préallouer la mémoire de std::vector

Tu ne dis pas ce que tu fais. Montre du code et dis quelle est la taille de ton vecteur, combien tu insères et tu supprimes chaque seconde, quel est ton hardware, combien de RAM tu as, etc.

@ el muchacho : le code est tellement grand que je ne peux pas le mettre

Tu peux pas le réduire au minimum ? En tout cas ça m'étonnerait que ce soit la STL qui soit limitante.
Je viens de faire un test sur mon Core2Duo à 2,13GHz.
std::deque.push_front de 5 000 000 d'int: 281 ms
std::deque.pop_front de 5 000 000 d'int: 17 ms
std::list.push_front de 5 000 000 d'int: 998ms
std::list.pop_front de 5 000 000 d'int: 1130ms

 
Il serait pertinent que tu donnes la partie du code qui lit et insère les données, et que tu donnes une idée de l avolumétrie des données (nombre/taille).

 
D'abord faire tourner un profiler, ça mettra en avant le point faible du code. Il y a pas mal de chances que ça ne soit pas la STL la responsable mais la façon dont tu t'en sers (ou un bout de code purement à toi). Si jamais le profiler indique que c'est vraiment la STL, reviens ici en causer

En fait j'ai une matrice de 64800*100 pour chaque élément cells[k][i] de la matrice un tableau lui est associé et à chaque appel de la fonction "Loader::ajour" je cherche dans tout les tableaux si "numFace" (un entier) existe alors je l'écrase.  
Voici la fonction où mon problème ce génère :  
 

Je crois que ça n'a pas de sens de mettre les j++ dans le else.
 
A part ce détail je ne vois pas les types des collections que tu utilises:
 
- pour cells
- pour listContribution
- pour listPenalites.

@ gelatine_velue j'utilise j++ dans un else pour éviter de sauter un élément (exemple : si j'efface l'élément qui se trouve dans la position j = 3 l'élément qui se trouve dans j = 4 prend sa place du coup si je ne met pas j++ dans un else je ne test jamais l'élément qui se trouvait dans la position j = 4)
pour les types :
struct CELL  
{
 float densite;
 bool active;
 listFace listContribution;
 listFace listPenalite;
 CELL(){  
  densite = 0.0;
  active = false;
 }
};
struct ContrPenal
{
 int numFace;
 float area;
};
 
typedef vector <ContrPenal> listFace;

Ok merci de ces précisions je crois qu'on a ce qu'il faut pour se pencher sur ton cas
 
Je regarderai ce soir chez moi (peux pas faire de C++ la tt de suite)

Merci infiniment

Elles font quelle taille tes listFace?
 
Est-ce que l'ordre y est important?

On apprend plus ce qu'est un cache dans les écoles:
 
 for(int i=0; i < 64800; i++){
 for(int k = 0; k < 100; k++){
  if(cells[k][i].active == false) continue;
 
change tes cell[k][i) en cell[i][k] et tu evitera de faire des accés avec des strides de 64800 elements par lignes de caches ...

@ Un Programmeur : les listFace sont dynamique  je ne connais pas leur taille au préalable

Yep.

ilelle tu ne dois pas oublier qu'en interne ton tableau est à une dimension, ton
    cells[row][col]
est un accès dans un tableau à une dimension, à la case
    col + row * maxcols

En faisant cells[k][i] à chaque k++ tu avances violemment dans ce tableau à une dimension
En faisant cells[i][k] à chaque k++ tu avances juste jusqu'au prochain 'word' en mémoire.

Le 2ème cas est beaucoup plus intéressant pour toi car les données sont déjà en cache prêtes à l'emploi.
Dans le 1er cas des données sont mises en cache pour rien, vu qu'à chaque itération tu vas voir ailleurs (bien trop loin)

Je sais pas si je suis clair.
edit : http://igoro.com/archive/gallery-o [...] e-effects/

 
Meme si elles sont dynamiques, tu dois avoir une idee du nombre d'elements possibles dedans

@ Xavier_OM et Joel F : je vient de faire le test avec cells[i][k] au lieu de cells[k][i] mais le résultat est le même  

@ Un Programmeur : ah d'accord pour le nombre max c'est 21000

Si je ne m'abuse cells[i][k] est un invariant de ta double boucle externe. Je pense que la moindre des choses est d'utiliser un pointeur dessus, histoire de pas avoir à faire le calcul d'adressage 15000 fois comme tu le fais ici. Certains me diront p-ê  que le compilateur sait faire ça quand il optimise (au fait, as-tu mis toutes les options d'optimisation ?), mais au moins c'est plus lisible.

Donc dans ta double boucle, tu mets un
Cell *cell = &cells[i][k];
et ensuite tu accèdes à tout avec ->
 
Ensuite listContribution et listPenalite, c'est quoi comme structure de donnée ?
Tu as un soucis parce que ton algo fait à la fois de l'accès direct ET de la suppression sur ces structures. Or il n'y a pas de structure simple performante dans ces deux secteurs à la fois, à part un arbre AVL ou red-black (std::map ou std::set ou Boost). Si le test (cell.listPenalite[j].numFace == numface) est souvent positif, tu as pratiquement du O(n), et tu as intérêt à passer sur une structure d'arbre. Si ce test est rarement positif, tu as intérêt à garder un vector, surtout si leur taille n'est pas trop grande.
Mais de toute façon, ici je pense que tu devrais utiliser un iterator plutôt que j++ (s'il est pas invalidé par erase), voire à modifier ton algo, p-ê en mettant un booleen que tu testes plutôt que de faire un erase, par ex.

Xavier_OM: merci pour cette page

 
Pas mieux.

Très intéressant ton lien, Xavier_OM

il serait parfait si il comptait en cycle/element et non en temps/element :ð

de rien les gens  

Ce qu'il y a de bien, c'est les gens qui disent "j'ai un pb" mais à qui il faut tirer les vers du nez pour obtenir la moindre information pertinente, et puis qui disparaissent sans dire merci quand on prend la peine de leur fournir une réponse un tant soit peu argumentée.

@ el muchacho je n'ai pas disparu mais justement j'était entrain d'essayer les différentes solution que vous m'avez proposé, et d'ailleurs j'ai ouvert ce forum pour remercier toute personne  qui a contribué à résoudre mon problème (je suis pas ingrate comme même) grâce à vous (tout particulièrement les solutions de : Joel F, el muchacho, Xavier_OM) j'ai pu diminuer le temps d'exécution même s'il reste comme un peut long
Merci encore à toutes et à tous

J'ai deux ruses qui peuvent aider si tu gardes un vector pour listPenalite et listContribution:

1. parcourir le vector dans le sens end() -> begin(): si tu supprimes bcp d'éléments, ça fait déjà ça en moins à déplacer en mémoire à chaque fois. Encore une fois, c'est à comparer avec des structures d'arbre.

2. si l'ordre des éléments dans  listPenalite  n'a pas d'importance, tu appliques 1 et tu remplaces chaque élément à supprimer par le dernier élément du tableau et tu supprimes ce dernier.
  std::swap(listPenalite[j], listPenalite.back());
  listPenalite.pop_back();
Tu perds l'ordre du tableau, mais tu auras par contre une performance optimale.

(au passage, ça devrait marcher aussi en Java et en C#)

Merci el muchacho je vais essayer cette solution et je vous rends la réponse

Je pense que les intervenants seraient intéressés par le gain cumulé par chacune des améliorations proposées, pas juste une réponse binaire du style "c'est mieux" ou "c'est pas mieux". Mesurer est la base de l'optimisation.

Alors voila :
pour une itération de 62 qui fait appel à la fonction ajour j'aurai un temps d'exécution de 18563 ms.  
 

Par pitié, et par respect pour tes interlocuteurs, ne donne pas "juste l'essentiel" comme tu dis, mais élabore un minimum tes réponses.

62, ça veut dire quoi ? C'est la valeur de numFace ?
Et ça prenait combien de temps (à peu près) avant les optims ? Quelles optims as-tu implémentées ?
Au final, vu la teneur de ta réponse, on ne sait tjrs pas si la durée actuelle est satisfaisante ou pas. J'ai répondu à tes questions, merci de répondre au miennes. C'est le minimum que l'on peut attendre.

Je suis vraiment désolée de vous avoir dérangé et surtout mal exprimé( en fin j'ai l'habitude de ne pas trop parler    )  
bon 62 c'est le nombre d'appel de la fonction ajour avec un numFace quelqu'on que.
 
Je vient de changer l'insertion des données dans listContribution et listPenalite d'une façon que les données seront trié et j'ai changé le code de la fonction ajour comme suit :
void Loader::ajour(int numface)
{
 for(int k = minRho; k < maxRho; k++){
  for(int i=0; i < gridSize; i++){
   CELL *cell = &cells[i][k];
   
   if(cell->active == false) continue;
 
    int j = 0;
    while(j < cell->listContribution.size())
    {
     if(cell->listContribution[j].numFace > numface) break;
     if(cell->listContribution[j].numFace == numface)
     {
      cell->densite = cell->densite - cell->listContribution[j].area;
      cell->listContribution.erase(cell->listContribution.begin()+j);
      break;
     }
              j ++ ;
    }
 
    //Penalité
    j = 0;
    while(j < cell->listPenalite.size())
    {
     if(cell->listPenalite[j].numFace > numface) break;
     if(cell->listPenalite[j].numFace == numface)
     {
      cell->densite = cell->densite + pFactor*cell->listPenalite[j].area;
      cell->listPenalite.erase(cell->listPenalite.begin()+j);
      break;
     }
     j ++ ;
    }
   // désactivation de la cellule
   if(cell->listContribution.size() == 0) cell->active = false;
   
  }
 }
}
 
et Cette fois ci pour un nombre d'appel de la fonction ajour égale à 62 j'aurai un temps d'exécution = 7969 ms  
Je suis satisfaite de ce dernier résultat je crois que je vais me contenter de ça pour pouvoir continuer le reste de l'algorithme.
 
Je tiens à remercier tout le monde pour le temps et l'intérêt que vous avez porté à mon problème
Merci  
 
 

Allez, hop, c'est gratuit:
2 changements rapides:
1.le parcours dans le sens inverse, potentiellement plus rapide, et plus besoin de break;
2.contrib invariant de boucle --> variable.

@ el muchacho c'est supère pour un nombre d'appel de la fonction ajour égale à 62 j'aurai un temps d'exécution = 3188 ms au lieu de 7969 ms  
Merci infiniment