Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

diffを実装した.

ソフトウェアエンジニアなら誰しもが触ったことのあるdiffアルゴリズムUNIXのdiffコマンドであったり、SVNやGitでのバージョン管理といった、普段の開発ではかなり利用頻度の高いアルゴリズムになる。そしてこうしたアルゴリズムは実は単純そうに見えて、割と複雑な計算原理によって実現されていたりする。

  • 編集距離 : 2つの要素列の違いを数値化したもの
  • LCS(Longest Common Subsequence): 2つの要素列の最長共通部分列
  • SES(Shortest Edit Script): ある要素列を別の要素列に変換するための最短手順

diffはこれらの計算原理を用いてエディットグラフというアルゴリズムを用いて実現されている。エディットグラフはたとえばカーナビの最短経路問題などでも使われている。で、Gitで使われているらしいMyersのアルゴリズムC++で実装してみたら、これがまた思いの外ハマってしまって、簡易的なコードでも気付いたら数時間が経っていた。

UNIXコマンドを自力で実装するというのはアルゴリズムの勉強に良いと聞いてやってみたけど、かなり重かった。僕らが何気なく普段から使っているUNIXコマンドやツールには、頭の良い人間が考えたアルゴリズムというものが詰まっている。

話が飛躍するが、昨今の技術、PaaSやSaaSといったサービスであったり、フレームワークなどが様々な技術をブラックボックス化して、利用者はそれらの原理原則を知らずとも扱える、という状態が進んでいる。しかし本当にそれらを利用者として扱うのみに留まるのはいかがなものかと思う。あくまで個人的にだが、こうした隠れたアルゴリズムを学んでおくとエンジニアとしての力になる気がする。というか単純にアルゴリズムは面白くて、Wikipediaでいろんなアルゴリズムを眺めるだけでも十分時間を潰せる。次は動的計画法でやってみたい。

Remove all ads