Bonjour,

Dans le cadre d'un exercice je dois trouver un algorithme qui calcule la somme des éléments entre deux indices d'un tableau de 100 000 entiers, et il y au pire 100 000 ce ces sommes à calculer.

J'ai déjà essayé l'algorithme "naif" http://pastebin.com/nFZEeBjY mais il est trop lent à trouver la solution lorsque le nombre de sommes devient grand. Donc il me faut un algorithme plus rapide, j'en ai déjà essayé 2 autres mais ils étaient encore plus lent... Maintenant je n'ai plus d'idées donc j'aurais besoin d'un indice sur le type d'algorithme à utiliser. Je sais qu'il est possible d'obtenir un algorithme beaucoup plus rapide que le "naif" car quand je compile mon programme avec l'option -O1 dans g++ le programme devient largement assez rapide pour résoudre l'exercice, mais je n'ai aucune idée de ce que fait g++ pour arriver à ce résultat.

g++ ne fait aucune optimisation algorithmique. Au niveau du code source, tout ce que tu peux faire sans faire d'hypothèse sur ton architecture c'est de pré-calculer ta valeur d'arrêt (end-1) hors de la boucle, pour éviter qu'elle ne soit recalculée à chaque fois.

Ensuite le compilateur peut faire beaucoup de choses sympa à l'optimisation, notamment du loop-unrolling, des indices de branch-prediction, une meilleure utilisation du cache ou encore de l'utilisation d'instructions particulières de ton CPU permettant de traiter plusieurs données d'un coup. Ce sont des choses dont tu ne devrais pas vraiment te soucier au niveau du programme lui-même.

Ton programme est taggé comme C++, mais est presque entièrement codé en pur C. Si par contre tu comptes utiliser des fonctionnalités C++, la meilleure solution est de mettre des données dans un std::valaray et utiliser std::valarray::sum:

http://www.cplusplus.com/reference/valarray/valarray/sum/

J'ai écris une nouvelle fonction sum qui utilise valarray : http://pastebin.com/3bKj26pe

Mais le programme est deux fois plus lent qu'avant.

Merci de m'aider en tout cas

-O1 élimine l'utilisation outrancière de la pile.

http://goo.gl/690QaG
http://goo.gl/xZkP8y

J'ai trouvé la solution en fait, il fallait utiliser un tableau cumulatif http://pastebin.com/pUEmB33i

merci elite_2009 pour ce site