良いもの。悪いもの。

編集距離(edit distance)とは二つの文字列がどの程度異なっているかを示す数値であり、 レーベンシュタイン距離(Levenshtein distance) を指すことが多い。文字の挿入、削除、置換それぞれを一つの操作として必要な操作の最小数を求めるものだ。例えば、kittenとsittingの編集距離を求める場合、下記のように3回の操作でkittenをsittingに変更できるので編集距離は3となる。 1. sitten (k を s に置換） 2. sittin (e を i に置換） 3. sitting (g を挿入) そこで今回は編集距離を求める複数のアルゴリズムについてC++で実装してみた。 動的計画法 編集距離を求めるもっとも一般的なアルゴリズムは、動的計画法(dynamic programming)だろう。計算時間はO(mn)であり、手軽だ。C++で書いたコードを下に示す。尚、コード中に出てくる定数SIZEは扱う文字列にあわせて適当に決めておく。動的にメモリを確保することもできるが処理が遅くなるので、あらかじめ決め打ちしておく方が効率がよい。 int edit_distance_dp(const string& str1, const string& str2) { static int d[SIZE][SIZE]; for (int i = 0; i < str1.size() + 1; i++) d[i][0] = i; for (int i = 0; i < str2.size() + 1; i++) d[0][i] = i; for (int i = 1; i < str1.size() + 1; i++) for (int j = 1; j < str2.size() + 1; j++) d[i][j] = min(min(d[i-1][j], d[i][j-1]) + 1, d[i-1][j-1] + (str1[i-1] == str2[j-1] ? 0 : 1)); return d[str1.size()][str2.size()]; } O(ND)アルゴリズム 追記 (...

名前の自動照合規則 によって指定していない名前空間の関数が呼ばれることがある。例えば、下に示すコードでは、赤字で示したfunc(x)の呼び出し時に、コンパイラはA::func()とB::func()のどちらを呼べば良いか分からずエラーになる。目的の関数を呼び出す場合、明示的にA::func(x)やB::func(x)のように書く必要がある。この問題は、Koenigの自動照合(Koenig lookup)とかADL(argument dependent lookup, argument dependent name lookup; 実引数依存の名前探索)として知られている。 namespace A { struct X; void func(X); }; namespace B { void func(A::X x) { func(x); // どの関数が呼ばれるのか? } }; 何故、同じ名前空間のB::func()だけが呼ばれずに異なる名前空間のA::func()も参照されるのかって? もし、ここで外部の名前空間が呼ばれなかったら、名前空間stdを持つ標準ライブラリを使った次のコードは通らない。 std::string str("lookup"); std::cout << "Koenig " << str << std::endl; 以下のように「正しく」書く必要がある。 std::string str("lookup"); std::operator<<(std::operator<<(std::cout, "Koenig "), str).operator<<(std::endl); 誰もこんなことは望まないと思うので、名前の自動照合がある訳だ。より詳しい内容を知りたければExceptional C++の第5章を読もう。因みに、第5章以外でもC++プログラマであるならば知っておかなくてはならないことが書かれている良書だと思う。

多くのプログラマ同様、C++を書くときには個人的にいくつかのこだわりを持っている。まず、main関数のreturn文は明示的に書くことにしている。規格ではmain関数のreturnを省略した場合、 return 0; が書かれたものとして動作するが、C89では戻り値は不定であり(C99では戻り値はC++と同じく0)、戻り値を0としたい場合は、必ず return 0; としなければならない。CとC++の統一性が崩れることが嫌なこともあり、いつも return 0; を入れているのだ。あと、コードの雛形を書くときに、mainの中身が空だと何となく落ちつかないってのもある。 また、戻り値を必要としない前置および後置のインクリメント/デクリメント(i++, ++i, i--, --i)については、intやdoubleなどのスカラー値では後置、STLのイテレータやユーザ定義型などのような非スカラー値の場合は前置にしている。一時オブジェクトを必要とする非スカラー値では効率に大きく影響するので、前置を使うわけだ。因みに、スカラー値の場合、戻り値を必要としない前置と後置の演算子でまったく同じ動作(副作用がない)であることが規格上決められているので、効率は全く変わらない。だったら、前置で統一すれば良いと思われるかもしれないが、Cでは伝統的にfor文などで後置が使われることが多く、自分もCでは後置を使っていたので、それを踏襲している。スカラー値か非スカラー値か一目でわかるのも良い。因みにGoogleが採用している C++スタイルガイド でも非スカラー値は前置でなければならないが、スカラー値はどちらでも良いことになっている。 あとは、括弧()の使い方だが、forのような文では、 for (int i = 0; i のように、 for と ( の間にスペースを入れる。関数では func(int n) のように関数と ( の間は詰めて書く。式2つを一行で書く際には a = 1; b = 2; のように ; と b の間のスペースは2つとする。ほかにもいろいろと細かいことを自分なりに決めているが、このぐらいにしておく。 ああ、でも、ポインタの宣言や仮引数は未だに迷うなぁ。Cなら int *p; だし、C++なら int* p; だ。上記のGoogleのスタイルガイドではどちらでも...

インターネットにより世界はとても身近なものになった。それはとても素晴らしいことなのだが、ある地域の現地時間が日本で何時なのかがすぐに分からず("4.30.2009 18:00 EET"なんて書かれていても分からないよね?)、いちいちネットで調べる羽目になることが度々ある。それが非常に煩わしかったので、Pythonを使ってコマンドラインで時間の変換を行えるようにしてみた。 標準時間の略名についてはネットで適当に検索してきてそれを利用している。プログラムのファイル名は一応standard_time.pyとしているが長すぎると思うのならst.pyなど好きに変えて使って欲しい。 使い方は以下の通り。変換先の標準時間が省略された場合はデフォルトで日本標準時(JST)となる。日付の指定は「年/月/日」とし、時刻は「時:分:秒」とする。年と秒は省略できる。 standard_time.py 日付 時刻 変換元の標準時間略名 [変換先の標準時間略名=JST] 例えば、米国東部夏時間(EDT)4月30日の午後6時を日本標準時(JST)に変換する場合は、 standard_time.py 4/30 18:00 EDT とすれば良い。出力結果は以下のようになる。 米国東部夏時間(EDT) 2009-04-30 18:00:00 日本標準時間(JST) 2009-05-01 07:00:00 また、米国東部夏時間(EDT)4月30日の午後6時を米国山岳部標準時間(MST)に変換する場合は、 standard_time.py 4/30 18:00 EDT MST とする。出力結果は以下の通り。 米国東部夏時間(EDT) 2009-04-30 18:00:00 米国山岳部標準時間(MST) 2009-04-30 15:00:00 以下にソースコードを示す。簡単なコードなので理解は容易だと思う。任意のフォーマットからの変換などの機能を組み込んでみるのも面白いかもしれない。もっとも、本格的にこの手のことをするなら pytz を利用すべきかなぁ。でも、夏時間の判定をするわけではないし、それに標準時間の略号との対応が面倒そうなんだよね。 standard_time.py #!/usr/bin/env python # -*...