Dela via


Gör så här: Att utföra map- och reduce-åtgärder parallellt

Det här exemplet visar hur du använder algoritmerna concurrency::parallel_transform och concurrency::parallel_reduce och concurrency::concurrent_unordered_map för att räkna förekomster av ord i filer.

En kartåtgärd tillämpar en funktion på varje värde i en sekvens. En reduce-åtgärd kombinerar elementen i en sekvens till ett värde. Du kan använda C++-standardbiblioteket funktionerna std::transform och std::accumulate för att utföra map- och reduce-operationer. Men för att förbättra prestandan för många problem kan du använda algoritmen parallel_transform för att utföra kartåtgärden parallellt och algoritmen parallel_reduce för att utföra reduce-åtgärden parallellt. I vissa fall kan du använda concurrent_unordered_map för att utföra kartan och minska i en åtgärd.

Exempel

I följande exempel räknas förekomster av ord i filer. Den använder std::vector för att representera innehållet i två filer. Kartåtgärden beräknar förekomsterna av varje ord i varje vektor. Reduce-åtgärden ackumulerar antalet ord i båda vektorerna.

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

Kompilera koden

Om du vill kompilera koden kopierar du den och klistrar sedan in den i ett Visual Studio-projekt eller klistrar in den i en fil med namnet parallel-map-reduce.cpp och kör sedan följande kommando i ett Visual Studio-kommandotolkfönster.

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

Robust Programmering

I det här exemplet kan du använda concurrent_unordered_map-klassen, som definieras i concurrent_unordered_map.h, för att utföra map och reduce i en och samma operation.

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

Vanligtvis parallelliserar du bara den yttre eller den inre slingan. Parallellisera den inre loopen om du har relativt få filer och varje fil innehåller många ord. Parallellisera den yttre loopen om du har relativt många filer och varje fil innehåller få ord.

Se även

Parallella algoritmer
parallel_transform funktion
parallel_reduce funktion
Concurrent_unordered_map-Klass