Jegyzet
Az oldalhoz való hozzáférés engedélyezést igényel. Próbálhatod be jelentkezni vagy könyvtárat váltani.
Az oldalhoz való hozzáférés engedélyezést igényel. Megpróbálhatod a könyvtár váltását.
Ez a témakör bemutatja, hogyan írhat keresési algoritmust egy alapszintű faszerkezethez.
A Lemondás témakör a lemondás szerepét ismerteti a párhuzamos minták tárában. A kivételkezelés használata kevésbé hatékony módszer a párhuzamos munka megszakítására, mint az egyidejűség::task_group::mégse és egyidejűség::structured_task_group::mégse metódusok használata. Azonban van egy olyan forgatókönyv, amikor a kivételkezelés használata megfelelő a munka megszakításához: ha olyan külső könyvtárba hív be, amely feladatokat vagy párhuzamos algoritmusokat használ, de nem ad meg egy task_group vagy structured_task_group objektumot a megszakításhoz.
Példa: Egyszerű fatípus
Az alábbi példa egy adatelemet és a gyermekcsomópontok listáját tartalmazó alaptípust tree mutat be. Az alábbi szakasz a for_all metódus törzsét mutatja be, amely rekurzív módon végrehajt egy munkafüggvényt az egyes gyerekcsomópontokon.
// 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;
};
Példa: Párhuzamos munkavégzés
Az alábbi példa a metódust for_all mutatja be. Az concurrency::parallel_for_each algoritmust használja, hogy párhuzamosan hajtson végre egy munkafüggvényt a fa minden csomópontján.
// 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);
}
Példa: Keress meg egy értéket a fán
Az alábbi példa a függvényt search_for_value mutatja be, amely egy értéket keres a megadott tree objektumban. Ez a függvény egy olyan munkafüggvényt ad át a for_all metódusnak, amely hibát dob, amikor egy megadott értéket tartalmazó facsomópontot talál.
Tegyük fel, hogy az tree osztályt egy harmadik féltől származó kódtár biztosítja, és nem módosíthatja. Ebben az esetben a kivételkezelés használata azért megfelelő, mert a for_all metódus nem biztosít task_group vagy structured_task_group objektumot a hívónak. Ezért a munkafüggvény nem képes közvetlenül megszakítani a szülő feladatcsoportját.
Amikor a feladatcsoportnak megadott munkafüggvény kivételt dob, a futtatási környezet leállítja a feladatcsoportban lévő összes feladatot (beleértve a gyerekfeladat-csoportokat is), és elveti azokat a feladatokat, amelyek még nem kezdődtek el. A search_for_value függvény egy try-catch blokkot használ a kivétel kezelésére és az eredmény konzolon történő megjelenítésére.
// 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();
}
Példa: Fa létrehozása és keresése párhuzamosan
Az alábbi példa létrehoz egy tree objektumot, és több értékre keres rá párhuzamosan. A build_tree függvény a jelen témakör későbbi részében jelenik meg.
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); }
);
}
Ez a példa a párhuzamosság::parallel_invoke algoritmust használja az értékek párhuzamos kereséséhez. Az algoritmusról további információt a Párhuzamos algoritmusok című témakörben talál.
Példa: Befejeződött a kivételkezelési kódminta
Az alábbi teljes példa kivételkezeléssel keres értékeket egy alapszintű faszerkezetben.
// 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); }
);
}
Ez a példa a következő mintakimenetet hozza létre.
Found a node with value 32614.
Found a node with value 86131.
Did not find node with value 17522.
A kód összeállítása
Másolja ki a példakódot, és illessze be egy Visual Studio-projektbe, vagy illessze be egy elnevezett task-tree-search.cpp fájlba, majd futtassa a következő parancsot egy Visual Studio parancssori ablakban.
cl.exe /EHsc task-tree-search.cpp
Lásd még
Lemondás a PPL-ben
Kivételkezelés
Feladat-párhuzamosság
Párhuzamos algoritmusok
task_group osztály
structured_task_group osztály
parallel_for_each függvény