Notitie
Voor toegang tot deze pagina is autorisatie vereist. U kunt proberen u aan te melden of de directory te wijzigen.
Voor toegang tot deze pagina is autorisatie vereist. U kunt proberen de mappen te wijzigen.
Dit onderwerp laat zien hoe je een zoekalgoritme schrijft voor een basisbomenstructuur.
In het onderwerp Annulering wordt de rol van annulering in de bibliotheek parallelle patronen uitgelegd. Het gebruik van uitzonderingsafhandeling is een minder efficiënte manier om parallelle werkzaamheden te annuleren dan het gebruik van de concurrency::task_group::cancel en concurrency::structured_task_group::cancel methoden. Een scenario waarin het gebruik van uitzonderingsafhandeling om werk te annuleren toch geschikt kan zijn, is wanneer u een bibliotheek van derden aanroept die gebruikmaakt van taken of parallelle algoritmen, maar geen task_group of structured_task_group object biedt om te annuleren.
Voorbeeld: Basistype boom
In het volgende voorbeeld ziet u een basistype tree dat een gegevenselement en een lijst met onderliggende knooppunten bevat. In de volgende sectie ziet u de body van de for_all-methode, die recursief een werkfunctie uitvoert op elk kindknooppunt.
// 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;
};
Voorbeeld: Werk parallel uitvoeren
In het volgende voorbeeld ziet u de for_all methode. Er wordt gebruikgemaakt van het algoritme concurrency::parallel_for_each om parallel een werkfunctie uit te voeren op elk knooppunt van de boom.
// 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);
}
Voorbeeld: Zoek in de boom naar een waarde
In het volgende voorbeeld ziet u de search_for_value functie, waarmee wordt gezocht naar een waarde in het opgegeven tree object. Deze functie wordt doorgegeven aan de for_all methode die een werkfunctie genereert wanneer er een structuurknooppunt wordt gevonden dat de opgegeven waarde bevat.
Stel dat de tree klasse wordt geleverd door een bibliotheek van derden en dat u deze niet kunt wijzigen. In dit geval is het gebruik van uitzonderingsafhandeling gepast omdat de for_all-methode geen task_group- of structured_task_group-object aan de aanroeper geeft. Daarom kan de werkfunctie de bovenliggende taakgroep niet rechtstreeks annuleren.
Wanneer de werkfunctie die u aan een taakgroep opgeeft, een uitzondering genereert, stopt de runtime alle taken die zich in de taakgroep bevinden (inclusief onderliggende taakgroepen) en worden alle taken verwijderd die nog niet zijn gestart. De search_for_value functie gebruikt een try-catch blok om de uitzondering vast te leggen en het resultaat af te drukken naar de console.
// 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();
}
Voorbeeld: Een boom parallel opzetten en doorzoeken
In het volgende voorbeeld wordt een tree object gemaakt en parallel wordt gezocht naar verschillende waarden. De build_tree functie wordt verderop in dit onderwerp weergegeven.
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); }
);
}
In dit voorbeeld wordt het algoritme gelijktijdigheid::parallel_invoke gebruikt om parallel naar waarden te zoeken. Zie Parallelle algoritmen voor meer informatie over dit algoritme.
Voorbeeld: Afgerond voorbeeld van uitzonderingsafhandeling
In het volgende volledige voorbeeld wordt de verwerking van uitzonderingen gebruikt om te zoeken naar waarden in een basisstructuur.
// 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); }
);
}
In dit voorbeeld wordt de volgende voorbeelduitvoer geproduceerd.
Found a node with value 32614.
Found a node with value 86131.
Did not find node with value 17522.
De code compileren
Kopieer de voorbeeldcode en plak deze in een Visual Studio-project, of plak deze in een bestand met de naam task-tree-search.cpp en voer vervolgens de volgende opdracht uit in een Visual Studio-opdrachtpromptvenster.
cl.exe /EHsc-task-tree-search.cpp
Zie ook
Annulering in de PPL
afhandeling van uitzonderingen
Parallelle uitvoering van taken
Parallelle algoritmen
task_group-klasse
structured_task_group-klasse
parallel_for_each, functie