Gewusst wie: Paralleles Ausführen von Zuordnungs- und Reduzierungsoperationen

Artikel
06/09/2015

Dieses Beispiel zeigt, wie die concurrency::parallel_transform und concurrency::parallel_reduce Algorithmen und die concurrency::concurrent_unordered_map-Klasse verwendet, um die Vorkommen von Wörtern in Dateien zu zählen.

Ein Reservierungsoperation wendet eine Funktion an einzelnen Werten in einer Sequenz. Ein reduzierens vorgang kombiniert die Elemente einer Sequenz in einen Wert. Sie können die Klassen Standardvorlagenbibliotheks (stl) verwenden std::transform std::accumulate, die Zuordnung ausführt und Vorgänge zu reduzieren. Um jedoch die Leistung für viele Probleme zu verbessern, können Sie den parallel_transform - Algorithmus verwenden, um die Reservierungsoperation und den parallel_reduce Algorithmus parallel auszuführen, um den reduzierensvorgang parallel auszuführen. In einigen Fällen können Sie concurrent_unordered_map verwenden, um die Belegung und das verringerte in einem Vorgang auszuführen.

Beispiel

Im folgenden Beispiel wird die Vorkommen von Wörtern in Dateien. Es verwendet std::vector, um den Inhalt zweier Dateien darstellen. Der Reservierungsoperation berechnet die Vorkommen eines Worts in jedem Vektor. Der reduzierensvorgang akkumuliert die Wortanzahlen zu beiden Vektoren.

// 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;
    v1.push_back(L"word1"); //1 
    v1.push_back(L"word1"); //2 
    v1.push_back(L"word2"); 
    v1.push_back(L"word3"); 
    v1.push_back(L"word4"); 

    // File 2 
    vector<wstring> v2; 
    v2.push_back(L"word5"); 
    v2.push_back(L"word6"); 
    v2.push_back(L"word7"); 
    v2.push_back(L"word8"); 
    v2.push_back(L"word1"); //3 

    vector<vector<wstring>> v;
    v.push_back(v1);
    v.push_back(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.
*/

Kompilieren des Codes

Zum Kompilieren kopieren Sie den Code, und in einem Visual Studio-Projekt dann, oder fügen Sie ihn in eine Datei mit dem Namen parallel-map-reduce.cpp ein, und dann folgenden Befehl in einem Visual Studio-Eingabeaufforderung ausgeführt.

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

Robuste Programmierung

In diesem Beispiel können Sie concurrent_unordered_map verwenden, Klasse-das in concurrent_unordered_map.h-to ausführen die Zuordnung definiert und reduzieren in einem Vorgang.

// File 1 
vector<wstring> v1;
v1.push_back(L"word1"); //1 
v1.push_back(L"word1"); //2 
v1.push_back(L"word2"); 
v1.push_back(L"word3"); 
v1.push_back(L"word4"); 

// File 2 
vector<wstring> v2; 
v2.push_back(L"word5"); 
v2.push_back(L"word6"); 
v2.push_back(L"word7"); 
v2.push_back(L"word8"); 
v2.push_back(L"word1"); //3 

vector<vector<wstring>> v;
v.push_back(v1);
v.push_back(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.
*/

Normalerweise parallelisieren Sie nur das äußere oder die innere Schleife. Parallelisieren Sie die innere Schleife, wenn Sie relativ wenige Dateien verfügen und jede Datei viele Wörter enthält. Parallelisieren Sie die äußere Schleife, wenn Sie relativ viele Dateien verfügen und jede Datei wenige Wörter enthält.

Siehe auch

Referenz

parallel_transform-Funktion

parallel_reduce-Funktion

concurrent_unordered_map-Klasse

Konzepte

Parallele Algorithmen

Freigeben über