Wydajna stabilna suma uporządkowanych liczb


12

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?


1
Szybko odpowiedzieć na pytanie. Benchmark to.
Davide Spataro

Czy prędkość jest ważniejsza niż dokładność?
surowy

Niezupełnie duplikat, ale bardzo podobne pytanie: suma serii za pomocą float
acraig5075,

4
Być może będziesz musiał zwrócić uwagę na liczby ujemne.
AProgrammer

3
Jeśli naprawdę zależy Ci na precyzji w wysokim stopniu, sprawdź podsumowanie Kahana .
Max Langhof,

Odpowiedzi:


3

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.


5

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

wprowadź opis zdjęcia tutaj


ta strona jest super fajna. Dla pewności: nie mierzysz losowego generowania, prawda?
Ruggero Turra,

Nie, tylko część w statepętli jest mierzona czasowo.
Davide Spataro

2

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

2
Czy możesz wyjaśnić: w tym kontekście „dostęp sekwencyjny” oznacza przewijanie do przodu, do tyłu lub jedno i drugie?
Ruggero Turra

1
@RuggeroTurra Nie mogę, dopóki nie znajdę źródła i nie mam teraz ochoty czytać kart danych procesora.
YSC

@RuggeroTurra Zwykle dostęp sekwencyjny oznaczałby przesyłanie dalej. Wszystkie na wpół przyzwoite moduły pobierania danych przechwytują sekwencyjny dostęp do przodu.
Szczoteczka do zębów

@Toothbrush, dzięki. Tak więc, jeśli zapętlę się do tyłu, w zasadzie może to być problem z wydajnością
Ruggero Turra

Zasadniczo, przynajmniej na niektórych urządzeniach, jeśli cały wektor nie znajduje się już w pamięci podręcznej L1.
Bezużyteczne

2

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


Popraw mnie, jeśli się mylę, ale myślę, że jest to nawet bardziej wydajne niż polecenie Foreach, którego używa OP, ponieważ wprowadza narzut. YSC ma rację co do części liczbowej stabilności, tys.
sephiroth

4
@sephiroth Nie, żaden na wpół przyzwoity kompilator tak naprawdę nie będzie dbał o to, czy napisałeś range-for czy iterator.
Max Langhof,

1
Rzeczywista wydajność zdecydowanie nie jest taka sama z powodu buforowania / pobierania wstępnego. Rozsądne jest, aby OP był ostrożny.
Max Langhof,

1

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.