hhmm1st.txt

-*- mode:my-memo; coding:utf-8 -*-
Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 の
参加中メモ。上が一番新しいので、下から読んでね
------------------------------------------------------------
[2017-11-28 23:40:35]
最終submitで
- 現状維持(s026)
- 差し戻す(s025)
- 新しいやつ(s026 を改善した？でもローカルで s026 に 0.012% 負けてる)

ローカルですべてほぼ同じスコアなので、
ローカルと鯖の環境違いが効いてる可能性を考えると、
鯖で高得点の s025 に差し戻すのが正解っぽいなあ
------------------------------------------------------------
[2017-11-28 23:35:56]
[s026] (gaiko.cpp rev1.1)
uniform をやらない感じ

          s025          s026
#150     4970.68 <     4970.89 (+0.213 / +0.004%)
">"(66)  "="(15)  "<"(69)

163399 (-175)

たぶんガシャ運の範囲だよなあ
------------------------------------------------------------
[2017-11-28 20:09:59]
[s025] (fina.cpp rev1.8)
この伸びは submit ガシャ運っぽい

163574 (+ 493)
------------------------------------------------------------
[2017-11-28 20:07:11]
gettimeofday() は重い？

コードテストで試してみよう (test_gettimeofday.cpp rev1.1)

10000回呼んで 3~4ms だった。
気にすることではないのう
------------------------------------------------------------
[2017-11-28 20:01:23]
(fina.cpp rev1.8)
- sa_t(10.0, 0.1) -> sa_t(3.0, 0.5)
------------------------------------------------------------
[2017-11-28 15:50:43]
[s024] (fina.cpp rev1.1)
なんだかんだでうまく行ってないので、s023 をそのまま 9.0sec -> 9.8sec に。

163081 (+114)
------------------------------------------------------------
[2017-11-28 01:49:47]
sa.accept(0) が常に true なのマズくね？
- enumerate すると、全部反転して戻ってくる感じになるやん

独立だとすると 1/2 で accept か？

芳しくない
------------------------------------------------------------
[2017-11-28 01:48:35]
edge とか関係なく、隣接マスswap はやるべきなのでは？
sparse でノードを端に詰めたりみたいな

-> すでに隣接してる状態の pivot が隣接マスswapの役目を果たしてる的な
------------------------------------------------------------
[2017-11-28 01:04:50]
expってどのくらい重いのん？(test_exp.cpp)
------------------------------------------------------------
[2017-11-27 21:17:32]
偏りがあるから sparse なヤツだと 8*V に特定の頂点の edge が
ゼロってありうるかもだ？

さすがになかった
------------------------------------------------------------
[2017-11-26 22:17:07]
next_cell[].size() は 3, 5, 8 がありえるけど、
rng.get(5) はロスい。

ところで uniform_int_distribution だと 3, 5, 8 に時間差ないっぽいけど
どう実装されてるん？

あー別に 5/8 で accept じゃなくて、
たとえば 255/256 で accept した後に 51 で割ればいいのか

next_cell[].size() はほぼほぼ 8 で、
4/W くらいの確率で 5 だから（中央によるからもっと低い）
特別に何かするほどのことでは無いだよ
------------------------------------------------------------
[2017-11-26 22:15:48]
(edge.cpp rev1.9)
ランダムで edge を swap するんじゃなくて、swap したやつも
候補に突っ込んどいて shuffle しとく

速度は大差なし。デメリットがあるはずなのでやめとく
------------------------------------------------------------
[2017-11-26 21:18:42]
(edge.cpp rev1.8)
es を vector<edge_t> から vector<pair<int16_t,int16_t>> にして、iter +1%くらい
------------------------------------------------------------
[2017-11-26 18:38:53]
[s023] (edge.cpp rev1.6)
密なとき(E > 0.3*Ec)は、W を大きめに

#150     4956.47 <     4962.81 (+6.340 / +0.128%)
">"(54)  "="(16)  "<"(80)

