Улучшение функции сгиба - PullRequest
1 голос
/ 21 октября 2019

Я реализовал простую функцию свертывания в C ++, которая принимает лямбду и может сворачивать несколько векторов одновременно во время компиляции. Мне интересно, можно ли это каким-то образом упростить (я предоставил как рекурсивную, так и итеративно рекурсивную версию - я не уверен, что должна иметь лучшую производительность): https://godbolt.org/z/39pW81

Также приветствуются оптимизации производительности -в связи с этим любой из двух подходов быстрее?

template<int I, typename type_identity, typename type_head, int N, typename ...type_tail, int ...N_tail,  typename Function>
auto foldHelperR(Function&& func, const type_identity& id, const tvecn<type_head, N>& head, const tvecn<type_tail, N_tail>&... tail)
{
    if constexpr (I>0)
    {
        return func(foldHelperR<I-1>(std::forward<Function>(func), id, head, tail...), head[I], tail[I]...);
    }
    else
    {
        return func(id, head[0], tail[0]...);
    }
}

template<int I, typename type_identity, typename type_head, int N, typename ...type_tail, int ...N_tail,  typename Function>
auto foldHelperI(Function&& func, const type_identity id, const tvecn<type_head, N>& head, const tvecn<type_tail, N_tail>&... tail)
{
    if constexpr (I<N-1)
    {
        return foldHelperI<I+1>(std::forward<Function>(func), func(id, head[I], tail[I]...), head, tail...);
    }
    else
    {
        return func(id, head[N-1], tail[N-1]...);
    }
}

template<typename type_identity, typename type_head, int N_head, typename ...type_tail, int ...N_tail, typename Function = void (const type_identity&, const type_head&, const type_tail&...)>
constexpr auto fold(Function&& func, const type_identity& id, const tvecn<type_head, N_head>& head, const tvecn<type_tail, N_tail>&... tail)
{
    static_assert(std::is_invocable_v<Function, const type_identity&, const type_head&, const type_tail &...>,
     "The function cannot be invoked with these zip arguments (possibly wrong argument count).");
    static_assert(all_equal_v<N_head, N_tail...>, "Vector sizes must match.");

    //return foldHelperR<N_head-1>(std::forward<Function>(func), id, head, tail...);
    return foldHelperI<0>(std::forward<Function>(func), id, head, tail...);
}

int main()
{
    tvecn<int,3> a(1,2,3);
    return fold([](auto x, auto y, auto z) {return x+y+z;}, 0, a, a);
}

Ответы [ 2 ]

3 голосов
/ 21 октября 2019

и может сложить несколько векторов одновременно во время компиляции

Не совсем так: если вы хотите работать во время компиляции

(1), вы должныопределить constexpr конструктор tvecn и

(2) вы должны определить constexpr функцию foldhelper и

(3) вы должны объявить constexpr a

 // VVVVVVVVV
    constexpr tvecn<int,3> a(1,2,3);

(4) Вы должны поместить результат сгиба в переменную constexpr (или, в более общем смысле, в место, где требуется значение времени компиляции, как поле размера C). -стиль массива, или параметр значения шаблона, или static_assert() тест)

constexpr auto f = fold([](auto x, auto y, auto z) {return x+y+z;},
                        0, a, a);

Интересно, можно ли его каким-то образом упростить

Конечно.

Прежде всего: если можете, избегайте повторного изобретения weel: ваш tvecn является упрощенной версией std::array.

Предложение: используйте std::array (если можетеочевидно)

Второе: вы пометили C ++ 17, чтобы вы могли использовать сворачивание

Предложение: используйте его также для all_equal

template <auto V0, auto ... Vs>
struct all_equal : public std::bool_constant<((V0 == Vs) && ...)>
 { };

template<auto ...N_pack>
constexpr bool all_equal_v = all_equal<N_pack...>::value;

