MM 90

コルン＠KaggleSanta2015 @colun_0eitm7gt

こうすることで、デッドロックが成立するためには700を超えるスレッドが必要になる。 現在40程度のスレッド数なのでへっちゃら、というわけ。

コルン＠KaggleSanta2015 @colun_0eitm7gt

ああ、違うか。1500程度スレッドが必要になる。今40だからへっちゃら、が正しそう。

コルン＠KaggleSanta2015 @colun_0eitm7gt

環状の隣接を考えることで、10飛ばしにしてもデッドロックの万が一の可能性を発生させるためには150程度のスレッドが必要。

コルン＠KaggleSanta2015 @colun_0eitm7gt

逆に言えば、理論上は、40のスレッドを使っているのだから、35飛ばし付近が限界。それを超えると諸々無理な状態になる。まぁ実際には10飛ばしぐらいできれば十分。もしかしたら5飛ばしまででもいいのかもしれない。

コルン＠KaggleSanta2015 @colun_0eitm7gt

マルチスレッド問題はとりあえず、lockじゃなくてtry_lockを使うことにすれば解決なのかなと思う。というのも、nextに限らずロックしたい理由が発生した。

コルン＠KaggleSanta2015 @colun_0eitm7gt

偏りまくって、try_lockが全て失敗するというパターンは存在するのだけれども、それはとある実行に対してであって、それ以外のいずれかは必ず偏りの外側に存在して、さらに外側には必ずlockされてないやつが広がっているので、絶対にデッドロックには陥らない、と。

コルン＠KaggleSanta2015 @colun_0eitm7gt

詰める際にロックとアンロック繰り返しながら詰めていく処理が現在存在するのだけれども、これはtry_lockじゃなくてlockでの実装にならざるをえない。 これによってロック待ちの先もロック待ち、、、という状態が発生しうるけれども、その先頭は必ず詰める以外の処理をしている。

コルン＠KaggleSanta2015 @colun_0eitm7gt

その詰める以外の処理をしているノードは、next方向へのlockまたは両方向へのtry_lockしかしない。 lockの場合は、やはりその先に先頭が存在している。確率的に必ずnext方向に収束することになるので、デッドロックは起こらないことが証明できる。

コルン＠KaggleSanta2015 @colun_0eitm7gt

ok

コルン＠KaggleSanta2015 @colun_0eitm7gt

横の配達列をどう取ってくるんだっていう問題があって、そのために詰める操作が存在していたけれども、これ実は要らないんじゃね？　っていう感じになりつつある。。。 とある配達列の要素のいずれかの近傍は、隣の配達列である可能性が高い。

コルン＠KaggleSanta2015 @colun_0eitm7gt

要素から近傍を引く、近傍から配達列を引く。この時に、索引を１つ使うことになるけれども、詰める処理を行うと、詰める時に索引も更新しなきゃいけない。 ところが、この方法を使うことで、要素は詰まってなくて良くなった。 解決。

agw @masashinakata

@hotpepsi SRMと同じノリでマラソンページがあると嬉しいっす!

コルン @colun

@nico_shindannin いつもお世話になっております。 shindannin.hatenadiary.com/entry/20121224… この記事の最後の「1変数ごとに焼きなまし」の項に関してですが、独立性の高い要素にあらかじめ分離可能な場合でも、正しく焼きなませているなら、結果は同じな気がします。

コルン @colun

@nico_shindannin 焼き鈍し途中の最良値を別途記録しておく場合は多少良くなりますが、最後まで十分に焼きなませるのでしたら、最良値は取らなくて良い前提になります。この時、仮に遷移が変数ごとだとすると、変数ごとにそれぞれ焼きなます場合と完全に同じ振る舞いになると思います

コルン @colun

@nico_shindannin 私も初心者なので、私の方が間違ってる可能性もあるのですが、とりあえず根拠を述べます。 t1℃でx1が変化して、t2℃でx2が変化して、t3℃でx1が変化して、t4℃でx2が変化して という順番だったとします。

コルン @colun

@nico_shindannin これは、x1とx2が独立なら、以下のように書き換えることができます。 t1℃でx1が変化して、t3℃でx1が変化して、t2℃でx2が変化して、t4℃でx2が変化して 教科書通りの遷移確率関数なら、温度と得点差のみに確率は依存します。

コルン @colun

@nico_shindannin 完全独立であっても、遷移が独立に行われるのなら、分離してもしなくても完全に同じ動作。独立ではなく他変数と関連性があるのなら、一緒に焼きなます必要がある。。。というわけで、盲目に一緒に焼きなます一択だと個人的には思っています。

コルン @colun

@nico_shindannin x1とx2の遷移が一緒に行われる場合については、あまり深く検証できていません。また、診断人さんの記事の「1変数ごとに焼きなまし」が「1変数ごとに遷移」ということでしたら、全くその通りだと思います。

コルン @colun

@nico_shindannin なお、付け加えておきますが、仮に他変数と関連性が高い場合であっても、温度管理さえきちんと出来ていれば、「1変数ごとに遷移」であってもきちんと焼きなましの恩恵を受けることができるという認識です。

コルン @colun

@nico_shindannin 逆に複数変数を一度に変化させる必要性を強いられるのは、山登り法の特徴の様な気がします。

hotpepsi @hotpepsi

@masashinakata 作るの忘れてました。やってみます。

tek1031 @tek1031

CODEVSは3月なんですか、たぶん忙しすぎてやばい時期なの爆発四散

tek1031 @tek1031

そろそろ新しい世代が・・・　とか言ってたけど前回決勝行けてないんで世代交代はすでにしている

はまづ @hama_du

はてなブログに投稿しました #はてなブログ マラソンマッチで最初の12時間にすべきこと - hama_duのブログ hama-du.hatenablog.com/entry/2015/12/… pic.twitter.com/vBBoRoHQkq

拡大

はまづ @hama_du

AWS S3+SQS+Lambda で格安でセキュアなジャッジシステムを作ろうとして一ヶ月溶かした by @hama_du on @Qiita qiita.com/hama_du/items/…　裏番組