どうかくE22とjit

問題: 辞書順に数を並べる 2018.3.3

実装: github.com

とりあえずナイーブに解いたやつ。鍋谷さんは「Rubyでは解けないくらいの計算量にしたつもりだった」と言っていたが案外解けている。

$ ruby -v
ruby 2.6.0preview1 (2018-02-24 trunk 62554) [x86_64-darwin17]

MacBook Retina, 12inch, 2017 1.4GHz Core i7 メモリ16GB

$ time ruby test.rb
ok 1
ok 2
ok 3
ok 4
ok 5
ok 6
ok 7
ok 8
ok 9
ok 10
ok 11
ok 12
ok 13
ok 14
ok 15
ok 16
ok 17
ok 18
ok 19
ok 20
ok 21
ok 22
ok 23
ok 24
ok 25
ok 26
ok 27
ok 28
ok 29
ok 30
ok 31
ok 32
ok 33
ok 34
ok 35
ok 36
ok 37
NG: 0
ruby test.rb  829.58s user 107.90s system 91% cpu 17:05.94 total

jit

$ time ruby --jit test.rb
ok 1
ok 2
ok 3
ok 4
ok 5
ok 6
ok 7
ok 8
ok 9
ok 10
ok 11
ok 12
ok 13
ok 14
ok 15
ok 16
ok 17
ok 18
ok 19
ok 20
ok 21
ok 22
ok 23
ok 24
ok 25
ok 26
ok 27
ok 28
ok 29
ok 30
ok 31
ok 32
ok 33
ok 34
ok 35
ok 36
ok 37
NG: 0
ruby --jit test.rb  752.21s user 114.54s system 95% cpu 15:06.41 total

約10%の高速化、な気がする (あまりベンチマークに詳しくない)

別解法を考えた。枝刈りバンバンしていくことでなんとかならないか、というやつ。
そもそも実装がよくわからんけどミスっているのと「xが大きいときにはやくならないですね」という指摘を受けてばたんきゅ〜
n進数なのに木構造を使わなかったのはちょっとダメな気がした。