STD :: уменьшить с помощью STD :: unordered_map - PullRequest
Новая
       66

STD :: уменьшить с помощью STD :: unordered_map

2 голосов
/ 11 марта 2019

У меня есть unordered_map из vectors, и я пытаюсь использовать std::reduce, чтобы получить сумму всех значений во всех векторах на карте.Мой текущий функциональный код (который я хочу заменить) выглядит следующим образом: 

// input is std::unordered_map<std::vector<uint64_t>>
template<typename T>
uint64_t get_map_sum(T& my_map)
{
    uint64_t totalcount = 0;
    for (auto& p : my_map) 
    {
        for (const auto& q : p.second)
            totalcount += q;
    }
    return total_count;
}

Я хотел бы заменить это на std::reduce, чтобы использовать параллельное выполнение;Я думал, что это будет просто, так как мне нужно было только заменить каждый цикл вызовом std::reduce, но это, похоже, не работает.Моя попытка заключается в следующем: 

#include <numeric>
#include <execution>
#include <vector>
#include <unordered_map>
#include <cstdint>
// reduces the vectors
template <typename Iter, typename T>
T get_vector_sum(Iter begin, Iter end, T initial = 0)
{
    return std::reduce(std::execution::par_unseq, begin, end, initial, 
           [&](auto cur, auto prev) { return cur + prev; });
}

// calls get_vector_sum for all vectors and then reduces vector sums
template<typename Iter>
uint64_t get_map_sum(Iter begin, Iter end)
{
    return std::reduce(std::execution::par_unseq, begin, end, 0ULL,
            [&](auto prev, auto cur)
            {
                return get_vector_sum<std::vector<uint64_t>::iterator, 
                       uint64_t>(cur.begin(), cur.end(), prev);
                //return get_vector_sum<std::vector<uint64_t>::iterator,
                //       uint64_t>(cur.second.begin(), cur.second.end(), prev);
            });
}

С кодом выше, я получаю сообщение об ошибке, говорящее error C2039: 'begin': is not a member of 'std::pair' со ссылкой на auto cur в лямбда внутри get_map_sum.Первоначально я использовал cur как std::pair, но когда я это сделал, у меня появилась другая ошибка: error C2228: left of '.second' must have class/struct/union. 

int main()
{
    std::unordered_map<uint64_t, std::vector<uint64_t>> in({ 
        {1, std::vector<uint64_t>{1,2,3,4,5} }, 
        {2, std::vector<uint64_t>{1,2,3,4,5}}, 
        {3, std::vector<uint64_t>{1,2,3,4,5}}});

    auto x = get_map_sum(in); // output 45
    auto y = get_map_sum(in.begin(), in.end()); // error

    return 0;
}

Можно ли использовать std::reduce с картами, подобными этой, и,если да, какие изменения мне нужно сделать, чтобы это работало?

Ответы [ 2 ]

2 голосов
/ 11 марта 2019

Обратите внимание на это требование для binary_op из std::reduce:

binary FunctionObject , которое будет применяться в неуказанном порядке к результат разыменования входных итераторов , результаты других двоичных_оп и init .

Это означает, что результат вашегоЛямбда-результат и init должны быть того же типа, что и тип значения карты, т. е. std::pair<const uint64_t, std::vector<uint64_t>>.

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

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

using M = std::unordered_map<uint64_t, std::vector<uint64_t>>;
using V = M::value_type;

M in({ {1, std::vector<uint64_t>{1,2,3,4,5}}, 
       {2, std::vector<uint64_t>{1,2,3,4,5}}, 
       {3, std::vector<uint64_t>{1,2,3,4,5}} });

auto p = std::reduce(in.begin(), in.end(), V{}, 
    [](const V& a, const V& b) {
        auto ra = std::reduce(a.second.begin(), a.second.end(), 0UL,
            [](uint64_t i1, uint64_t i2){ return i1 + i2; });
        auto rb = std::reduce(b.second.begin(), b.second.end(), 0UL,
            [](uint64_t i1, uint64_t i2){ return i1 + i2; });
        return V{0, { ra + rb }};
});

Но он не компилируется с GCC из-за отсутствующей реализации std::reduce, и Кланг жалуется на отсутствие оператора назначения копирования для типа значения, который не может быть назначен для копирования из-за ключа const: https://wandbox.org/permlink/FBYAhCArtOHvwu8C.

Однако, в cppreference, требования для типа значения составляют только MoveConstructible , а не Copy / MoveAssignable .Итак, кажется, что в libc ++ существует неправильная реализация.

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

using V = std::pair<uint64_t, std::vector<uint64_t>>;

См. https://wandbox.org/permlink/lF9VuJwISYXhpBJL.

1 голос
/ 11 марта 2019

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

using M = std::unordered_map<uint64_t, std::vector<uint64_t>>;

template <typename Iter, typename T>
T par_unseq_sum(Iter begin, Iter end, T initial = 0)
{
    // std::plus is the default reducer
    return std::reduce(std::execution::par_unseq, begin, end, initial);
}

class map_vector_sum
{
public:
    map_vector_sum() : sum(0) {}
    map_vector_sum(M::const_reference elem) : sum(par_unseq_sum(elem.second)) {}

    map_vector_sum& operator+(const map_vector_sum & rhs) { sum += rhs.sum; }

    explicit operator uint64_t() { return sum; }
private:
    uint64_t sum;
}

M in({ {1, std::vector<uint64_t>{1,2,3,4,5}}, 
       {2, std::vector<uint64_t>{1,2,3,4,5}}, 
       {3, std::vector<uint64_t>{1,2,3,4,5}} });

uint64_t sum = par_unseq_sum(in.begin(), in.end(), map_vector_sum());
...