Somme stable efficace de nombres ordonnés

12

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 sumsera 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?

Ruggero Turra
la source
1
La question de vitesse est facile à répondre. Comparez-le.
Davide Spataro
La vitesse est-elle plus importante que la précision?
Stark
Pas tout à fait un double, mais une question très similaire: somme des séries utilisant float
acraig5075
4
Vous devrez peut-être faire attention aux nombres négatifs.
AProgrammer
3
Si vous vous souciez réellement de la précision à des degrés élevés, consultez la somme de Kahan .
Max Langhof

Réponses:

3

Je suppose que je peux avoir un problème de stabilité numérique

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.

... J'aurai plus de cache manquant?

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.

Existe-t-il une autre solution intelligente?

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.

Inutile
la source
5

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:

std::accumulate(rbegin(data), rend(data), 0.0f);

tandis que pour l'accumulation vers l'avant:

std::accumulate(begin(data), end(data), 0.0f);

entrez la description de l'image ici

Davide Spataro
la source
ce site est super cool. Juste pour être sûr: vous ne chronométrez pas la génération aléatoire, non?
Ruggero Turra
Non, seule la partie de la stateboucle est chronométrée.
Davide Spataro
2

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?

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é:

#include <numeric>

auto const sum = std::accumulate(crbegin(v), crend(v), 0.f);
YSC
la source
2
Pouvez-vous préciser: dans ce contexte, "accès séquentiel" signifie en avant, en arrière ou les deux?
Ruggero Turra
1
@RuggeroTurra Je ne peux pas sauf si je peux trouver une source, et je ne suis pas d'humeur à lire les fiches techniques du CPU pour le moment.
YSC
@RuggeroTurra Habituellement, un accès séquentiel signifie vers l'avant. Tous les pré-récupérateurs de mémoire semi-décents interceptent un accès séquentiel avancé.
Brosse à dents
@Toothbrush, merci. Donc, si je boucle en arrière, en principe, cela peut être un problème de performance
Ruggero Turra
En principe, sur au moins certains matériels, si le vecteur entier n'est pas déjà dans le cache L1.
inutile
2

À cette fin, vous pouvez utiliser l'itérateur inversé sans transposition dans votre std::vector<float> vec:

float sum{0.f};
for (auto rIt = vec.rbegin(); rIt!= vec.rend(); ++rIt)
{
    sum += *rit;
}

Ou faites le même travail en utilisant l'algorithme standard:

float sum = std::accumulate(vec.crbegin(), vec.crend(), 0.f);

Les performances doivent être les mêmes, modifié uniquement la direction de contournement de votre vecteur

Malov Vladimir
la source
Corrigez-moi si je me trompe, mais je pense que c'est encore plus efficace que l'instruction foreach utilisée par OP, car elle introduit une surcharge. YSC a raison sur la partie stabilité numérique, tho.
sephiroth
4
@sephiroth Non, tout compilateur à moitié décent ne se souciera pas vraiment de savoir si vous avez écrit un range-for ou un itérateur pour.
Max Langhof
1
Les performances réelles ne sont décidément pas garanties d'être les mêmes, en raison des caches / prélecture. Il est raisonnable que le PO se méfie de cela.
Max Langhof
1

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

#include <vector>
#include <execution>
#include <iostream>
#include <numeric>

int main()
{  
   std::vector<double> input{0.1, 0.9, 0.2, 0.8, 0.3, 0.7, 0.4, 0.6, 0.5};

   double reduceResult = std::reduce(std::execution::par, std::begin(input), std::end(input));

   std:: cout << "reduceResult " << reduceResult << '\n';
}

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).

Paul Floyd
la source