J'ai une assez longue liste de nombres positifs à virgule flottante ( std::vector<float>
, taille ~ 1000). Les nombres sont triés par ordre décroissant. Si je les additionne suite à la commande:
for (auto v : vec) { sum += v; }
Je suppose que je peux avoir un problème de stabilité numérique, car près de la fin du vecteur sum
sera beaucoup plus grand que v
. La solution la plus simple serait de traverser le vecteur dans l'ordre inverse. Ma question est la suivante: est-ce efficace ainsi que le cas avancé? J'aurai plus de cache manquant?
Existe-t-il une autre solution intelligente?
c++
floating-point
precision
Ruggero Turra
la source
la source
Réponses:
Alors testez-le. Actuellement, vous avez un problème hypothétique, c'est-à-dire aucun problème du tout.
Si vous testez et que l'hypothétique se matérialise en un problème réel , vous devez vous soucier de le corriger.
C'est-à-dire que la précision en virgule flottante peut causer des problèmes, mais vous pouvez confirmer si cela s'applique vraiment à vos données, avant de prioriser cela sur tout le reste.
Un millier de flotteurs est de 4 Ko - il trouvera sa place dans le cache d'un système de marché de masse moderne (si vous avez une autre plateforme en tête, dites-nous de quoi il s'agit).
Le seul risque est que le préfiltre ne vous aide pas lors de l'itération en arrière, mais bien sûr votre vecteur peut déjà être dans le cache. Vous ne pouvez pas vraiment déterminer cela avant d'avoir un profil dans le contexte de votre programme complet, il est donc inutile de s'en inquiéter jusqu'à ce que vous ayez un programme complet.
Ne vous inquiétez pas des choses qui pourraient devenir des problèmes, jusqu'à ce qu'elles deviennent réellement des problèmes. Tout au plus, il convient de noter les problèmes possibles et de structurer votre code afin de pouvoir remplacer la solution la plus simple possible par une solution soigneusement optimisée plus tard, sans réécrire tout le reste.
la source
J'ai comparé votre cas d'utilisation et les résultats (voir l'image ci-jointe) indiquent que cela ne fait aucune différence de performance pour boucler en avant ou en arrière.
Vous voudrez peut-être également mesurer sur votre matériel + compilateur.
L'utilisation de STL pour effectuer la somme est aussi rapide qu'une boucle manuelle sur des données mais beaucoup plus expressive.
utilisez ce qui suit pour une accumulation inverse:
tandis que pour l'accumulation vers l'avant:
la source
state
boucle est chronométrée.Oui c'est efficace. La prédiction de branche et la stratégie de cache intelligent de votre matériel sont réglées pour un accès séquentiel. Vous pouvez accumuler votre vecteur en toute sécurité:
la source
À cette fin, vous pouvez utiliser l'itérateur inversé sans transposition dans votre
std::vector<float> vec
:Ou faites le même travail en utilisant l'algorithme standard:
Les performances doivent être les mêmes, modifié uniquement la direction de contournement de votre vecteur
la source
Si par stabilité numérique vous entendez la précision, alors oui, vous pouvez vous retrouver avec des problèmes de précision. Selon le rapport des valeurs les plus grandes aux plus petites, et vos exigences de précision dans le résultat, cela peut ou non être un problème.
Si vous voulez avoir une grande précision, envisagez la sommation de Kahan - cela utilise un flotteur supplémentaire pour la compensation des erreurs. Il existe également une sommation par paire .
Pour une analyse détaillée du compromis entre précision et temps, consultez cet article .
MISE À JOUR pour C ++ 17:
Quelques autres réponses mentionnent
std::accumulate
. Depuis C ++ 17, il existe des politiques d'exécution qui permettent de paralléliser les algorithmes.Par exemple
Cela devrait accélérer la sommation de grands ensembles de données au prix d'erreurs d'arrondi non déterministes (je suppose que l'utilisateur ne pourra pas déterminer le partitionnement des threads).
la source