Левые свёртки и другие редукции (серия «114 алгоритмов C++»)

Добро пожаловать в пятую часть серии «114 стандартных алгоритмов C++». В этой главе мы поговорим об алгоритмах редукции, то есть об алгоритмах, которые сводят диапазон к одному значению.

В данной статье мы рассмотрим три группы алгоритмов: левые свёртки, работающие строго линейно, обобщенные редукции из C++17 и логические редукции. Мы также сделаем небольшое отступление и поговорим об особенностях смешивания числовых типов в C++.

Все алгоритмы, которые мы обсудим сегодня (за исключением логических редукций), взяты из заголовочного файла <numeric> и не имеют аналогов в библиотеке диапазонов C++20 (некоторая поддержка ожидается в C++23).

accumulate, inner_product

Начнём с левых свёрток, алгоритмов, которые работают строго слева направо, вычисляя для каждого элемента аккумулятор = op(аккумулятор, элемент) и возвращая конечное значение аккумулятора.

Из-за строго линейной работы у нас нет доступа к параллельным версиям этих алгоритмов. В версии accumulate по умолчанию используется бинарный operator+, а если он указан, этому бинарному функтору не разрешается изменять элементы в диапазоне или делать итераторы недействительными.

std::vector<int> data{1, 2, 3, 4, 5};
auto sum = std::accumulate(data.begin(), data.end(), 0);
// sum == 15
auto product = std::accumulate(data.begin(), data.end(), 1, std::multiplies<>{});
// product == 120

Чтобы превратить любой из алгоритмов левой свертки в правую свертку, мы можем использовать rbegin() и rend() (при условии, что диапазон двунаправленный).

std::vector<int> data{1, 2, 3, 4, 5};
auto left = std::accumulate(data.begin(), data.end(), 0, [](int acc, int el) {
    return acc / 2 + el;
});
auto right = std::accumulate(data.rbegin(), data.rend(), 0, [](int acc, int el) {
    return acc / 2 + el;
});
// left == 8, right == 3

Добавив еще один диапазон и операцию объединения, мы получаем inner_product. Операция левой свертки изменяется на аккумулятор = op(аккумулятор, объединение(элемент1, элемент2)), где элемент1 приходит из первого диапазона, а элемент2 – из второго диапазона.

Версия по умолчанию использует operator+ для накопления и operator* для объединения. Если они указаны, то ни одному функтору не разрешено изменять элементы или делать итераторы недействительными.

std::vector<int> heights{1, 2, 3, 4, 5};
std::vector<int> widths{2, 3, 4, 5, 6};
auto total_area = std::inner_product(heights.begin(), heights.end(), widths.begin(), 0);
// total_area == 70

Естественно, мы также можем использовать inner_product с одним диапазоном, например, для вычисления суммы модулей разностей между последовательными элементами:

std::vector<int> data{6, 4, 3, 7, 2, 1};
auto sum_of_diffs = std::inner_product(data.begin(), std::prev(data.end()), 
                                       std::next(data.begin()), 
                                       0, std::plus<>{}, 
                                       [](int left, int right) { return std::abs(left-right); });
// sum_of_diffs == 13

Небольшое отступление в сторону арифметики

Алгоритмы в заголовке <numeric> могут иметь неожиданные особенности. В основном это связано с тем, как C++ обрабатывает смешанные числовые типы, и как работает вывод шаблонов. Например, легко допустить следующую ошибку:

std::vector<double> data{1.1, 2.2, 3.3, 4.4, 5.5};
auto result = std::accumulate(data.begin(), data.end(), 0);
// result == 15 (реальная сумма 16.5)

Поскольку мы передаем 0 в качестве начального значения аккумулятора, который является константой типа int, аккумулятор оказывается типа int. Затем каждая операция свертки складывает число int и число double, в результате чего получается значение с плавающей запятой. Однако оно немедленно сохраняется в целочисленной переменной, усекая значение.

Если вы хотите избежать этой проблемы, вам нужно знать буквенные суффиксы:

• буквенные суффиксы для целых чисел;
• буквенные суффиксы для чисел с плавающей запятой;
• буквенные макросы для целых чисел фиксированного размера.

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

std::vector<unsigned> data{1, std::numeric_limits<unsigned>::max()/2};
auto ok = std::accumulate(data.begin(), data.end(), 0u, 
                          [](auto acc, auto el) { return acc + el; });
// Всегда OK, типы совпадают.

auto impl = std::accumulate(data.begin(), data.end(), 0, 
                            [](auto acc, auto el) { return acc + el; });
// Определяется реализацией:
// acc определяется как int
// в acc + el: acc приводится к unsigned, результат будет unsigned

// если значение без знака не может быть представлено целевой переменной
// со знаком, поведение определяется реализацией

auto maybe = std::accumulate(data.begin(), data.end(), 0L, 
                             [](auto acc, auto el) { return acc + el; });
// OK пока sizeof(long) > sizeof(unsigned)
// acc - это long
// в acc + el: el приводится к long

// если sizeof(long) > sizeof(unsigned), long может представлять 
// все значения unsigned; следовательно, всё OK

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

Если вас интересуют более подробные сведения о целочисленных преобразованиях и расширяющих приведениях, на эту тему есть статья «Продвижение целочисленных типов и типов с плавающей запятой».

partial_sum

Алгоритм partial_sum здесь немного выделяется, так как это не алгоритм строгой редукции. Вместо этого он вычисляет частичные суммы в заданном диапазоне. n-ый сгенерированный элемент представляет собой сумму первых n элементов из исходного диапазона.

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

