方法: 例外処理を使用して並列ループを中断する
ここでは、基本ツリー構造の検索アルゴリズムを記述する方法について説明します。
「PPL における取り消し処理」では、並列パターン ライブラリでのキャンセル処理の役割について説明しています。 例外処理を使用して並列処理を取り消す concurrency::task_group::cancel と concurrency::structured_task_group::cancel のメソッドを使用する方法よりも効率的です。 ただし、タスクまたは並列アルゴリズムを使用しているサードパーティのライブラリを呼び出すようなシナリオにおいて、そのライブラリが取り消し用の task_group または structured_task_group オブジェクトを提供しない場合は、例外処理を使用して処理を取り消す方法が適しています。
使用例
次の例は、1 つのデータ要素と子ノードのリストを含む基本 tree 型を示します。 次のセクションに、それぞれの子ノードに対して反復的に処理関数を実行する for_all メソッドの本体を示します。
// 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;
};
for_all メソッドの例を次に示します。 これは、ツリーの各ノードに対して処理関数を並列に実行するために concurrency::parallel_for_each アルゴリズムを使用します。
// 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);
}
次の例は search_for_value 関数で、提供された tree オブジェクト内で値を検索します。 この関数は、提供された値を含むツリー ノードを検出したときに例外をスローする処理関数を for_all メソッドに渡します。
サードパーティのライブラリによって、変更できない tree クラスが提供されるものとします。 この場合、for_all メソッドは task_group オブジェクトまたは structured_task_group オブジェクトを呼び出し元に提供しないため、例外処理の使用が適切です。 したがって、処理関数は、親タスク グループを直接取り消すことはできません。
タスク グループに指定した処理関数が例外をスローすると、ランタイムは、(子タスク グループを含む) タスク グループ内のすべてのタスクを中止すると共に、開始されていないすべてのタスクを破棄します。 search_for_value 関数は、try-catch ブロックを使用して例外をキャプチャし、結果をコンソールに印刷します。
// 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();
}
次の例では、tree オブジェクトを作成し、このオブジェクト内で複数の値を同時に検索します。 build_tree 関数については、このトピックの後で説明します。
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); }
);
}
この例では、値を同時に検索に concurrency::parallel_invoke アルゴリズムを使用します。 このアルゴリズムの詳細については、「並列アルゴリズム」を参照してください。
次の完全な例では、例外処理を使用して、基本ツリー構造内の値を検索します。
// 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); }
);
}
この例では、次のサンプル出力が生成されます。
コードのコンパイル
プログラム例をコピーし、Visual Studio のプロジェクトに貼り付けるか、ツリー search.cpp タスク という名前で、Visual Studio のコマンド プロンプト ウィンドウで次のコマンドを実行してファイルに貼り付けます。
cl.exe /EHsc task-tree-search.cpp