Comment : exécuter des opérations de mappage et de réduction en parallèle

Article
03/04/2013

Cet exemple montre comment utiliser la concurrency::parallel_transform et concurrency::parallel_reduce les algorithmes et les concurrency::concurrent_unordered_map pour compter les occurrences des mots dans les fichiers de classe.

A carte opération s'applique à une fonction pour chaque valeur dans une séquence.A réduire opération combine les éléments d'une séquence dans une seule valeur.Vous pouvez utiliser la bibliothèque STL (Standard Template Library) std::transform std::accumulate classes pour effectuer le mappage et de réduire les opérations.Toutefois, pour améliorer les performances de nombreux problèmes, vous pouvez utiliser le parallel_transform algorithme pour effectuer l'opération de mappage en parallèle et la parallel_reduce algorithme pour effectuer l'opération de réduction en parallèle.Dans certains cas, vous pouvez utiliser concurrent_unordered_map pour effectuer le mappage et le réduire en une seule opération.

Exemple

L'exemple suivant compte les occurrences des mots dans des fichiers.Il utilise std::vector pour représenter le contenu de deux fichiers.L'opération map calcule les occurrences de chaque mot dans chaque vecteur.L'opération de réduction accumule le décompte de mots entre les deux vecteurs.

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

Compilation du code

Pour compiler le code, copiez-le et collez-le dans un projet Visual Studio ou le coller dans un fichier nommé parallèle-map-reduce.cpp , puis exécutez la commande suivante dans une fenêtre d'invite de commande Visual Studio.

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

Programmation fiable

Dans cet exemple, vous pouvez utiliser le concurrent_unordered_map classe — qui est défini dans concurrent_unordered_map.h—to effectuer le mappage et réduire en une seule opération.

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

En règle générale, vous paralléliser la boucle interne ou l'extérieur.Paralléliser la boucle interne si vous avez des fichiers relativement peu et chaque fichier contient le nombre de mots.Paralléliser la boucle externe si vous avez relativement beaucoup de fichiers et de chaque fichier contient quelques mots.

Voir aussi

Référence

parallel_transform, fonction

parallel_reduce, fonction

concurrent_unordered_map, classe

Concepts

Algorithmes parallèles

Share via