std::vector<int> data(6, 1);
// data == {1, 1, 1, 1, 1, 1}
std::partial_sum(data.begin(), data.end(), data.begin());
// data == {1, 2, 3, 4, 5, 6}

std::vector<int> out;
std::partial_sum(data.begin(), data.end(), std::back_inserter(out), std::multiplies<>{});
// out == {1, 2, 6, 24, 120, 720}

reduce, transform_reduce

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

Однако, когда мы работаем с ассоциативными операциями op(a, op(b,c)) == op(op(a,b),c) и коммутативными операциями op(a,b) == op(b,a), на самом деле не имеет значения, при каких перестановке элементов и порядке операций мы выполняем вычисление, мы всегда придем к одному и тому же результату.

В C++17, наряду с другими параллельными алгоритмами, мы получили reduce, inclusive_scan и exclusive_scan, которые являются смягченными версиями accumulate, inner_product и partial_sum, которые для получения детерминированных результатов требуют ассоциативной и коммутативной операций.

Вдобавок к эквивалентам accumulate мы получаем еще одну перегрузку, которая удаляет начальное значение аккумулятора, устраняя упомянутые выше проблемы с числами.

std::vector<double> data{1.1, 2.2, 3.3, 4.4, 5.5};
auto result = reduce(data.begin(), data.end());
// result == 16.5

Аккумулятор будет иметь тип элементов диапазонов и будет инициализирован значением по умолчанию. Таким образом, в этом примере аккумулятор будет иметь тип double и инициализироваться нулем.

Конечно, это также работает для пользовательских типов:

struct Duck {
    std::string sound = "Quack";
    friend Duck operator+(const Duck& left, const Duck& right) {
        return {left.sound+right.sound};
    }
};

std::vector<Duck> data(2, Duck{});
Duck final_duck = std::reduce(data.begin(), data.end());
// final_duck.sound == "QuackQuackQuack"

Начальное значение аккумулятора будет "Quack". Добавляя двух других уток, мы получаем "QuackQuackQuack".

Аналогом inner_product является transform_reduce с дополнительными перегрузками для унарного случая (один диапазон).

Так же, как и в reduce, предоставляемые функторы не должны изменять элементы или делать итераторы недействительными. Кроме того, функтор редукции должен быть ассоциативным и коммутативным.

std::vector<int> data{1, 2, 3, 4, 5};
auto sum_of_squares = std::transform_reduce(data.begin(), data.end(), 0, 
                                            std::plus<>{}, [](int v) { return v*v; });
// sum_of_squares == 55

std::vector<int> coef{1, -1, 1, -1, 1};
auto result = std::transform_reduce(data.begin(), data.end(), coef.begin(), 0);
// result == 1*1 + 2*(-1) + 3*1 + 4*(-1) + 5*1 == 3

exclusive_scan, inclusive_scan, transform_exclusive_scan, transform_inclusive_scan

Последний алгоритм левой свертки пока без параллельной противоположности – partial_sum.

Противоположность 1:1 к partial_sum – это inclusive_scan, который следует той же логике: n-ый сгенерированный элемент – это сумма первых n исходных элементов. Вдобавок ко всему, мы также получаем exclusive_scan, где n-ый сгенерированный элемент является суммой первых n-1 исходных элементов. То есть инклюзивная версия включает элемент на n-ой позиции, а эксклюзивная версия исключает его.

Следовательно, для алгоритма exclusive_scan мы должны указать начальное значение аккумулятора, которое будет значением первого сгенерированного элемента.

std::vector<int> src{1, 2, 3, 4, 5, 6};
{
    std::vector<int> out;
    std::inclusive_scan(src.begin(), src.end(), std::back_inserter(out));
    // out == {1, 3, 6, 10, 15, 21}
    std::inclusive_scan(src.begin(), src.end(), out.begin(), std::multiplies<>{}, 1);
    // out == {1, 2, 6, 24, 120, 720}
}
{
    std::vector<int> out;
    std::exclusive_scan(src.begin(), src.end(), std::back_inserter(out), 0);
    // out == {0, 1, 3, 6, 10, 15}
    std::exclusive_scan(src.begin(), src.end(), out.begin(), 1, std::multiplies<>{});
    // out == {1, 1, 2, 6, 24, 120}
}

Варианты преобразования inclusive_scan и exclusive_scan применяют унарное преобразование к каждому элементу. К сожалению, у нас не получается перегрузка, которая оперировала бы двумя входными диапазонами (в стиле inner_product).

std::vector<int> data{-10, 3, -2, 5, 6};

std::vector<int> out1;
std::inclusive_scan(data.begin(), data.end(), std::back_inserter(out1), 
                    std::plus<>{});
// out1 == {-10, -7, -9, -4, 2}

std::vector<int> out2;
std::transform_inclusive_scan(data.begin(), data.end(), std::back_inserter(out2), 
                              std::plus<>{}, [](int v) { return std::abs(v); });
// out2 == {10, 13, 15, 20, 26}

all_of, any_of, none_of

Наконец, мы возвращаемся к заголовку <algorithm>, где у нас есть три логических редукции.

Эти алгоритмы следуют ожидаемой логической логике.

Обратите внимание, что any_of требует положительного присутствия; он возвращает значение true только в том случае, если существует хотя бы один элемент, для которого предикат возвращает значение true, и значение false для пустого диапазона.

Спасибо за чтение

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

Теги