tkow score 1177
2017/01/25 13:02 投稿
| Dictionary型のオブジェクトのKEY VALUEペアのロック |
| お世話になっております。 |
| C#で既存プログラムの実装の高速化をしたいと思っています。 |
| 以下のような木構造があり、それぞれのノードにはDictionaryでenum型に応じたkeyとdouble型のスコア値をvalueとして格納しています。 |
| それぞれのエッジのスコアをrootから順に合計し、それぞれの枝について一番深いノードのスコア（図の赤色のスコア）を合計して出したいと思っています。 |
|  |
| 実際はもっと複雑なアルゴリズムでノード間のスコアを決めるためにノードごとに共有される変数が必要になり、単純にそれぞれのスコアタイプごとにツリー構造をインスタンス化して並列化するという解決策は難しいということを前提としてください。 |
| エッジのスコアと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の中ではノードの分岐点までは並列化，分岐点では排他制御がしたい**ということです。）このようなことは可能なのでしょうか？よろしくお願いいたします。 |
| 必要があれば、子から親までのパスはノードを作るときに作成できます。 |
tkow score 1177
2017/01/25 12:56 投稿
| Dictionary型のオブジェクトのKEY VALUEペアのロック |
| お世話になっております。 |
| C#で既存プログラムの実装の高速化をしたいと思っています。 |
| 以下のような木構造があり、それぞれのノードにはDictionaryでenum型に応じたkeyとint型のスコア値をvalueとして格納しています。 |
| 以下のような木構造があり、それぞれのノードにはDictionaryでenum型に応じたkeyとdouble型のスコア値をvalueとして格納しています。 |
| それぞれのエッジのスコアをrootから順に合計し、それぞれの枝について一番深いノードのスコア（図の赤色のスコア）を合計して出したいと思っています。 |
|  |
| 実際はもっと複雑なアルゴリズムでノード間のスコアを決めるためにノードごとに共有される変数が必要になり、単純にそれぞれのスコアタイプごとにツリー構造をインスタンス化して並列化するという解決策は難しいということを前提としてください。 |
| エッジのスコアと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の中ではノードの分岐点までは並列化分岐点では排他制御がしたい**ということです。）このようなことは可能なのでしょうか？よろしくお願いいたします。 |
| 必要があれば、子から親までのパスはノードを作るときに作成できます。 |
