diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
プログラミング万能練習法
暇な人はやってみるといいプログラミングの万能練習法 は良いトレーニングになる。 プログラムを自ら書きたいと思う人って、与えられたメニューをこなすだけの人間ではないと思うけどハッカーを目指している人には UNIX の勉強にもなるんじゃないだろうか。というわけで、実際の練習メニューは以下の通り。 プログラミング言語を選択する 書いてみようと思う POSIX のコマンド を決める man をはじめとするマニュアルを読んでコマンドの仕様を理解する 設計する(初回のコーディングと同時進行はやめたほうがいいかも) コーディング テストする。設計とコーディングの反復。 終了 C 言語で書いたならテストのあとにオリジナルのソースを読んで答え合わせするのですが、必ずしもオリジナルのコードが正解とは言い切れない。 自分が書いたプログラムが仕様どおりに動いているならアルゴリズムの違いなどは気にしなくていいと思う
いまさらgrepが10倍高速化したのはなぜか – はむかず！
最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事：grepコマンド最新版、”-i”で10倍の高速化 本家のリリースノート：grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？ そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