162967 (+95 / +0.058%)
------------------------------------------------------------
[2017-11-26 11:30:20]
[s022] (edge.cpp rev1.4)

#150     4950.20 <     4956.47 (+6.267 / +0.126%)
">"(56)  "="(18)  "<"(76)

162872 (+346 / +0.212%)

------------------------------------------------------------
[2017-11-26 10:17:29]
0.1*Ec というのがてきとーすぎる。
Vに対して定数倍、というのはありえる

(edge.cpp rev1.4)
8*V でやってみる
------------------------------------------------------------
[2017-11-26 00:24:54]
[s021] (edge.cpp rev1.3)

162526 (+859)
------------------------------------------------------------
[2017-11-26 00:16:30]
(edge.cpp rev1.3)
dense なグラフも（スコアの低い）辺を減らして、エッジベースで回すか。
とりあえずmax(100, 0.1*Ec) まで選ぶ
Ec は完全グラフの辺数 = V*(V-1)/2 な。

          s020        edge r1.3
#150     4919.83 <     4950.20 (+30.367 / +0.613%)
">"(37)  "="(13)  "<"(100)

伸びすぎてヘンな声が出た
何かおかしいのでは？

あ、あと uniform を 0.1 で打ち切ってる
------------------------------------------------------------
[2017-11-25 23:18:32]
[s020] (edge.cpp rev1.2)
edge ベースを実装した。

           s019         s020
#150     4922.13 >     4919.83 (-2.293 / -0.047%)
">"(71)  "="(14)  "<"(65)

まあ伸びてない（むしろ落ちてる）けど投げるだけなげる

161667 (+131)

謎うｐだけど、誤差だよ誤差
------------------------------------------------------------
[2017-11-25 00:22:22]
序盤に、距離dだとスコア +w/d みたいな、なんらかの拡張問題としてやる？
近くにあるとなんとかなるかもじゃん？
------------------------------------------------------------
[2017-11-25 00:22:05]
SA のパラメータいじりは闇なので保留
------------------------------------------------------------
[2017-11-24 12:53:28]
[s019] (climb.cpp rev1.7)

          s017          s019
#150     4892.93 <     4922.13 (+29.193 / +0.593%)
">"(38)  "="(12)  "<"(100)

5th    161536 (+856 / +0.530%)
ほぼ予想通りだのう
------------------------------------------------------------
[2017-11-24 06:22:00]
s017-s018 のいいとこどりで 161739。
sparse が s017、それ以外がs018　だと 161636。

dense_factor が 0.05 あたりで sa(10.0,1.0) と sa(5.0,2.0) を切り替え？
(climb.climb rev1.7)
------------------------------------------------------------
[2017-11-24 05:28:38]
[s018] (climb.cpp rev1.6)

10xx     5403.41 <     5443.70 (+40.290 / +0.740%)
">"(29)  "="(9)  "<"(62)

ローカルではすごい伸びた！と思ったら、
160595 (-85)

ケース別で見ると、sparse で悪化してるのう。

20xx    3116.95 >    3035.01 (-81.940 / -2.629%)
">"(83)  "="(7)  "<"(10)

たしかに sparse でガタ落ちしてる

いい加減、テストケースに sparse も入れようぜ

本番は
random 50
complete 60
sparse 40
の計150ケースっぽい。
------------------------------------------------------------
[2017-11-24 05:28:01]
(climb.cpp rev1.6)
pivot も sa(5.0, 2.0) にした

これ前やって、鯖ではアカンやったやつな気もする…
とりあえず投げるか
------------------------------------------------------------
[2017-11-24 03:50:23]
(climb.cpp rev1.3, 1.4)
next_node や next_cell を選択するのも rand じゃなくて
enumerate にしてみた

けど、（多分）互いに素制約が満たせないのでスコアはダメですわ。
rev 1.2 に revert する。
------------------------------------------------------------
[2017-11-24 03:49:33]
ちょっとclimbを切り分ける
(climb.cpp)

