TCO16 MM R3
-
masashinakata
- 17041
- 0
- 0
- 0
-
- いいね！0
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
結局末端コストは同じなんだけれども、早期枝刈りと、ループ最下層じゃない箇所での少し重めのコストが削れる。 ループ最下層じゃないけど、最下層が多重ループからlog処理へと既に書き換わってるため、従来4重ループだったものが１重ループ４つに書き換わってる。このため、最下層の１つ手前。
2016-07-05 09:16:43
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
最下層の１つ手前を削れるし、しかも早期枝刈りがある。しかもその順序をいじれるので、結構な高速化になるはず。
2016-07-05 09:17:33
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
具体的には、従来、5optで両端除いて決めなきゃいけない所が4箇所、 ABCD とあるのに対して、従来はA→B→C→Dと決めてきた。 これを、 キャッシュ化(D)+(A→B→キャッシュD→C)の順序で処理する。
2016-07-05 09:19:43
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
AとBが決まっている状態では、 ・Cが決まればDも決まる。 ・あるいは、Dが決まればCも決まる。 わけなので、CとDの選択の順序は元から同時だけれども、それが問題ないかどうかの判定は個別に行われて枝刈りされる。
2016-07-05 09:23:22
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
枝刈り判定は同時には行われない（同時に行うと、よほど判定処理が低コストでない限りは、常に悪い）ので、枝刈り判定には順序がある。
2016-07-05 09:26:06
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
焼きなましの揺らぎを作るために、log2(randFloat())を使っているのだけれども、これが計算時間のそれなりを占めていた模様。少し削って実験しよう。でも、これは重要な可能性もある。
2016-07-05 10:48:40
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
パターンごとに共通の値を使っている箇所を、もうちょっと範囲を広げて共通の値を使うようにするという話ね。
2016-07-05 10:49:43
まなめ
@maname
「コンピューターが問題を解きやすいように、人間が知恵を絞ること」これな。 / “「プログラミング」と「プログラミング的思考」の違いを、分かったつもりになれるヒント - SenseiCode” htn.to/5RKKP8
2016-07-05 10:57:10
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
おそらく探索性能は行き着く所まで行き着いている様な気がするので、後は距離定義の問題で、現在最終焼きなましでやっていることを、距離定義の段階でやることで、かなり点数が上がる余地がある。
2016-07-05 12:24:47
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
今焼肉中で、手元にデータがないので分からないけれども、たしか0.4%ぐらい、最終焼きなましで点数が上がっていたはず。
2016-07-05 12:26:29
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
最終焼きなましで、点数が上がる場合から、下がる場合まであるのだけれども、その平均が、0.4%ということ。これが仮に0〜0.8%に分布しているなら、全て0.8%を取れば差額で現在から0.4%上がる。仮に0.2〜0.6%に分布しているのなら、全て0.6%を取れば差額で0.2%上がる。
2016-07-05 12:29:15
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
つまる所、決勝点への大きな足がかりになる可能性がある。また、1位の点の均一さから考えて、この様な機構は必ず入っている。
2016-07-05 12:30:38
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
この辺になってくるとゴルフみたいな感じになってくるので、ドラゴンレーダーをまず持っている必要があって、筋斗雲は必須ではない。
2016-07-05 12:35:24
コルン
@colun
マラソンマッチをドラゴンボールに喩えるの、それなりに合ってる気がする。 ドラゴンボールの位置を知る、ドラゴンレーダー。 位置が分かった時にいち早く目的地に到着する、筋斗雲。 同じ位置にいる相手に打ち勝つための、如意棒。
2016-07-05 12:41:06
コルン
@colun
ドラゴンボール1つ目ぐらいだったら、ドラゴンレーダーがなくても、噂を聞きつけ偶然場所を知り、それが偶然近くてドラゴンボールを入手できるかも知れない。 でも、全部集めるためには、ドラゴンレーダーは必須。 場所が分かっても、そこは地球の裏側かもしれない。筋斗雲も出来れば欲しい。
2016-07-05 12:44:11
コルン
@colun
時間が充分にあれば、筋斗雲がなくても飛行機とか船を乗り継いで目的地には到達できる。が、場合によってはドラゴンボールの方が少しずつ動いていて、筋斗雲がないとドラゴンレーダーに引っかからない状態のまま時間切れになるかもしれない。超高性能な筋斗雲じゃなくても、自家用機ぐらいは欲しい。
2016-07-05 12:48:23
コルン
@colun
目的地にたどり着いたとしても、同じ様にドラゴンレーダーを持ち、ドラゴンボールを集めている競合がいるかもしれない。集めたドラゴンボールの数が増えれば増えるほどに競合の数は減っていくが、それでもなお最後のドラゴンボールにたどり着いた後に残った競合に打ち勝つためには、如意棒が欲しい。
2016-07-05 12:51:51
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
自己評価だけれども、僕は ドラゴンレーダー：A+ 筋斗雲：B 如意棒：A という感じな気がする。 勝手なレッテル貼りになってしまうけれども、たとえばchokudaiさんだと ドラゴンレーダー：A 筋斗雲：S+ 如意棒：A+ という風に見える。 PsyhoさんはオールS。
2016-07-05 13:13:15
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
marekさんは問題限定で如意棒がS+な予感。 wleiteさんはオールA+ぐらいな認識。 ainu7さんは如意棒Sで他がA+なイメージだな。 A+は凡人レッドコーダーで到達可能な上限。Sはレッドコーダー中でも最高級。S+は全プレイヤーの中でその域に達する人が数名しかいない。
2016-07-05 13:21:02
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
高速なコードを書く力は如意棒に含まれるけれども、おそらくそれよりも定番的なデータ収集からのパラメータ調整力の方が如意棒としては支配的。ドラゴンレーダーは、何の手がかりもない状態から糸を辿る能力。
2016-07-05 13:31:02
コルン＠TCO16MR2&MR3
@colun_t4o3yv5g
Komakiさん、如意棒A+かな。 なお、レッドコーダーに手っ取り早くなる方法は、昔だったらドラゴンレーダーA+だけあれば他がひどくてもなんとかなった。 今は定番問題率が増えて、ドラゴンレーダーよりも如意棒重視になりつつある気がする。
2016-07-05 13:53:40