自分が気になったこと、今後知りたいことのメモで何かの解決策とか役に立つことは一切書いてません。
年末年始でAtCoderを始めて問題を解くことにハマっています。difficulty1000前後の問題をやるのが楽しいです。
Rubyを利用して問題を解いている中で文字列の添字アクセスでの書き換え等を行ったりしていた際の処理速度に違和感を感じたので少し調査しました。
AtCoderで動作するRubyは2.3.3なので2.3系とそれ以降でDockerで実験してみました。
require 'benchmark'
str = 'A' * 50000
puts Benchmark.measure{
1000.times do
10000.times do |i|
str[i+25000] = "B"
end
end
}
$ docker run -v $HOME/sandbox:/sandbox ruby:2.3 ruby /sandbox/string_benchmark.rb
28.600000 0.010000 28.610000 ( 28.656694)
$ docker run -v $HOME/sandbox:/sandbox ruby:2.4 ruby /sandbox/string_benchmark.rb
29.080000 0.010000 29.090000 ( 29.140195)
$ docker run -v $HOME/sandbox:/sandbox ruby:2.5 ruby /sandbox/string_benchmark.rb
1.380000 0.000000 1.380000 ( 1.383977)
$ docker run -v $HOME/sandbox:/sandbox ruby:2.6 ruby /sandbox/string_benchmark.rb
1.380000 0.000000 1.380000 ( 1.386950)
$ docker run -v $HOME/sandbox:/sandbox ruby:2.7 ruby /sandbox/string_benchmark.rb
1.450000 0.000000 1.450000 ( 1.458249)
2.5でかなり高速化されていることが確認できます。
Array#concat、Enumerable#sort_by、String#concat、String#index、Time#+、などの組み込みメソッドの速度が向上しました。
Rubyのstring.cの2.4=>2.5の変化に答えはあるんでしょうが、大規模C言語プロジェクトを自分がちゃんと追いきれずどの部分がこのパフォーマンスの変化に繋がったのかまだわかっていないので、そういう部分も追えるようになるのは今後の課題ですね。
こちらのRubyソースコード完全解説が参考になるかもとは思うのですが書かれたのが1.7.3の頃で15年以上前のものなので、現代版が発売されて欲しい気持ちです。
ちなみにAtCoder上での文字列添字書き換えでのパフォーマンス低下に関してはsplit('')して配列として扱う、添字アクセスの変わりにgetbyte, setbyteを使う(ASCII文字だけなので)等で解決できました。
追記
2020年01月02日 11時54分 (JST)に肝心の実験コードを別のコードと取り違えている事に気づき、修正を行いました。