やったこと

ジャンクガレッジで辛ラーメンを食べた。やはり辛いものは苦手だ（昨日財布を忘れた腹いせ）

配列のrotateについて

長さNの配列をD個分rotateするには、いくつか方法がある。

1. 一時配列を使う方法

D個分の要素を先頭からコピーして、配列の残りの要素を先頭まで持ってきたあとコピーしたものをその後ろに追加する方法。一番直感的。
N - D < Dの際にN - D個分後ろからコピーするようにしたりすると、Dが極端に小さい/大きい場合は十分に早いのだけどDがN / 2に近付くとかなり遅くなる。
あとin-placeじゃない。

2. ジャグリング法

D = 1の場合、0番目の要素を保存しておいて、1番目の要素を0番目に移動して、2番目を1番目に移動して、をN - 2番目の要素まで繰り返しN - 1番目に保存しておいた0番目の要素を移動すれば完了する。
しかしD >= 2の場合、同じようにしようとすると、保存しておかなきゃいけない先頭の要素の数がD個になってしまい、in-placeにならない。そこで(i + D) % N番目の要素をi % D番目に代入したら、次は(i + 2 *D) % N番目の要素を(i + D) % N番目の要素に代入し、最初の位置の手前に戻ってきたら保存しておいた最初の要素を代入する、という風にする。するとDとNがもし互いに素なら一周すると開始位置が1ずれて、何周か繰り返すうちに最初の位置に戻ってくるようになり、完了する。DとNが互いに素でないなら最大公約数だけ系列が存在するので、開始位置をずらして全ての系列に対して同じことをしていけばいい。
こうすることで、in-placeで内側のループの回数はN - GCD(N, D)回で動く。GCD(N, D)が大きくなるとき（例えばNが2の倍数のときのD = N / 2のとき）に群を抜いて高速になるが、それ以外のときは全体的に遅めな気がする（ランダムアクセスすぎてキャッシュに載らない？）。

3. ブロックスワップ、リバース

明日解説する。眠い。

とりあえず、ブロックスワップが優秀な気がするのでこれで行きたい。

重要なことは、rotateは使われるとしたらD = 1かD = -1で少しずつ回転させていくか、もしくは様々な大きさで満遍なく回転させるかのどちらかだと予想できて、現状の実装は様々な大きさの場合にパーフォーマンスがそこまでよくなくて、また|D| = 1の場合もそれならメモリ確保は不要なのだということ。個人的にはどうにかしてin-placeでいいという流れにしたい。少なくともRubyはin-placeだった。