Handleiding voor: Map- en Reduce-bewerkingen parallel uitvoeren

In dit voorbeeld ziet u hoe u de algoritmen concurrency::parallel_transform en concurrency::parallel_reduce en de klasse concurrency::concurrent_unordered_map gebruikt om het aantal voorkomens van woorden in bestanden te tellen.

Met een map-bewerking wordt een functie toegepast op elke waarde in een sequentie. Een reductiebewerking combineert de elementen van een reeks in één waarde. U kunt de C++ Standaardbibliotheek std::transform en std::accumulate functies gebruiken om transformatie- en reductiebewerkingen uit te voeren. Als u echter de prestaties voor veel problemen wilt verbeteren, kunt u het parallel_transform algoritme gebruiken om de toewijzingsbewerking parallel uit te voeren en het parallel_reduce algoritme om de reductiebewerking parallel uit te voeren. In sommige gevallen kunt u met concurrent_unordered_map de map en reduce in één bewerking uitvoeren.

Voorbeeld

In het volgende voorbeeld worden de voorkomens van woorden in bestanden geteld. Hierbij wordt std::vector gebruikt om de inhoud van twee bestanden weer te geven. De kaartbewerking berekent de exemplaren van elk woord in elke vector. De reductiebewerking verzamelt het aantal woorden over beide vectoren.

// 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.
*/

De code compileren

Als u de code wilt compileren, kopieert u deze en plakt u deze in een Visual Studio-project of plakt u deze in een bestand met de naam parallel-map-reduce.cpp en voert u vervolgens de volgende opdracht uit in een Visual Studio-opdrachtpromptvenster.

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

Robuuste programmering

In dit voorbeeld kunt u de concurrent_unordered_map klasse ( die is gedefinieerd in concurrent_unordered_map.h) gebruiken om de kaart uit te voeren en in één bewerking te verminderen.

// 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.
*/

Normaal gesproken parallelliseert u alleen de buitenste of de binnenste lus. Parallelliseer de binnenste lus als u relatief weinig bestanden hebt en elk bestand veel woorden bevat. Parallelliseer de buitenste lus als u relatief veel bestanden hebt en elk bestand enkele woorden bevat.

Zie ook

Parallelle algoritmen
parallel_transform Functie
parallel_reduce functie
concurrent_unordered_map-klasse