Различие стандартных алгоритмов std::inclusive_scan и std::partial_sum
std::exclusive_scan- подобна std::partial_sum, не включает i-й элемент в i-ю "сумму"
С этим все ясно, но вот:
std::inclusive_scan- (C++17) подобна std::partial_sum, включает i-й элемент в i-ю "сумму"
Не очень понятно. И простая программа:
int arr[10] = { 2, 4, 6, 7, 3, 5, 1, 8, 9, 10 },
arr1[10];
std::exclusive_scan(arr, arr + 10, arr1, 0);
//функция выводит все элементы последовательности
show(arr1); //0 2 6 12 19 22 27 28 36 45
std::partial_sum(arr, arr + 10, arr1);
show(arr1); //2 6 12 19 22 27 28 36 45 55
std::inclusive_scan(arr, arr + 10, arr1);
show(arr1); //2 6 12 19 22 27 28 36 45 55
показывает, что std::inclusive_scan выдает результат тот же, что и std::partial_sum
- И с чем связана необходимость существования этого алгоритма?
- Когда может быть удобнее применение
std::inclusive_scanвместоstd::partial_sum?
(можно просто привести пример кода)
Ответы (1 шт):
Первая разница небольшая - partial_sum не имеет начального значения. inclusive_scan - имеет.
Вторая разница - это в особенностях "бинарной операции", которая может быть передана отдельным параметром. Если бинарная операция не является ассоциативной, то в случае partial_sum результат будет "предсказуемый", а для inclusive_scan - нет, так как оно может суммировать (точнее, применять бинарную операцию) в "произвольном порядке"
https://en.cppreference.com/w/cpp/algorithm/inclusive_scan
In other words, the summation operations may be performed in arbitrary order, and the behavior is nondeterministic if binary_op is not associative.
ассоциативность - это следующее свойство (a+b)+c == a+(b+c)