安西先生、高速化がしたいです… - KBDAHOLIC

諦めたらそこで試合終了ですよという声が聞こえた気がしたので一昨日書いた autoload/color/xterm256.vim の color#xterm256#RGB2Nr() を最低で約 12 倍、最高で 28 倍ほど高速化。これで colorscheme の読み込みも速くなりっ。

base 16 と colorcube と grayscale とでは全然性質が違うのですべての色を同じ色空間にあると仮定して計算するよりは個別に探索関数を書いてやった方が速くなるはず、というわけで以下それぞれに試した手法。

base 16
1. 1 色ずつ距離を計算して最短になるものを探す。距離が 0 のものが見つかったらそこで計算終了。
2. 16 色分の距離をすべて計算してから最短の距離の色を探す。
colorcube
1. 1 色ずつ距離を計算して最短になるものを探す。距離が 0 のものが見つかったらそこで計算終了。
2. 3 次元空間における最短距離 ( を持つ色 ) を求めたいわけなのでそれぞれの軸 ( RGB ) からの距離が一番短いものを個別に求めることと同義。というわけで RGB の各成分は 6 つの離散的な値のうちどれかを取ると決まっているのでその 6 つとの距離をすべて求めてから最短の距離の成分を探す。最後に見つかった RGB 3 つの成分を colorcube 色の色番号を求める式にあてはめて計算する。
grayscale
1. 1 色ずつ距離を計算して最短になるものを探す。距離が 0 のものが見つかったらそこで計算終了。
2. grayscale の色空間は単調増加かつ可換操作で 1 次元へ写像可能なので quick sort の細分化の要領で距離の最小値を持つだろう幅を最後ひとつになるまで狭めていく。
3. 24 色分の距離をすべて計算してから最短の距離の色を探す。

で、すべて最後に書いたものを採用した。 grayscale に関しては 2 番目と最後で速度は変わらなかったので code の単純な後者を選択した感じ。てか対象がたった 24 個じゃ quick sort の考え方とか全然意味ねぇし。再帰関数の呼び出しや List の slice の overhead で帳消しだわ。

えーと最終的に 16 + 24 + (6 * 3) / 3 = 46 回ほど 3 次元の距離計算が走る ( colorcube に関しては 1 次元計算 6 回を 3 つなので ) ということか。まぁ 16 色や grayscale の時点で距離が 0 の色が見つかったらすぐに計算やめるようにしているので全平均ではそれ以下なんだけど。あーそれと距離計算なんだけど正確な距離が欲しいわけじゃなくて最短の距離を持つものが欲しいので単純に abs() で絶対値とって一番短いものーとした。本当にちょっとだけど abs() の方が pow() よりも速かったってのと min() が Number しか扱えない仕様だったので。

あと script の書き方として関数呼び出しの overhead がやけに高いことに気がついたので距離計算関数を手動で in-line 展開した。いやー最初半信半疑で速くなるかなと思ってやってみたんだけどここだけで 2 倍とか有意すぎる差が出て吹いた。 vim script は高度に抽象化するよりはベタに書いた方がいいみたい。まぁ何回も呼ばれるとわかってる部分に対してだけやった方が読みやすいだろうけど。あとは List の全要素に対して何かすると決まっているなら for でひとつずつ見ていくのではなく map() を使って一気に写像させた方が速いというところ。まぁこれは別に vim に限ったハナシではない、と。

で、一昨日の結果と見比べると高速感が割り増し。てか全体的には本家抜いてる。見てわかるとおり 16 色や grayscale 色にぴったり一致する色はよく使われるだろうという heuristic な手法で ( 独断と偏見ともいう ) 速く結果が返るようになっております。

:Profile color#xterm256#RGB2Nr('#000000')       " return   0, time: 0.000379 msec
:Profile color#xterm256#RGB2NrOld('#000000')    " return   0, time: 0.010981 msec
:Profile RGB2ESC('#000000')                     " return   0, time: 0.000228 msec

:Profile color#xterm256#RGB2Nr('#808080')       " return 244, time: 0.000672 msec
:Profile color#xterm256#RGB2NrOld('#808080')    " return 244, time: 0.011079 msec
:Profile RGB2ESC('#808080')                     " return   8, time: 0.007508 msec

:Profile color#xterm256#RGB2Nr('#ffff80')       " return 228, time: 0.000871 msec
:Profile color#xterm256#RGB2NrOld('#ffff80')    " return 228, time: 0.011023 msec
:Profile RGB2ESC('#ffff80')                     " return 228, time: 0.017075 msec

:Profile color#xterm256#RGB2Nr('#234567')       " return  23, time: 0.000865 msec
:Profile color#xterm256#RGB2Nr('#ffffff')       " return  15, time: 0.000387 msec