Soma estável eficiente de números ordenados

Eu tenho uma lista bastante longa de números positivos de ponto flutuante ( std::vector<float>, tamanho ~ 1000). Os números são classificados em ordem decrescente. Se eu somar eles seguindo a ordem:

for (auto v : vec) { sum += v; }

Acho que posso ter algum problema de estabilidade numérica, já que perto do final do vetor sumserá muito maior que v. A solução mais fácil seria atravessar o vetor na ordem inversa. Minha pergunta é: isso é eficiente e também o caso a seguir? Faltarei mais cache?

Existe alguma outra solução inteligente?

Eu acho que posso ter algum problema de estabilidade numérica

Então teste para isso. Atualmente, você tem um problema hipotético, ou seja, nenhum problema.

Se você testar, e o hipotético se materializar em um problema real , deverá se preocupar em corrigi-lo.

Ou seja, a precisão de ponto flutuante pode causar problemas, mas você pode confirmar se realmente faz com seus dados, antes de priorizar isso sobre todo o resto.

... Faltarei mais cache?

Milhares de carros alegóricos são 4Kb - caberão no cache de um sistema moderno de mercado de massa (se você tiver outra plataforma em mente, diga-nos o que é).

O único risco é que o pré-buscador não o ajude ao iterar para trás, mas é claro que seu vetor já pode estar no cache. Você realmente não pode determinar isso até criar um perfil no contexto de seu programa completo, portanto não adianta se preocupar com isso até ter um programa completo.

Existe alguma outra solução inteligente?

Não se preocupe com coisas que podem se tornar problemas, até que elas realmente se tornem problemas. No máximo, vale a pena observar possíveis problemas e estruturar seu código para que você possa substituir a solução mais simples possível por uma cuidadosamente otimizada posteriormente, sem reescrever todo o resto.

I banco marcado seu caso de uso e os resultados (ver imagem em anexo) apontam para a direção que não faz qualquer diferença de desempenho para fazer um loop para a frente ou para trás.

Você também pode medir no seu hardware + compilador.

O uso do STL para realizar a soma é tão rápido quanto o loop manual dos dados, mas muito mais expressivo.

use o seguinte para acumulação reversa:

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

enquanto para acumulação direta:

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

A solução mais fácil seria atravessar o vetor na ordem inversa. Minha pergunta é: isso é eficiente e também o caso a seguir? Faltarei mais cache?

Sim, é eficiente. A previsão de ramificação e a estratégia de cache inteligente do seu hardware são ajustadas para acesso seqüencial. Você pode acumular com segurança seu vetor:

#include <numeric>

auto const sum = std::accumulate(crbegin(v), crend(v), 0.f);

Para esse fim, você pode usar o iterador reverso sem nenhuma transposição no seu std::vector<float> vec:

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

Ou faça o mesmo trabalho usando o algoritmo padrão:

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

O desempenho deve ser o mesmo, alterado apenas na direção de desvio do seu vetor

Se por estabilidade numérica você quer dizer precisão, sim, você pode acabar com problemas de precisão. Dependendo da proporção do maior para o menor, e de seus requisitos de precisão no resultado, isso pode ou não ser um problema.

Se você deseja ter alta precisão, considere o somatório de Kahan - isso usa um flutuador extra para compensação de erro. Também há somas aos pares .

Para uma análise detalhada da troca entre precisão e tempo, consulte este artigo .

ATUALIZAÇÃO para C ++ 17:

Algumas das outras respostas mencionam std::accumulate. Desde o C ++ 17, existem políticas de execução que permitem que os algoritmos sejam paralelizados.

Por exemplo

#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';
}

Isso deve tornar a soma de conjuntos de dados grandes mais rápida, com o custo de erros de arredondamento não determinísticos (suponho que o usuário não consiga determinar o particionamento do encadeamento).