Vim script でレーベンシュタイン距離を計算する
Vim script にビットシフト演算子が導入されたそうです。
Vim script にビットシフト演算子が入りました。https://t.co/Rb5x9hNFqX
— mattn (@mattn_jp) 2022年5月22日
というわけで、とりあえずレーベンシュタイン距離を計算してみました。 レーベンシュタイン距離というのは編集距離と呼ばれる文字列同士の類似度の尺度の一つですが、距離というだけあって小さいほど似ている文字列ということになります。
詳しくは wikipedia とかみてください。
基本的には動的計画法 (Dynamic programming) を用いて計算するのが直感的にはわかりやすいのですが、その変形で bit-parallel アルゴリズムと呼ばれる方法もあります。 これは動的計画法で埋めていくマトリックスの列の計算に相当する部分を、ビット演算で置き換えてしまうという方法です。 はい、冒頭のビットシフトはここに繋がります。 Bit-parallel法の計算にはちょっとだけビット左シフトが使われるのです。 Bit-parallel法を使うと、いくらかの制限は付きますが動的計画法に比べて高速に計算することができます。
というわけで Vim script で実装して比較してみました。
(6/18 Vim9 script の結果を追記)
| Dynamic programming | Bit-parallel | Bit-parallel (obsolete) | Dynamic programming (vim9) | Bit-parallel (vim9) | |
|---|---|---|---|---|---|
| min. | 0.045096 | 0.002326 | 0.002409 | 0.003242 | 0.000235 |
| max. | 0.053966 | 0.002536 | 0.002647 | 0.003401 | 0.000254 |
| mean | 0.046023 | 0.002372 | 0.002452 | 0.003330 | 0.000245 |
| median | 0.045995 (1x) | 0.002372 (19.4x) | 0.002451 (18.8x) | 0.003334 (13.8x) | 0.000245 (187.7x) |
ランダムな64文字の文字列同士を1000回計算して、一回の計算にかかった時間の最短(min.)、最長(max.)、平均値(mean)、中央値(median)を表にしました。 単位は秒です。 中央値の括弧のなかみは動的計画法より何倍高速かを表示しています。 Bit-parallel (obsolete) はビット左シフト演算 (n << m) を積と累乗 (n * 2m) で置き換えた場合の結果です。
まあ動的計画法よりは早いですけどシフト演算ない場合との比較は残念な感じですね…。 そもそも、bit-parallelではシフト演算が大体 n << 1 みたいなのばっかりなのでありがたみが薄かった…。 そして Vim9 script 速い...!
一応、成果物です。
シフト演算子とは全然関係ない話なんですけど、Vim script の min(), max() 関数が浮動小数点数に対応してないのさっきまで知らなかった…