(climb.cpp rev1.2)
uniform を sa(5.0, 2.0) にする
------------------------------------------------------------
[2017-11-23 23:19:57]
dense な方が、局所スコア大きくなるから、初期温度高くないといけない？
------------------------------------------------------------
[2017-11-23 22:16:01]
部分グラフをまとめて移動できたらいいのにねえ
------------------------------------------------------------
[2017-11-23 16:31:48]
あー重さ0の辺が存在するから、pivot のときは除外した方がいいはず
------------------------------------------------------------
[2017-11-23 14:30:43]
アイデア
- 3点 swap
- 盤面の一部分をシフトする
------------------------------------------------------------
[2017-11-23 07:12:37]
[s017] (pivot.cpp rev1.11)
- sa(10.0, 0.5) -> sa(10.0, 1.0)


------------------------------------------------------------
[2017-11-23 06:43:35]
(table_result.rb)
result-* を比較してみた

sparse 以外は s014 がいいっぽい。
sa(10.0, 1.0) だな？

投げてみるか。

------------------------------------------------------------
[2017-11-23 06:15:57]
[s016] (pivot.cpp rev1.10)
- e/e_c > 0.5 なら SA_uniform() 旧来
- e/e_c < 0.5 なら、progress < 0.6 なら uniform、超えたら pivot。

14th: 159927 (+341)
------------------------------------------------------------
[2017-11-23 05:18:24]
e/v**2 が低いと pivot 有利なはず

(th.rb)
比較して e/v**2 でソートして th より上か下かで切り替えるやーつ

0.25 より小さいなら pivot、かなあ

あー気持ち的には complete graph の E = v*(v-1)/2 との比率にしたいかも？
となると e/e_c < 0.5 かなあ

------------------------------------------------------------
[2017-11-23 03:59:26]
(pivot.cpp rev1.3)
> a = rng.get(V)+1
じゃなくて
> a = (same as uniform)
したらスコア上がるんですけどー

一様性なのか局所性なのか。確かめる？

