Wydajna stabilna suma uporządkowanych liczb

Mam dość długą listę liczb zmiennoprzecinkowych dodatnich ( std::vector<float>rozmiar ~ 1000). Liczby są sortowane według malejącej kolejności. Jeśli sumuję je zgodnie z kolejnością:

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

Myślę, że mogę mieć problem ze stabilnością numeryczną, ponieważ blisko końca wektora sumbędzie znacznie większy niż v. Najłatwiejszym rozwiązaniem byłoby przejście wektora w odwrotnej kolejności. Moje pytanie brzmi: czy jest to równie skuteczne, co sprawa do przodu? Brakuje mi więcej pamięci podręcznej?

Czy jest jakieś inne inteligentne rozwiązanie?

Chyba mogę mieć problem ze stabilnością liczbową

Przetestuj to. Obecnie masz hipotetyczny problem, to znaczy żaden problem.

Jeśli wykonasz test, a hipotetyczny materializuje się w rzeczywisty problem, powinieneś się martwić o jego naprawienie.

To znaczy - precyzja zmiennoprzecinkowa może powodować problemy, ale możesz potwierdzić, czy to naprawdę dotyczy twoich danych, zanim ustalisz priorytet nad wszystkim innym.

... Brakuje mi więcej pamięci podręcznej?

Tysiąc liczb zmiennoprzecinkowych to 4Kb - zmieści się w pamięci podręcznej na nowoczesnym systemie masowego rynku (jeśli masz na myśli inną platformę, powiedz nam, co to jest).

Jedynym ryzykiem jest to, że moduł pobierania wstępnego nie pomoże ci podczas iteracji wstecz, ale oczywiście twój wektor może już znajdować się w pamięci podręcznej. Naprawdę nie możesz tego ustalić, dopóki nie utworzysz profilu w kontekście pełnego programu, więc nie ma sensu się tym martwić, dopóki nie masz pełnego programu.

Czy jest jakieś inne inteligentne rozwiązanie?

Nie martw się o rzeczy, które mogą stać się problemami, dopóki nie staną się problemami. Warto co najwyżej zwrócić uwagę na możliwe problemy i ustrukturyzować kod, aby później zastąpić najprostsze możliwe rozwiązanie dokładnie zoptymalizowanym, bez konieczności ponownego pisania wszystkiego.

I ława oznakowane przypadku użycia oraz wyniki (patrz załączony obrazek) punkt do kierunku, że nie ma żadnej różnicy wydajności do pętli do przodu lub do tyłu.

Możesz także zmierzyć na swoim sprzęcie + kompilatorze.

Używanie STL do wykonania sumy jest tak szybkie jak ręczne zapętlanie danych, ale o wiele bardziej wyraziste.

użyj poniższej metody do akumulacji wstecznej:

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

natomiast w przypadku akumulacji do przodu:

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

Najłatwiejszym rozwiązaniem byłoby przejście wektora w odwrotnej kolejności. Moje pytanie brzmi: czy jest to równie skuteczne, co sprawa do przodu? Brakuje mi więcej pamięci podręcznej?

Tak, jest wydajny. Prognozowanie rozgałęzień i strategia inteligentnej pamięci podręcznej ze sprzętu jest dostosowana do sekwencyjnego dostępu. Możesz bezpiecznie zgromadzić swój wektor:

#include <numeric>

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

W tym celu możesz użyć iteratora wstecznego bez żadnych transpozycji w std::vector<float> vec:

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

Lub wykonaj tę samą pracę przy użyciu standardowego algorytmu:

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

Wydajność musi być taka sama, zmieniona tylko kierunek obejścia wektora

Jeśli przez stabilność liczbową rozumiesz dokładność, to tak, możesz mieć problemy z dokładnością. W zależności od stosunku wartości największych do najmniejszych oraz wymagań dotyczących dokładności wyniku może to stanowić problem.

Jeśli chcesz mieć wysoką dokładność, zastanów się nad sumowaniem Kahana - używa to dodatkowej liczby zmiennoprzecinkowej do kompensacji błędów. Istnieje również sumowanie parami .

Aby uzyskać szczegółową analizę kompromisu między dokładnością a czasem, zobacz ten artykuł .

AKTUALIZACJA dla C ++ 17:

W kilku innych odpowiedziach wspomniano std::accumulate. Od wersji C ++ 17 istnieją zasady wykonywania które pozwalają na równoległe działanie algorytmów.

Na przykład

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

Powinno to przyspieszyć sumowanie dużych zestawów danych kosztem niedeterministycznych błędów zaokrąglania (zakładam, że użytkownik nie będzie w stanie określić partycjonowania wątków).