質問編集履歴

2 読みやすさを考慮

tkow

tkow score 1177

2017/01/25 13:02  投稿

Dictionary型のオブジェクトのKEY VALUEペアのロック
お世話になっております。
C#で既存プログラムの実装の高速化をしたいと思っています。
以下のような木構造があり、それぞれのノードにはDictionaryでenum型に応じたkeyとdouble型のスコア値をvalueとして格納しています。
それぞれのエッジのスコアをrootから順に合計し、それぞれの枝について一番深いノードのスコア(図の赤色のスコア)を合計して出したいと思っています。
![イメージ説明](c259e101c025594f43b9d5e66438e06b.png)
実際はもっと複雑なアルゴリズムでノード間のスコアを決めるためにノードごとに共有される変数が必要になり、単純にそれぞれのスコアタイプごとにツリー構造をインスタンス化して並列化するという解決策は難しいということを前提としてください。
エッジのスコアとrootのスコアの初期値は既知でノードごとのスコアの累積和が未知の時に木構造の最も深いノードのスコアの累積和を求めるプログラムを書くと以下のようになりました。
一度通ったノードであれば再計算する必要がないのでそれぞれのノードにそのノード時点でのスコアの累積和を(Ditcionary<int,double> score)にキャッシュさせ、一度計算した経路については親の累積スコアを使いまわすことで計算を効率化するようにしています。
```C#
class Program{
 static double ROOT_SCORE=0.1;
}
class Node{
 
   public Ditcionary<int,double> score;
   private Dictionary<int,double> _edgeScore;
   //constructor 省略
   double edgeScore(int stype){
       return _edgeScore[stype];
   }
   public double calcScore(int stype,bool recalc=false)
   {
       if (score.ContainsKey(type)&&!recalc) {
           return score[stype];
       }
       if (parent != null)
       {
         score[stype] = edgeScore(stype)
           score[stype] += parent.calcScore(score,recalc);
           return score[stype];
       }
       else
       {
           return ROOT_SCORE;
       }
   }
}
//末端のNodeは取得できる
//List<Node> deepestNodes = new List<Node>{deepNode1,deepNode2};
//deepestNodes.Select(node=>types.Select(type=>node.calcScore(type)));
```
このとき、この処理をtypeごと,末端nodeごとに並列化したいのですがこれらの並列化にはDictionary scoreの排他制御。をしなければいけないと思うのですが。Dictionaryごとロックする方法は出てくるのですが、Dictionaryインスタンスすべてをロックするのは効率が悪いのでDictionaryのkeyの参照先のオブジェクトの書き込みの排他制御を行いたいと思っています。(つまり、要約すると**stypeごとの実行はほかのstypeと競合しないので並列化,stypeの中ではノードの分岐点までは並列化分岐点では排他制御がしたい**ということです。)このようなことは可能なのでしょうか?よろしくお願いいたします。
このとき、この処理をtypeごと,末端nodeごとに並列化したいのですがこれらの並列化にはDictionary scoreの排他制御。をしなければいけないと思うのですが。Dictionaryごとロックする方法は出てくるのですが、Dictionaryインスタンスすべてをロックするのは効率が悪いのでDictionaryのkeyの参照先のオブジェクトの書き込みの排他制御を行いたいと思っています。(つまり、要約すると**stypeごとの実行はほかのstypeと競合しないので並列化,stypeの中ではノードの分岐点までは並列化,分岐点では排他制御がしたい**ということです。)このようなことは可能なのでしょうか?よろしくお願いいたします。
必要があれば、子から親までのパスはノードを作るときに作成できます。
  • C#

    9028 questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

1 型指定ミス

tkow

tkow score 1177

2017/01/25 12:56  投稿

Dictionary型のオブジェクトのKEY VALUEペアのロック
お世話になっております。
C#で既存プログラムの実装の高速化をしたいと思っています。
以下のような木構造があり、それぞれのノードにはDictionaryでenum型に応じたkeyとint型のスコア値をvalueとして格納しています。
以下のような木構造があり、それぞれのノードにはDictionaryでenum型に応じたkeyとdouble型のスコア値をvalueとして格納しています。
それぞれのエッジのスコアをrootから順に合計し、それぞれの枝について一番深いノードのスコア(図の赤色のスコア)を合計して出したいと思っています。
![イメージ説明](c259e101c025594f43b9d5e66438e06b.png)
実際はもっと複雑なアルゴリズムでノード間のスコアを決めるためにノードごとに共有される変数が必要になり、単純にそれぞれのスコアタイプごとにツリー構造をインスタンス化して並列化するという解決策は難しいということを前提としてください。
エッジのスコアとrootのスコアの初期値は既知でノードごとのスコアの累積和が未知の時に木構造の最も深いノードのスコアの累積和を求めるプログラムを書くと以下のようになりました。
一度通ったノードであれば再計算する必要がないのでそれぞれのノードにそのノード時点でのスコアの累積和を(Ditcionary<int,double> score)にキャッシュさせ、一度計算した経路については親の累積スコアを使いまわすことで計算を効率化するようにしています。
```C#
class Program{
 static double ROOT_SCORE=0.1;
}
class Node{
 
   public Ditcionary<int,double> score;
   private Dictionary<int,double> _edgeScore;
   //constructor 省略
   double edgeScore(int stype){
       return _edgeScore[stype];
   }
   public double calcScore(int stype,bool recalc=false)
   {
       if (score.ContainsKey(type)&&!recalc) {
           return score[stype];
       }
       if (parent != null)
       {
         score[stype] = edgeScore(stype)
           score[stype] += parent.calcScore(score,recalc);
           return score[stype];
       }
       else
       {
           return ROOT_SCORE;
       }
   }
}
//末端のNodeは取得できる
//List<Node> deepestNodes = new List<Node>{deepNode1,deepNode2};
//deepestNodes.Select(node=>types.Select(type=>node.calcScore(type)));
```
このとき、この処理をtypeごと,末端nodeごとに並列化したいのですがこれらの並列化にはDictionary scoreの排他制御。をしなければいけないと思うのですが。Dictionaryごとロックする方法は出てくるのですが、Dictionaryインスタンスすべてをロックするのは効率が悪いのでDictionaryのkeyの参照先のオブジェクトの書き込みの排他制御を行いたいと思っています。(つまり、要約すると**stypeごとの実行はほかのstypeと競合しないので並列化,stypeの中ではノードの分岐点までは並列化分岐点では排他制御がしたい**ということです。)このようなことは可能なのでしょうか?よろしくお願いいたします。
必要があれば、子から親までのパスはノードを作るときに作成できます。
  • C#

    9028 questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る