いや、一様性だろ。a -> a+1 には局所性は無い
------------------------------------------------------------
[2017-11-23 03:30:04]
なんか pivot うまくいってない感じ (sparse なケースで s015 よりだいぶ落ちる）

sparse に特化したはずなのに sparse だと 2% 落ちるの問題外って感じでは

          s015        pivot r1.2
10xx     5375.06 >     5359.61 (-15.450 / -0.287%)
">"(53)  "="(11)  "<"(36)


          s015        pivot r1.2
20xx     3074.57 >    3018.50 (-56.070 / -1.824%)
">"(80)  "="(5)  "<"(15)
------------------------------------------------------------
[2017-11-23 03:29:47]
seed: 2004
V: 295
E: 294
(double)E/V: 0.99661
------------------------------------------------------------
[2017-11-23 02:24:25]
(pivot.cpp)
↓ これやる
------------------------------------------------------------
[2017-11-23 00:31:23]
sparse なヤツ、大抵のswap が無効なので
エッジのあるやつでしかやらないとか？

cell r (node c) を選ぶ
c と辺のある a (node p) と
r に隣接してる q (node b) を swap、みたいな？
------------------------------------------------------------
[2017-11-22 23:41:14]
s013 と比べて 1.5倍くらい回ってる
SA のパラメータ変えたときの挙動が全然思った風じゃないので
単純速度UP以外に、何をチューニングすべきかわっかんねー
------------------------------------------------------------
[2017-11-22 23:05:18]
generator に E を V*4以下、次数を8以下に抑えるオプションつけて生成
(testcase/tc-20xx.txt)

[log-uniform-r1.2-20xx.txt]

Error: "phi" must be injective function
seed:2079 -> 0

再実行したけどエラーじゃない。再現性はないのう

解が単射じゃないということ。
出力時に a は 1~V を舐めてるので uniq。
よって
- fo[a] がかぶってる or
- fo[a] の分解→結合でかぶる
のどっちか。

あー seed: 2079 で
> lq*INNER_ITER: 100860000
> cur_score: 586
> best_score: 611
> assign.score(): 611
> == hill climbing
> cur_score: 617
> best_score: 617
> assign.score(): 618
hill climbing の後の score() が計算違ってる。これか？

無理やり hill climbing するように sa をでかくして走らす

あー Error: "phi" must be だ

あー for(a) for(j) を、for(j) for(a) をひっくり返したんだから
p = q じゃなくて q = p だ。

------------------------------------------------------------
[2017-11-22 22:32:31]
[s014] (uniform.cpp rev1.2)

WA もらってるんですけどー。
sparse_05	0 / 1000000	C026_scrambled
sparse_06	0 / 1000000	C027_scrambled


------------------------------------------------------------
[2017-11-22 21:46:50]
(uniform.cpp rev1.1)
a, q を 乱数じゃなくて enumerate してみたよー

- V == V_emb のとき 互いに素じゃないからアレ
------------------------------------------------------------
[2017-11-22 19:22:00]
[s013] (quiet.cpp rev1.10)
- q の範囲を a から距離1以内に制限

          s012          s013
#100     5354.82 <     5358.55 (+3.730 / +0.070%)
">"(54)  "="(8)  "<"(38)

          s010          s013
#100     5347.91 <     5358.55 (+10.640 / +0.199%)
">"(38)  "="(7)  "<"(55)

14th 159310

------------------------------------------------------------
[2017-11-22 16:23:28]
- int q = rng.get(W*W)*(W+1)/W + W+2;
+ int q = pre_computed[rng.get(W*W)];

にするだけで、2割くらい速くなったんだけどマジか…
------------------------------------------------------------
[2017-11-22 15:35:57]
- 評価値の出現回数で遷移するやつ
------------------------------------------------------------
[2017-11-21 23:48:49]
[s012]
- sa(10.0, 2.0)
- 山登
------------------------------------------------------------
[2017-11-21 23:46:52]
アイデア
- ws[] (コストテーブル)を半分に
- W を一回り大きく取る
------------------------------------------------------------
[2017-11-21 17:55:48]
[s011] (guessiter.cpp rev1.2)
鯖で何回くらい回ってるのか知るために、
score が lq/2 になるように寄せてみる
------------------------------------------------------------
[2017-11-21 04:20:41]
[s010] (quiet.cpp rev1.1)

s008 の log 出力とかを削ったバージョン

12th 159057 (+600)
------------------------------------------------------------
[2017-11-20 23:18:20]
(smemo.cpp rev1.10)
too_bad は実装できたはず
どこから too_bad 使うのに切り替えるかがねぇ。

         s008          smemo rev1.10
#100     5335.49 <     5342.79 (+7.300 / +0.137%)
">"(45)  "="(8)  "<"(47)
         s009          smemo rev1.10
#100     5351.54 >     5342.79 (-8.750 / -0.164%)
">"(56)  "="(7)  "<"(37)

------------------------------------------------------------
[2017-11-20 15:51:51]
swap評価値の受理確率が eps を下回ったらメモ
それは選択しない、
swap 起きたらメモクリア、みたいな？

発展的には、
vector と set で二重に持っておいて、
vector.sample() で選ぶ感じ？
------------------------------------------------------------
[2017-11-20 15:51:23]
いまの SA-mod のやり方はいったん保留
------------------------------------------------------------
[2017-11-20 15:08:54]
smemo.cpp rev1.8 seed:1098 で落ちる
sc_memo[] の範囲外代入が原因っぽい。
なんで範囲外に？

> for (int j=0; j<=W*W; j++)
jをW*W まで(inclusive)回してたのが原因。
------------------------------------------------------------
[2017-11-19 23:29:37]
(smemo.cpp rev1.8)
SA-mod に着手
------------------------------------------------------------
[2017-11-19 17:31:58]
[s009] (smemo.cpp rev1.6)

          s008          s009
#100     5335.49 <     5351.54 (+16.050 / +0.300%)
">"(39)  "="(5)  "<"(56)

(13th 158457)
158396

うーん、スコア落ちたのう。
鯖とはiteration が違うからにゃんとも言えないんだよなあ
------------------------------------------------------------
[2017-11-19 17:20:24]
(smemo.cpp rev1.6)
- 焼きなましを冷やしすぎない
-- sa_t(10.0, 0.5) -> sa_t(10.0, 1.0)
-- 最後に山登り

安定しない感じだなあ…
でも s008 よりは上なはずなので投げるか
------------------------------------------------------------
[2017-11-18 02:39:13]
[s008] (smemo.cpp rev1.3)
- ローカル用の画像出力のコードのっけてるけどー
- まあ rev1.2 と同じということにして log もそれ保存しとく

          s007          s008
#100     5322.44 <     5335.49 (+13.050 / +0.245%)
">"(37)  "="(7)  "<"(56)


------------------------------------------------------------
[2017-11-18 02:36:55]
(smemo.cpp rev1.2)
空白にも置くように。
かなりムダがあるけどどうか

いちおープラス。

          s007
#100     5322.44 <     5335.49 (+13.050 / +0.245%)
">"(37)  "="(7)  "<"(56)

          rev1.1
#100     5327.18 <     5335.49 (+8.310 / +0.156%)
">"(37)  "="(7)  "<"(56)


------------------------------------------------------------
[2017-11-17 17:52:49]
(smemo.cpp rev1.1)
グラフの変形にそなえて、 memo_sc を a じゃなく p で記憶

局所性があがる恩恵がある？
------------------------------------------------------------
[2017-11-17 15:01:07]
[s007] (assign.cpp rev1.10)

6th 158274
------------------------------------------------------------
[2017-11-17 14:58:32]
[assign.cpp rev1.10]
- SA は int なので、accept 確率はテーブルを引くように
- xor128_t (64x2) の実戦投入

          (s006)      (assign.cpp rev1.10)
#100     5285.66 <     5322.44 (+36.780 / +0.691%)
">"(31)  "="(6)  "<"(63)
------------------------------------------------------------
[2017-11-17 13:49:07]
- 形決め打ちなのを何とかする?
- 時刻における遷移確率を見てみる
------------------------------------------------------------
[2017-11-17 02:34:36]
仮に10倍速くなったら何が起きる？というのを知るために
TIME_LIMIT を 10倍にして走らせてみる

#100     5307.83 <     5434.75 (+126.920 / +2.335%)
">"(3)  "="(7)  "<"(90)

うーむ、これで16.1万相当だから、このレベルのスコア上昇が必要か
------------------------------------------------------------
[2017-11-17 02:33:07]
(assign.cpp rev1.9)
キャッシュを意識してデータ型をint8_t とかに

s006 -> assign.cpp rev1.9
rev1.8 よりちょい速いけど、iteration数が少なかったとこほど伸びが大きい
------------------------------------------------------------
[2017-11-16 23:39:53]
局所スコアをメモるか。
(assign.cpp rev1.8)

s006 -> assign.cpp rev1.8
iteration が 1.1~1.3倍ってとこかなあ
------------------------------------------------------------
[2017-11-16 23:39:02]
SAパラメータいじりとかしてる
してる場合じゃないよ

とりあえず
(2.0, 2.5)
(2.0, 0.5)
(100.0, 0.05)
(10.0, 0.5)  <- これ
------------------------------------------------------------
[2017-11-16 16:11:32]
[s006] (assign.cpp rev1.3)

          s005          s006
#100     5034.71 <     5285.66 (+250.950 / +4.748%)
">"(3)  "="(7)  "<"(90)

3rd  	157372
------------------------------------------------------------
[2017-11-16 15:57:38]
[assign.cpp rev1.3]
- V = 1 のとき出力おかしかったので修正
-- E = 0 だから initial_assignment() で初期値が 0 になってた
- ログが大量すぎるから出力量を減らす
-- lq%100 == 0 のときだけ
-- [FIXME] というか鯖では出力抑制すべきでは
------------------------------------------------------------
[2017-11-16 15:40:27]
[assign.cpp]
- assign_t: 順方向(fo), 逆方向(ba) を vector にした
-- 入力の Gemb じゃなくて、必要最小限サイズの King's Graph で持つ
--- 出力時はノード番号の変換が必要なので注意！
-- 番兵に空白行・列を入れることで、隣接ノードをノード番号で直指定できるように

s005 vs (assign.cpp rev1.2)
あんま iteration かわらん、と思ったら1桁違ってた

#100     5034.71 <     5285.87 (+251.160 / +4.752%)
">"(1)  "="(7)  "<"(92)

------------------------------------------------------------
[2017-11-16 00:03:49]
[s004] (simple.cpp rev1.16)
- 隣接辺を特別扱いしない
- sa_t(10.0, 0.1) -> sa_t(10.0, 0.5)

24th 150708
------------------------------------------------------------
[2017-11-15 23:48:19]
隣接ノードのswapはノードごとにスコア計算すると
同じ辺を2回カウントするからダメ、みたいに思い込んでたけど、

同じ辺だとswap前後での差分は0なんだから、2回カウントしても無問題だった。
------------------------------------------------------------
[2017-11-15 18:24:45]
[s003] (simple.cpp rev 1.14)
- SA
- 出力logを簡素化

18th 146273
------------------------------------------------------------
[2017-11-15 14:47:57]
SAにする。
差分スコアを持っておく。
絶対遷移するSA。
------------------------------------------------------------
[2017-11-15 14:44:32]
[s003] (simple.cpp rev1.8)
swap で山登り。swapした8近傍だけのスコアで差分計算

21st 135231
------------------------------------------------------------
[2017-11-15 03:18:36]
King's Graph で最密な（頂点数について最も辺の多い）選択って？

ちょっと舐める(dense_king.rb)
八角形？
------------------------------------------------------------
[2017-11-15 02:21:37]
(simple.cpp rev1.2)
seed: 1097 が out of range (output)

V と V_emb が近いせいで wrap すると K*K を超えちゃってた。
wrap を sqrt(V) じゃなくて ceil(sqrt(V)) にするよ
------------------------------------------------------------
[2017-11-15 02:17:03]
(simple.cpp rev1.1)
seed: 1031 で SEGV

おー、seed: 1031 は V=1, E=0 だ。
コーナーケース引くとかやるじゃん
------------------------------------------------------------
[2017-11-15 02:08:48]
[s001] (simple.cpp rev1.1)
いくつかのケースでエラーがでるけど、あえて投げて挙動を見てみるか

WA があるけど順位表に乗るな。WAは単に0スコアとして扱われるもよう。

各テストケースのスコアが見れるのな
[提出一覧]→[自分の提出]→[詳細]
result-sXXX.txt にコピペしとこう
------------------------------------------------------------
[2017-11-15 02:04:21]
upper bound を考える。
G_emb は高々degree:8 なので、
G の各頂点について高々8個しか辺を充足できない
ので高い方から8個が upper bound。

全頂点について↑を足した上で（二度数えてるから）2で割ると、全体の upper bound
------------------------------------------------------------
[2017-11-15 01:10:00]
辺に重みの付いた頂点を、
既知の定形グラフの頂点に対応付けて、
対応先でも辺があるような辺の重みの和、を最大化。

これ相対スコアじゃないから、最大ケースで高スコアとればいいって話だよね？
うーん。
ランダムグラフの最大スコアは MAX_E*MAX_C で抑えられる

と思ったら、MAX_E は 20000 で
ランダムグラフは |V| <= 500 だけど
完全グラフは |V| <= 200 ( |E| <= 200*199/2 = 19900 ) だから
まあそんな感じか
------------------------------------------------------------
[2017-11-15 00:23:17]
readme が Markdown で読みにくい（こなみ）。
フォーマッタとか探してたけど手頃なのがわからんから諦める
------------------------------------------------------------
[2017-11-15 00:22:38]
グラフの実用（用途のある）問題らしいけど、マラソン的に面白い問題なことを祈る
chokudai さんを信じよう
------------------------------------------------------------