OpenMP плюс сокращение на unordered_map - PullRequest
Новая
       9

OpenMP плюс сокращение на unordered_map

0 голосов
/ 18 октября 2018

Я хотел бы распараллелить цикл for, в котором обновляются значения unordered_map: 

unordered_map<string,double> umap {{"foo", 0}, {"bar", 0}};

#pragma omp parallel for reduction(my_reduction:umap)
for (int i = 0; i < 100; ++i)
{
    // some_string(i) would return either "foo" or "bar"
    umap[some_string(i)] += some_double(i);
}

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

В этом ответе объявленное пользователем сокращение определено для случая вектора.Может ли объявленное пользователем сокращение быть определенным аналогичным образом в случае unordered_map?

1 Ответ

0 голосов
/ 18 октября 2018

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

//GCC version, but the documentation suggests the same thing. 
*__result = __binary_op(*__first1, *__first2);

Поскольку карты хранят типы std::pair<const T1, T2> (т.е. первое всегда должно быть константным, вы не можете изменитьключ), это может привести к ошибке, потому что operator= для этого случая удаляется.

По этой причине мы заканчиваем тем, что пишем все это сами (ответ, который следует, можно сделать чище,Я просто жестко запрограммировал ваш тип ...).

Мы могли бы просто начать с примеров std::transform ( посмотреть на примерную реализацию 2 ) и изменить проблемную часть, но @Zulan поднимает хорошую точку в комментариях, которые одновременно проходят неупорядоченныйКарты могут не быть хорошей идеей (поскольку они, по определению, не упорядочены).Хотя может иметь смысл, что конструктор копирования сохраняет порядок, кажется, что это не гарантируется стандартом (по крайней мере, я нигде не мог его найти), так как такой подход, который использует std::transform, становится довольно бесполезным.

Мы можем решить эту проблему с немного другим сокращением.

#include <unordered_map>
#include <string>
#include <iostream>
#include <utility>

void reduce_umaps(\
    std::unordered_map<std::string, double>& output, \
    std::unordered_map<std::string, double>& input)
{
    for (auto& X : input) {
      output.at(X.first) += X.second; //Will throw if X.first doesn't exist in output. 
    }
}

#pragma omp declare reduction(umap_reduction : \
    std::unordered_map<std::string, double> : \
    reduce_umaps(omp_out, omp_in)) \
    initializer(omp_priv(omp_orig))

using namespace std;

unordered_map<string, double> umap {{"foo", 0}, {"bar", 0}};

string some_string(int in) {
    if (in % 2 == 0) return "foo";
    else return "bar";
}

inline double some_double(int in) {
    return static_cast<double>(in);
}

int main(void) {
#pragma omp parallel for reduction(umap_reduction:umap)
for (int i = 0; i < 100; ++i) {
        umap.at(some_string(i)) += some_double(i);
    }
    std::cerr << umap["foo"] << " " << umap["bar"] << "\n";
    return 0;
}

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

В качестве последнего примечания я заменил umap[some_string(i)] на umap.at(some_string(i)), чтобы избежать случайного добавления элементов, очень похожих на то, что было предложено в комментариях, но find не самая практичная функция для этой цели.

...