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上でのC++ソフトウェア設計の定石 (1) - memologue
UNIXは、Windowsなどの“開発者に優しい”OSと比較すると、シグナルやスレッドの利用に関して制限事項が多いですが、それを知らずにアーキテクチャ設計および実装を行ってしまうケースが散見されます。これは、再現困難なバグの温床となるでしょう。 そこで、罠に嵌らないための「鉄則」を何回かに分けて書いてみようと思います。 鉄則1: シグナルの送受に依存しない設計にしよう 他プロセスおよび自プロセスに対し、非同期シグナルを配送して処理の流れを変える設計はやめよう 非同期シグナルとは、SIGUSR1・SIGUSR2・SIGINT・SIGTERM などの、killシステムコールによって生成・配送されるシグナルのこと 単に無視(SIG_IGN)するのは問題なし スレッドとシグナルの併用もやめよう 動作の予測が困難、デバッグが困難 説明： 同期シグナルとは、SIGSEGV,SIGBUS,SIGPIPE
memologue - UNIX上でのC++ソフトウェア設計の定石 (2)
鉄則2: シグナルハンドラで行ってよい処理を知ろう sigaction関数で登録したシグナルハンドラで行ってよい処理は非常に限定されている 次の３つの処理だけが許されている 自動変数の操作 “volatile sig_atomic_t” 型の大域変数の操作 「非同期シグナルセーフ」関数の呼び出し これ以外の処理を記述しないこと！ 説明： シグナル受信時に何らかの処理を行うためには、シグナルハンドラと呼ばれる関数を用意し、それをsigaction関数でシグナル名と紐付けておけばOKです。しかし、シグナルハンドラ内で行ってよい処理は、上記の通り非常に限定されています。これを把握しないまま奔放なコードを書くと次のような現象が起き得ます： 問題1: プログラムがデッドロックする危険がある タイミングに依存する、再現困難なバグの原因となる デッドロックの発生が典型例だが、それ以外にも関数の戻り値不正
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
