Практическое руководство. Параллельное выполнение операций сопоставления и сокращения числа элементов

В этом примере показано, как использовать алгоритмы параллелизма::p arallel_transform и concurrency::p arallel_reduce и класс concurrency::concurrent_unordered_map для подсчета вхождения слов в файлах.

Операция сопоставления применяет функцию к каждому значению последовательности. Операция уменьшения объединяет элементы последовательности в одно значение. Вы можете использовать стандартную библиотеку C++ std::transform и std::аккумулировать функции для выполнения операций сопоставления и уменьшения. Однако для повышения производительности при многих проблемах можно использовать алгоритм parallel_transform для параллельного выполнения операции сопоставления и алгоритм parallel_reduce для параллельного выполнения операции редукции. В некоторых случаях можно использовать concurrent_unordered_map для выполнения сопоставления и операции редукции в одной операции.

Пример

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

// parallel-map-reduce.cpp
// compile with: /EHsc
#include <ppl.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <unordered_map>
#include <windows.h>

using namespace concurrency;
using namespace std;

class MapFunc 
{ 
public:
    unordered_map<wstring, size_t> operator()(vector<wstring>& elements) const 
    { 
        unordered_map<wstring, size_t> m;
        for_each(begin(elements), end(elements), [&m](const wstring& elem)
        { 
            m[elem]++;
        });
        return m; 
    }
}; 

struct ReduceFunc : binary_function<unordered_map<wstring, size_t>, 
                    unordered_map<wstring, size_t>, unordered_map<wstring, size_t>>
{
    unordered_map<wstring, size_t> operator() (
        const unordered_map<wstring, size_t>& x, 
        const unordered_map<wstring, size_t>& y) const
    {
        unordered_map<wstring, size_t> ret(x);
        for_each(begin(y), end(y), [&ret](const pair<wstring, size_t>& pr) {
            auto key = pr.first;
            auto val = pr.second;
            ret[key] += val;
        });
        return ret; 
    }
}; 

int wmain()
{ 
    // File 1 
    vector<wstring> v1 {
      L"word1", // 1
      L"word1", // 1
      L"word2",
      L"word3",
      L"word4"
    };

    // File 2 
    vector<wstring> v2 {
      L"word5",
      L"word6",
      L"word7",
      L"word8",
      L"word1" // 3
    };

    vector<vector<wstring>> v { v1, v2 };

    vector<unordered_map<wstring, size_t>> map(v.size()); 

    // The Map operation
    parallel_transform(begin(v), end(v), begin(map), MapFunc()); 

    // The Reduce operation 
    unordered_map<wstring, size_t> result = parallel_reduce(
        begin(map), end(map), unordered_map<wstring, size_t>(), ReduceFunc());

    wcout << L"\"word1\" occurs " << result.at(L"word1") << L" times. " << endl;
} 
/* Output:
   "word1" occurs 3 times.
*/

Компиляция кода

Чтобы скомпилировать код, скопируйте его и вставьте его в проект Visual Studio или вставьте его в файл с именем parallel-map-reduce.cpp , а затем выполните следующую команду в окне командной строки Visual Studio.

cl.exe /EHsc parallel-map-reduce.cpp

Отказоустойчивость

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

// File 1 
vector<wstring> v1 {
  L"word1", // 1
  L"word1", // 2
  L"word2",
  L"word3",
  L"word4",
};

// File 2 
vector<wstring> v2 {
  L"word5",
  L"word6",
  L"word7",
  L"word8",
  L"word1", // 3
}; 

vector<vector<wstring>> v { v1, v2 };

concurrent_unordered_map<wstring, size_t> result;
for_each(begin(v), end(v), [&result](const vector<wstring>& words) {
    parallel_for_each(begin(words), end(words), [&result](const wstring& word) {
        InterlockedIncrement(&result[word]);
    });
});
            
wcout << L"\"word1\" occurs " << result.at(L"word1") << L" times. " << endl;

/* Output:
   "word1" occurs 3 times.
*/

Как правило, вы параллелизуете только внешний или внутренний цикл. Параллелизуйте внутренний цикл при наличии относительно небольшого числа файлов, когда каждый файл содержит много слов. Параллелизуйте внешний цикл при наличии довольно большого числа файлов, когда каждый файл содержит мало слов.

См. также

Параллельные алгоритмы
Функция parallel_transform
Функция parallel_reduce
Класс concurrent_unordered_map