Еще вобщее: когда вам нужно определить черты пользовательского типа, которые должны предоставить число, наследуйте (если возможно) от std::integral_constant (или std::bool_constant, или std::true_type, или std::false_type: все std::integral_constant специализации). Таким образом, вы автоматически наследуете все std::integral_constant объектов.

В-третьих: почти все стандартные C ++ используют std::size_t, а не int, для размеров.

Предложение: когда вы имеете дело с размерами, используйте std::size_t, а не int,Таким образом, вы можете избежать многих неприятных неприятностей.

Четвертый: с main() вы должны вернуть только EXIT_SUCCESS (обычно ноль) или EXIT_FAILURE (обычно 1)

Предложение:избегайте таких вещей, как

return fold([](auto x, auto y, auto z) {return x+y+z;}, 0, a, a);

Пятое: никогда не стоит недооценивать силу оператора запятой.

Предложение: вообще избегать рекурсии и использовать свертывание шаблонов также для вспомогательной функции;в качестве примера

template <std::size_t ... Is, typename F, typename T, typename ... As>
constexpr auto foldHelperF (std::index_sequence<Is...>,
                            F const & f, T id, As const & ... arrs)
 { return ( ..., (id = [&](auto i){ return f(id, arrs[i]...); }(Is))); }

, который можно вызвать следующим образом из fold()

return foldHelperF(std::make_index_sequence<N_head>{}, 
                   std::forward<Function>(func),
                   id, head, tail...);

Ниже приведена полная компиляция, упрощенная, например

#include <array>
#include <utility>
#include <iostream>
#include <type_traits>

template <auto V0, auto ... Vs>
struct all_equal : public std::bool_constant<((V0 == Vs) && ...)>
 { };

template<auto ...N_pack>
constexpr bool all_equal_v = all_equal<N_pack...>::value;


template <std::size_t ... Is, typename F, typename T, typename ... As>
constexpr auto foldHelperF (std::index_sequence<Is...>,
                            F const & f, T id, As const & ... arrs)
 { return ( ..., (id = [&](auto i){ return f(id, arrs[i]...); }(Is))); }


template <typename type_identity, typename type_head, std::size_t N_head,
          typename ...type_tail, std::size_t ...N_tail,
          typename Function = void (type_identity const &,
                                    type_head const &,
                                    type_tail const & ...)>
constexpr auto fold (Function && func, type_identity const & id,
                     std::array<type_head, N_head> const & head,
                     std::array<type_tail, N_tail> const & ... tail)
 {
   static_assert( std::is_invocable_v<Function, const type_identity&,
                  const type_head&, const type_tail &...>,
                  "The function cannot be invoked with these zip arguments"
                  " (possibly wrong argument count).");

   static_assert( all_equal_v<N_head, N_tail...>,
                 "Vector sizes must match.");

   return foldHelperF(std::make_index_sequence<N_head>{}, 
                      std::forward<Function>(func),
                      id, head, tail...);
}

int main()
 {
   constexpr std::array<int, 3u> b{2, 5, 7};

   constexpr auto f = fold([](auto x, auto y, auto z) {return x+y+z;},
                           0, b, b);

   std::cout << f << std::endl;
 }
2 голосов
/ 21 октября 2019

С выражением Fold это может быть:

template <typename F, typename Init, std::size_t... Is, typename... Arrays>
constexpr auto fold_impl(F&& f, Init init, std::index_sequence<Is...>, Arrays&&... arrays)
{
    auto l = [&](Init init, std::size_t i){ return f(init, arrays[i]...); };
    return ((init = l(init, Is)), ...);
}


template <typename F, typename Init, typename Array, typename ... Arrays>
constexpr auto fold(F&& f, Init init, Array&& array, Arrays&&... arrays)
{
    static_assert(((arrays.size() == array.size()) && ...));
    return fold_impl(f, init, std::make_index_sequence<array.size()>{}, array, arrays...);
}

Демо

...