На сайте вакансий Яндекса предлагают вычислить сумму элементов массива и предлагают три варианта решения задачи. Эти примеры намеренно не оптимальны и существует лучшее решение задачи. Рассмотрим сначала предлагаемый вариант решения:
1
2
3
4
5
6
7
8
9
10
11
double sum1(std::vector<double>& v)
{
if (v.empty()) {
return 0.0;
}
for(size_t i = 0; i < v.size() - 1; ++i) {
std::sort(v.begin()+i, v.end());
v[i+1] += v[i];
}
return v.back();
}
Сразу бросается в глаза сортировка при суммировании следующего элемента. Это требуется чтобы суммировались сначала меньшие числа. Точности double не хватает для данных вычислений, поэтому если поступить иначе и складывать числа от больших к меньшим, то при добавлении маленьких чисел они могут быть денормализованы с огромной ошибкой.
Предлагаемые Яндексом варианты можно посмотреть тут.
Для оценки этой ошибки напишем простую тестовую программу:
1
2
3
4
5
6
7
8
9
const double x = 0.01; // суммируем эту величину 10000 раз
double sum = 1000000000.0; // начальное значение суммы
for (int i = 0; i < 10000; ++i ) {
sum = sum + x;
}
const double error = 1000000100.0 - sum;
std::cout << error << std::endl;
Результат: 9.53674e-05
Если не компенсировать эту ошибку и продолжать работать таким образом, то рано или поздно результат будет содержать ошибку во всех разрядах. Простое суммирование чисел в худшем случае имеет ошибку, которая растет пропорционально n, и среднеквадратичную ошибку, которая растет как √n на случайных данных.
Есть вариант решения данной задачи не за линейно-логарифмическое время O(n*logn), а за линейное O(n). Данный алгоритм предложил автора стандарта IEEE 754, Уильям Мортон Кэхэн (Kahan). Он разработал алгоритм для минимизации ошибки при сложении чисел в представлении IEEE 754, который был назван в его честь. Вот пример его реализации:
1
2
3
4
5
6
7
8
9
10
11
12
13
const double x = 0.01;
double e = 0; // будем держать ошибку тут. Начальная ошибка 0
double sum = 1000000000.; // начальное значение суммы
for (int i = 0; i < 10000; ++i ) {
const double y = x - e; // компенсируем ошибку
const double t = sum + y;
e = (t - sum) - y; // сохраним новую ошибку
sum = t;
}
const double error = 1000000100. - sum;
std::cout << error << std::endl;
Результат: 0
При суммировании с компенсацией в худшем случае ошибка не зависит от n, поэтому большие числа могут быть сложены с ошибкой, которая зависит только от точности типа с плавающей точкой.