Accéleration des calculs

**Onimaru** · 13/03/2012, 19h27

Salut à tous,
Je veux générer tous les chemins et cycles possibles d'un graphe, or ce problème est NP-Complet, il consomme donc beaucoup de temps et de ressources. J'ai implémenté une solution en utilisant les tableaux dynamiques, les threads et les fichiers binaires, elle marche mais pour un certain nombre élevé de nœuds (sommets) le programme plante totalement.
Comment faire pour optimiser les calculs ???
Est ce que TMemoryStream et TFileStream peuvent aider à améliorer les performances ???

**ShaiLeTroll** · 13/03/2012, 19h39

Si D7, pense que la réallocation par SetLength de Tableau dynamique c'est une opération très couteuse !
Si FastMM ou D2007+, c'est entre 100 et 1000 fois plus rapide !

Si cela consomme beaucoup de mémoire (genre en Go) et que cela utilise le SWAP, faire directement certaine manipulation sur un fichier sera plus rapide, j'avais observé cela dans le sujet Test possibilités possible longue boucle
Je dis ça pour une mahcine avec 512Mo de RAM, quand je suis passé à 4Go, la machine était globalement 2 à 5 fois plus rapide (mon ressenti), sur des algos gourmand en RAM, c'était un facteur x100 car tout pouvait rester en RAM

**Onimaru** · 13/03/2012, 19h46

Envoyé par ShaiLeTroll

Si D7, pense que la réallocation par SetLength de Tableau dynamique c'est une opération très couteuse !
Si FastMM ou D2007+, c'est entre 100 et 1000 fois plus rapide !

Si cela consomme beaucoup de mémoire (genre en Go) et que cela utilise le SWAP, faire directement certaine manipulation sur un fichier sera plus rapide, j'avais observé cela dans le sujet Test possibilités possible longue boucle
Je dis ça pour une mahcine avec 512Mo de RAM, quand je suis passé à 4Go, la machine était globalement 2 à 5 fois plus rapide (mon ressenti), sur des algos gourmand en RAM, c'était un facteur x100 car tout pouvait rester en RAM

Merci.
C'est quoi FastMM ??? est ce qu'il peut aider dans ce problème ???

**Andnotor** · 13/03/2012, 23h20

J'ai relu plusieurs fois la question et j'ai toujours rien compris

**ShaiLeTroll** · 14/03/2012, 09h38

FastMM 1er lien de

Son problème si j'ai bien compris, c'est qu'il calcule tous les chemins possibles dans un Graphe, un algo de PathFinding, et qu'ils stockent ces chemins quelque part !
Déjà qu'un simple PathFinding c'est long, alors chercher tous les chemins, c'est de la combinatoire, le nombre de combinaison est exponentielle !