Эффективная стабильная сумма упорядоченных чисел

У меня есть довольно длинный список положительных чисел с плавающей точкой ( std::vector<float>, размер ~ 1000). Числа отсортированы в порядке убывания. Если я суммирую их в следующем порядке:

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

Я предполагаю, что у меня может быть некоторая проблема с числовой стабильностью, поскольку ближе к концу вектор sumбудет намного больше, чем v. Самым простым решением было бы пройти вектор в обратном порядке. Мой вопрос: это эффективно, так же как и передовой случай? У меня будет больше кеша не хватает?

Есть ли другое умное решение?

Я думаю, у меня может быть проблема с числовой стабильностью

Так что проверяйте это. В настоящее время у вас есть гипотетическая проблема, то есть проблема вообще отсутствует.

Если вы проверяете, и гипотетическая материализация превращается в реальную проблему, тогда вам стоит задуматься о том, чтобы ее исправить.

Это значит, что точность с плавающей запятой может вызвать проблемы, но вы можете проверить, действительно ли она влияет на ваши данные, прежде чем расставлять приоритеты над всеми остальными.

... у меня будет больше кеша не хватает?

Одна тысяча операций с плавающей запятой - 4 КБ - она ​​будет помещаться в кэш в современной системе массового рынка (если у вас есть другая платформа, расскажите нам, что это).

Единственный риск состоит в том, что средство предварительной выборки не поможет вам при выполнении итерации в обратном направлении, но, конечно, ваш вектор уже может быть в кеше. Вы не можете определить это до тех пор, пока не создадите профиль в контексте своей полной программы, поэтому бесполезно беспокоиться об этом, пока у вас не будет полной программы.

Есть ли другое умное решение?

Не беспокойтесь о вещах, которые могут стать проблемами, пока они действительно не станут проблемами. Самое большее, стоит отметить возможные проблемы и структурировать ваш код так, чтобы вы могли позже заменить простейшее решение на тщательно оптимизированное, не переписывая все остальное.

Я протестировал ваш вариант использования, и результаты (см. Прилагаемое изображение) указывают на то, что при выполнении цикла вперед или назад не будет никакой разницы в производительности.

Возможно, вы захотите измерить на вашем оборудовании + компилятор.

Использование STL для вычисления суммы - это так же быстро, как ручное циклическое перемещение по данным, но гораздо более выразительное.

используйте следующее для обратного накопления:

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

в то время как для прямого накопления:

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

Самым простым решением было бы пройти вектор в обратном порядке. Мой вопрос: это эффективно, так же как и передовой случай? У меня будет больше кеша не хватает?

Да, это эффективно. Предсказание ветвей и стратегия интеллектуального кэширования на вашем оборудовании настроены для последовательного доступа. Вы можете смело накапливать свой вектор:

#include <numeric>

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

Для этого вы можете использовать обратный итератор без каких-либо транспозиций в вашем std::vector<float> vec:

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

Или сделайте ту же работу, используя стандартный алгоритм:

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

Производительность должна быть одинаковой, меняется только направление обхода вашего вектора

Если под числовой стабильностью вы подразумеваете точность, то да, у вас могут возникнуть проблемы с точностью. В зависимости от соотношения самых больших и самых маленьких значений и ваших требований к точности в результате, это может быть или не быть проблемой.

Если вы хотите иметь высокую точность, рассмотрите суммирование по Кахану - для компенсации ошибок используется дополнительный float. Существует также парное суммирование .

Для подробного анализа компромисса между точностью и временем, см. Эту статью .

ОБНОВЛЕНИЕ для C ++ 17:

Несколько других ответов упоминают std::accumulate. Начиная с C ++ 17 существуют политики выполнения, которые позволяют распараллеливать алгоритмы.

Например

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

Это должно ускорить суммирование больших наборов данных за счет недетерминированных ошибок округления (я предполагаю, что пользователь не сможет определить разбиение потока).