Posted at

Vimで二分探索する

More than 1 year has passed since last update.


注意

実用性は無いです。


前提

vim -u NONE -i NONE -N -c 'put=range(1000)' -c '$ delete' -c 'set cul'


  • 初期状態ではバッファの各行が 0, 1, 2, ... 999 で埋まっている

  • 探索する値は何でもいいけど今回は42ということにしておく


手順

:let s=42^Mqqgs50%zzgsy$@=@0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"^Mq@q



  • ^M はcarriage returnに置き換えること


結果

t.gif


解説


Step 1: 人間に読める形に分解する

:let s=42^Mqqgs50%zzgsy$@=@0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"^Mq@q



  1. :let s=42^M


    • 探す値を変数 s に代入




  2. qqgs50%zzgsy$@=@0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"^Mq


    • 何か凄そうだけど……全体は qq ... q なのでキーボードマクロの記録をしてるだけ




  3. @q



    • ... の操作をもう一度やる




Step 2: 記録された ... の正体

gs50%zzgsy$@=@0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"^M



  1. gs


    • 1秒sleep

    • 動きを人間の目でも認識できるよう仕込んでる(省略可)




  2. 50%


    • バッファ全体の大体50%くらいの位置に移動




  3. zz


    • カーソル行が画面の中央に表示されるようビューを調整

    • 動きを人間の目でも認識できるよう仕込んでる(省略可)




  4. gs


    • 1秒sleep(省略化)




  5. y$


    • カーソル行の内容をコピー




  6. @=@0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"^M


    • 何か凄い事をやってる




Step 3: 何か凄い事の正体

@=@0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"^M



  1. @=


    • レジスタ = の内容をキーボードマクロとして実行する

    • 実行する内容は「この後に書いた式の評価結果」なので……




  2. @0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"


    • これが何か凄い式




  3. ^M


    • 式の終わりを示すcarriage return




Step 4: 何か凄い式の正体

@0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"



  1. @0==''


    • 最後にコピーした内容(=カーソル行の内容)が空文字列か判定する




  2.  ?"SNot found\<Esc>"


    • 空文字列なら全要素探索し終えたので終了




  3.  :@0<s


    • カーソル行の内容が探索対象の値より小さいか判定する




  4.   ?'dgg@q'


    • 小さいならバッファの前半を消して二分探索を再実行




  5.   :@0>s


    • カーソル行の内容が探索対象の値より大きいか判定する




  6.    ?'dG@q'


    • 大きいならバッファの後半を消して二分探索を再実行




  7.    :"IFound: \<Esc>"


    • ここまで来たら探索対象の値が見つかったので終了




ポイント

qqgs50%zzgsy$@=@0==''?"SNot found\<Esc>":@0<s?'dgg@q':@0>s?'dG@q':"IFound: \<Esc>"^Mq@q

↓ (これの骨格だけを抽出すると)

qq...@=...''?'...@q':'...'^Mq@q

↓ (より本質的なところを抽出すると)

qq...@q...q@q


  • 1個目の @q: キーボードマクロ q の記録中なのに @q で実行してる


    • この段階ではレジスタ q の内容は空なので、 @q しても何も起きない



  • 2個目の @q: 先程レジスタ q に記録された内容が実行される


    • この段階ではレジスタ q の内容は沢山あるので、 @q の実行で更に @q が再帰的に実行される