Anteckning
Åtkomst till den här sidan kräver auktorisering. Du kan prova att logga in eller ändra kataloger.
Åtkomst till den här sidan kräver auktorisering. Du kan prova att ändra kataloger.
Det här avsnittet visar hur du skriver en sökalgoritm för en grundläggande trädstruktur.
I avsnittet Annullering förklaras rollen som annullering i det parallella mönsterbiblioteket. Användning av undantagshantering är ett mindre effektivt sätt att avbryta parallellt arbete än användningen av samtidighet::task_group::avbryt och samtidighet::structured_task_group::avbryt metoder. Ett scenario där det är lämpligt att använda undantagshantering för att avbryta arbetet är när du anropar till ett bibliotek från tredje part som använder uppgifter eller parallella algoritmer men inte tillhandahåller ett task_group eller structured_task_group -objekt att avbryta.
Exempel: Grundläggande trädtyp
I följande exempel visas en grundläggande tree typ som innehåller ett dataelement och en lista över underordnade noder. I följande avsnitt visas implementationen av for_all-metoden, som rekursivt utför en arbetsfunktion på varje barnnod.
// A simple tree structure that has multiple child nodes.
template <typename T>
class tree
{
public:
explicit tree(T data)
: _data(data)
{
}
// Retrieves the data element for the node.
T get_data() const
{
return _data;
}
// Adds a child node to the tree.
void add_child(tree& child)
{
_children.push_back(child);
}
// Performs the given work function on the data element of the tree and
// on each child.
template<class Function>
void for_all(Function& action);
private:
// The data for this node.
T _data;
// The child nodes.
list<tree> _children;
};
Exempel: Utföra arbete parallellt
I följande exempel visas for_all metoden. Den använder algoritmen concurrency::parallel_for_each för att utföra en funktion på varje nod i trädet parallellt.
// Performs the given work function on the data element of the tree and
// on each child.
template<class Function>
void for_all(Function& action)
{
// Perform the action on each child.
parallel_for_each(begin(_children), end(_children), [&](tree& child) {
child.for_all(action);
});
// Perform the action on this node.
action(*this);
}
Exempel: Sök i trädet efter ett värde
I följande exempel visas funktionen search_for_value som söker efter ett värde i det angivna tree objektet. Den här funktionen skickar till for_all metoden en arbetsfunktion som genererar när den hittar en trädnod som innehåller det angivna värdet.
Anta att tree klassen tillhandahålls av ett bibliotek från tredje part och att du inte kan ändra den. I det här fallet är det lämpligt att använda undantagshantering eftersom for_all metoden inte ger anroparen ett task_group eller structured_task_group -objekt. Därför kan arbetsfunktionen inte avbryta den överordnade aktivitetsgruppen direkt.
När den arbetsfunktion som du anger för en aktivitetsgrupp utlöser ett undantag stoppar körningen alla aktiviteter som finns i aktivitetsgruppen (inklusive eventuella underordnade aktivitetsgrupper) och tar bort alla aktiviteter som ännu inte har startats. Funktionen search_for_value använder ett try-catch block för att avbilda undantaget och skriva ut resultatet till konsolen.
// Searches for a value in the provided tree object.
template <typename T>
void search_for_value(tree<T>& t, int value)
{
try
{
// Call the for_all method to search for a value. The work function
// throws an exception when it finds the value.
t.for_all([value](const tree<T>& node) {
if (node.get_data() == value)
{
throw &node;
}
});
}
catch (const tree<T>* node)
{
// A matching node was found. Print a message to the console.
wstringstream ss;
ss << L"Found a node with value " << value << L'.' << endl;
wcout << ss.str();
return;
}
// A matching node was not found. Print a message to the console.
wstringstream ss;
ss << L"Did not find node with value " << value << L'.' << endl;
wcout << ss.str();
}
Exempel: Skapa och söka i ett träd parallellt
I följande exempel skapas ett tree objekt och söker efter flera värden parallellt. Funktionen build_tree visas senare i det här avsnittet.
int wmain()
{
// Build a tree that is four levels deep with the initial level
// having three children. The value of each node is a random number.
mt19937 gen(38);
tree<int> t = build_tree<int>(4, 3, [&gen]{ return gen()%100000; });
// Search for a few values in the tree in parallel.
parallel_invoke(
[&t] { search_for_value(t, 86131); },
[&t] { search_for_value(t, 17522); },
[&t] { search_for_value(t, 32614); }
);
}
I det här exemplet används algoritmen concurrency::p arallel_invoke för att söka efter värden parallellt. Mer information om den här algoritmen finns i Parallella algoritmer.
Exempel: Kodexempel för färdig undantagshantering
I följande fullständiga exempel används undantagshantering för att söka efter värden i en grundläggande trädstruktur.
// task-tree-search.cpp
// compile with: /EHsc
#include <ppl.h>
#include <list>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <random>
using namespace concurrency;
using namespace std;
// A simple tree structure that has multiple child nodes.
template <typename T>
class tree
{
public:
explicit tree(T data)
: _data(data)
{
}
// Retrieves the data element for the node.
T get_data() const
{
return _data;
}
// Adds a child node to the tree.
void add_child(tree& child)
{
_children.push_back(child);
}
// Performs the given work function on the data element of the tree and
// on each child.
template<class Function>
void for_all(Function& action)
{
// Perform the action on each child.
parallel_for_each(begin(_children), end(_children), [&](tree& child) {
child.for_all(action);
});
// Perform the action on this node.
action(*this);
}
private:
// The data for this node.
T _data;
// The child nodes.
list<tree> _children;
};
// Builds a tree with the given depth.
// Each node of the tree is initialized with the provided generator function.
// Each level of the tree has one more child than the previous level.
template <typename T, class Generator>
tree<T> build_tree(int depth, int child_count, Generator& g)
{
// Create the tree node.
tree<T> t(g());
// Add children.
if (depth > 0)
{
for(int i = 0; i < child_count; ++i)
{
t.add_child(build_tree<T>(depth - 1, child_count + 1, g));
}
}
return t;
}
// Searches for a value in the provided tree object.
template <typename T>
void search_for_value(tree<T>& t, int value)
{
try
{
// Call the for_all method to search for a value. The work function
// throws an exception when it finds the value.
t.for_all([value](const tree<T>& node) {
if (node.get_data() == value)
{
throw &node;
}
});
}
catch (const tree<T>* node)
{
// A matching node was found. Print a message to the console.
wstringstream ss;
ss << L"Found a node with value " << value << L'.' << endl;
wcout << ss.str();
return;
}
// A matching node was not found. Print a message to the console.
wstringstream ss;
ss << L"Did not find node with value " << value << L'.' << endl;
wcout << ss.str();
}
int wmain()
{
// Build a tree that is four levels deep with the initial level
// having three children. The value of each node is a random number.
mt19937 gen(38);
tree<int> t = build_tree<int>(4, 3, [&gen]{ return gen()%100000; });
// Search for a few values in the tree in parallel.
parallel_invoke(
[&t] { search_for_value(t, 86131); },
[&t] { search_for_value(t, 17522); },
[&t] { search_for_value(t, 32614); }
);
}
Det här exemplet genererar följande exempelutdata.
Found a node with value 32614.
Found a node with value 86131.
Did not find node with value 17522.
Kompilera koden
Kopiera exempelkoden och klistra in den i ett Visual Studio-projekt, eller klistra in den i en fil med namnet task-tree-search.cpp och kör sedan följande kommando i ett Visual Studio-kommandotolkfönster.
cl.exe /EHsc task-tree-search.cpp
Se även
Annullering i PPL
undantagshantering
Uppgiftsparallellitet
Parallella algoritmer
task_group-klass
structured_task_group-klass
parallel_for_each funktion