方法: 例外処理を使用して並列ループを中断する

  • [アーティクル]

このトピックでは、基本的なツリー構造の検索アルゴリズムを記述する方法を示します。

取り消し処理に関するトピックでは、並列パターン ライブラリにおける取り消し処理の役割について説明しています。 並列処理を取り消すために例外処理を使用する方法は、concurrency::task_group::cancel メソッドおよび concurrency::structured_task_group::cancel メソッドを使用する方法ほど効率的ではありません。 ただし、例外処理を使用した処理の取り消しが適しているシナリオの 1 つとして、タスクまたは並列アルゴリズムは使用しても、取り消し処理を行うための task_group または structured_task_group オブジェクトが用意されていないサードパーティのライブラリを呼び出す場合があります。

例: 基本的なツリー型

次の例は、データ要素と子ノードのリストを含む基本的な 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::p arallel_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); }
   );
}

この例では、次のサンプル出力が生成されます。

Found a node with value 32614.
Found a node with value 86131.
Did not find node with value 17522.

コードのコンパイル

コード例をコピーし、Visual Studio プロジェクトに貼り付けるか、task-tree-search.cpp という名前のファイルに貼り付けてから、Visual Studio のコマンド プロンプト ウィンドウで次のコマンドを実行します。

cl.exe /EHsc task-tree-search.cpp

関連項目

PPL における取り消し処理
例外処理
タスクの並列処理
並列アルゴリズム
task_group クラス
structured_task_group クラス
parallel_for_each関数