2009年4月29日水曜日

C++: 編集距離を求めるアルゴリズム

このブログ記事をはてなブックマークに追加

編集距離(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)アルゴリズム

追記(2009/7/8): コメントで指摘を受けたので、O(ND)/O(NP)アルゴリズムについて調べたところ、挿入と削除のみを使った操作の最小数(論文中ではshortest edit "script")を求めるアルゴリズムだった。つまり、置換は削除・挿入の2手順になる。上記の動的計画法の三項演算子の部分を、(str1[i-1] == str2[j-1] ? 0 : 1)から(str1[i-1] == str2[j-1] ? 0 : 2)と変更すれば同じ操作数を求めることができる。

次に、O(ND)アルゴリズムを示す。Nは2つの要素数(m, n)の合計、Dは編集距離になる。つまり、編集距離が少なければ少ないほど高速に計算されるわけだ。原著論文は、E. W. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1, 251-266 (1986)で、日本語による解説では、後述のO(NP)アルゴリズムとともに、文書比較アルゴリズムが参考になる。以下にコードを示す。

int edit_distance_ond(const string& str1, const string& str2) { static int V[SIZE]; int x, y; int offset = str1.size(); V[offset + 1] = 0; for (int D = 0; D <= str1.size() + str2.size(); D++) { for (int k = -D; k <= D; k += 2) { if (k == -D || k != D && V[k-1+offset] < V[k+1+offset]) x = V[k+1+offset]; else x = V[k-1+offset] + 1; y = x - k; while (x < str1.size() && y < str2.size() && str1[x] == str2[y]) { x++; y++; } V[k+offset] = x; if (x >= str1.size() && y >= str2.size()) return D; } } return -1; }

O(NP)アルゴリズム

O(ND)をさらに改良したアルゴリズムが、O(NP)アルゴリズムとなる。Pは、m, n (m >= n)をそれぞれ要素数とした場合、P=(D-(m-n))/2で表される。経験的にはO(ND)の半分ほどになるらしい。原著論文は、S. Wu, U. Manber, and G. Myers. An O(NP) sequence comparison algorithm. Information Processing Letter. 35(6) 317-332 (1990)だ。以下にコードを示す。

int snake(int k, int y, const string& str1, const string& str2) { int x = y - k; while (x < str1.size() && y < str2.size() && str1[x] == str2[y]) { x++; y++; } return y; } int edit_distance_onp(const string& str1, const string& str2) { // required: s1->size() <= s2->size() const string* const s1 = str1.size() > str2.size() ? &str2 : &str1; const string* const s2 = str1.size() > str2.size() ? &str1 : &str2; static int fp[SIZE]; int x, y, k, p; int offset = s1->size() + 1; int delta = s2->size() - s1->size(); for (int i = 0; i < SIZE; i++) fp[i] = -1; for (p = 0; fp[delta + offset] != s2->size(); p++) { for(k = -p; k < delta; k++) fp[k + offset] = snake(k, max(fp[k-1+offset] + 1, fp[k+1+offset]), *s1, *s2); for(k = delta + p; k > delta; k--) fp[k + offset] = snake(k, max(fp[k-1+offset] + 1, fp[k+1+offset]), *s1, *s2); fp[delta + offset] = snake(delta, max(fp[delta-1+offset] + 1, fp[delta+1+offset]), *s1, *s2); } return delta + (p - 1) * 2; }

ビットパラレル法

最後にビットパラレル(bit-parallel)法を示す。これは動的計画法を応用しており、ビット演算を利用することで並列処理が可能となり、O(m/w n)で計算ができる。ここでwはワード長を示す。つまり、要素数mがワード長wと同じかそれ以下ならO(n)で計算ができることになり、非常に高速に処理ができる。原著論文は、G. Myers. A fast bit-vector algorithm for approximate string matching based on dynamic progamming. JACM, 46(3) 395-415, (1999)である。以下にコードを示す。

template<typename T> int edit_distance_bit(const string& str1, const string& str2) { char s1[sizeof(T) * 8] = { ' ' }; char s2[sizeof(T) * 8] = { ' ' }; char *p1, *p2; // required: str1.size() >= str2.size() if (str1.size() >= str2.size()) { p1 = s1; p2 = s2; } else { p1 = s2; p2 = s1; } copy(str1.begin(), str1.end(), p1 + 1); copy(str2.begin(), str2.end(), p2 + 1); int m = strlen(s1); int n = strlen(s2); const T ONE = 1; T Peq[256] = { 0 }; T Pv, Eq, Xv, Xh, Ph, Mh; T Mv = 0; int Score = m; for (int i = 0; i < m; i++) { Peq[s1[i]] |= ONE << i; Pv |= (ONE << i); } for (int j = 0; j < n; j++) { Eq = Peq[s2[j]]; Xv = Eq | Mv; Xh = (((Eq & Pv) + Pv) ^ Pv) | Eq; Ph = Mv | ~(Xh | Pv); Mh = Pv & Xh; if (Ph & (ONE << (m - 1))) Score++; else if (Mh & (ONE << (m - 1))) Score--; Ph <<= ONE; Pv = (Mh << ONE) | ~(Xv | Ph); Mv = Ph & Xv; } return Score; }

ついでに、C++のbitsetを利用して、何ビットでも演算できるようにしてみた。bitsetではほとんどの場合、通常のビット演算が可能なので、コードは上記のコードとあまり変わらない。ただ、足し算の演算が用意されていないので、演算子オーバーロードでoperator+()を用意した。もっとも、bitsetの利用はビット演算の高速処理が失われるのであまり意味はないかもしれない。コードは以下の通り。

template<size_t N> const bitset<N> operator+(const bitset<N>& lhs, const bitset<N>& rhs) { bitset<N> a(lhs), b(rhs), ret(lhs ^ rhs); for (b = (a & b) << 1, a = ret; b.any(); b = (a & b) << 1, a = ret) ret ^= b; return ret; } template<size_t N> int edit_distance_bitset(const string& str1, const string& str2) { char s1[N] = { ' ' }; char s2[N] = { ' ' }; char *p1, *p2; // required: str1.size() >= str2.size() if (str1.size() >= str2.size()) { p1 = s1; p2 = s2; } else { p1 = s2; p2 = s1; } copy(str1.begin(), str1.end(), p1 + 1); copy(str2.begin(), str2.end(), p2 + 1); int m = strlen(s1); int n = strlen(s2); const bitset<N> ONE(1); bitset<N> Peq[256]; bitset<N> Pv, Mv, Eq, Xv, Xh, Ph, Mh; int Score = m; for (int i = 0; i < m; i++) { Peq[s1[i]] |= ONE << i; Pv |= (ONE << i); } for (int j = 0; j < n; j++) { Eq = Peq[s2[j]]; Xv = Eq | Mv; Xh = (((Eq & Pv) + Pv) ^ Pv) | Eq; Ph = Mv | ~(Xh | Pv); Mh = Pv & Xh; if ((Ph & (ONE << (m - 1))).any()) Score++; else if ((Mh & (ONE << (m - 1))).any()) Score--; Ph <<= 1; Pv = (Mh << 1) | ~(Xv | Ph); Mv = Ph & Xv; } return Score; }

速度比較

さて、これらのアルゴリズムがどれほどの速度で、どれだけの差があるのか、実際に計測してみた。環境は、Windows XP、Intel Core2 6600@2.4GHz、RAM 2GBで、"cl edist_test.cpp /EHsc /O2"としてコンパイルした。結果は以下の通りで、ビット長以下の文字列長ではやはりビットパラレル法が最も速い。今回の結果では動的計画法の20分の1以下の時間で計算が完了した。次いでO(NP)となり、O(ND)、動的計画法の順で遅くなった。遅いと云えばbitsetを利用したビットパラレル法も遅かったがそれでも動的計画法よりは速かった。また、文字列長やその組み合わせによって速度は大きく変わるので、今回の結果はそれらの一例として考えてもらいたい。因みに、文字列はDNAの塩基配列(acgt)となっている。

文字列1: agtcaaaagtcagtcagtcagtcagtcacagtcagaaggcatccaaccga 文字列2: ccgttagtcagaaacagtcagtcagtcagtcagtccagtcttaggcccgga 動的計画法: 10万回の繰り返しで2.859秒 O(ND)アルゴリズム: 10万回の繰り返しで0.500秒 O(NP)アルゴリズム: 10万回の繰り返しで0.359秒 ビットパラレル法(unsigned long long : 64ビット): 10万回の繰り返しで0.125秒 ビットパラレル法(bitset : 60ビット): 10万回の繰り返しで1.281秒

参考までに、測定に用いたコードを示しておく。

void run(int (*func)(const string&, const string&), const string& arg1, const string& arg2, int num, const string& msg) { clock_t start, finish; start = clock(); for (int i = 0; i < num - 1; i++) (*func)(arg1, arg2); cout << msg << " : " << (*func)(arg1, arg2) << endl; finish = clock(); cout << "Time: " << (double)(finish - start) / CLOCKS_PER_SEC << "s (" << num << " times)" << endl; cout << endl; } int main() { string str1 = "agtcaaaagtcagtcagtcagtcagtcacagtcagaaggcatccaaccga"; string str2 = "ccgttagtcagaaacagtcagtcagtcagtcagtccagtcttaggcccgga"; cout << str1 << endl; cout << str2 << endl; run(edit_distance_dp, str1, str2, 100000, "dp "); run(edit_distance_ond, str1, str2, 100000, "ond "); run(edit_distance_onp, str1, str2, 100000, "onp "); run(edit_distance_bit<unsigned long long>, str1, str2, 100000, "bit "); run(edit_distance_bitset<60>, str1, str2, 100000, "bitset"); return 0; }

ところで、アルゴリズムによって編集距離が微妙に違ってくるが、これは仕方がないことなのかなぁ。
上でも書いたが、一操作を「挿入、削除、置換」とするか(動的計画法、ビットパラレル法)、「挿入、削除」にするか(O(ND)/O(NP)アルゴリズム)の違いだった。いくつかのバグと一緒に修正しておいた。

続きを読む...

2009年4月22日水曜日

C++の名前空間は完全に独立というわけではない

このブログ記事をはてなブックマークに追加

名前の自動照合規則によって指定していない名前空間の関数が呼ばれることがある。例えば、下に示すコードでは、赤字で示した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++プログラマであるならば知っておかなくてはならないことが書かれている良書だと思う。

続きを読む...

2009年4月10日金曜日

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 < 10; i++)のように、for(の間にスペースを入れる。関数ではfunc(int n)のように関数と(の間は詰めて書く。式2つを一行で書く際にはa = 1; b = 2;のように;bの間のスペースは2つとする。ほかにもいろいろと細かいことを自分なりに決めているが、このぐらいにしておく。

ああ、でも、ポインタの宣言や仮引数は未だに迷うなぁ。Cならint *p;だし、C++ならint* p;だ。上記のGoogleのスタイルガイドではどちらでも良いことになっている。ただし、同じファイル内では統一するべき。

以下はコード例。

void func(int a[], int n) { for (int i = 0; i < n; i++) { a[i] = i * i; } } int main() { int a[10]; func(a, sizeof(a) / sizeof(*a)); return 0; }

念のために断っておくけど、上記のコーディングスタイル以外を認めなかったり、駄目だと考えているわけではない。これはあくまで自分の個人的なコーディングスタイルの話。

続きを読む...

2009年4月5日日曜日

Python: 世界の標準時間を相互に変換する

このブログ記事をはてなブックマークに追加

インターネットにより世界はとても身近なものになった。それはとても素晴らしいことなのだが、ある地域の現地時間が日本で何時なのかがすぐに分からず("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 # -*- coding: utf-8 -*- """世界の標準時間を相互に変換""" import sys, os, datetime TIMEZONE_TABLE = { "NZDT" : ["+13:00", u"ニュージーランド夏時間"], "IDLE": ["+12:00", u"国際日付変更線の東側"], "NZST": ["+12:00", u"ニュージーランド標準時間"], "NZT": ["+12:00", u"ニュージーランド時間"], "AESST": ["+11:00", u"オーストラリア東部標準夏時間"], "ACSST": ["+10:30", u"オーストラリア中部標準夏時間"], "CADT": ["+10:30", u"オーストラリア中部夏時間"], "SADT": ["+10:30", u"オーストラリア南部夏時間"], "AEST": ["+10:00", u"オーストラリア東部標準時間"], "EAST": ["+10:00", u"オーストラリア東部標準時間"], "GST": ["+10:00", u"グアム標準時間"], "LIGT": ["+10:00", u"オーストラリア、メルボルン"], "SAST": ["+09:30", u"オーストラリア南部標準時間"], "CAST": ["+09:30", u"オーストラリア中部標準時間"], "AWSST": ["+09:00", u"オーストラリア西部標準夏時間"], "JST": ["+09:00", u"日本標準時間"], "KST": ["+09:00", u"韓国標準時間"], "MHT": ["+09:00", u"マーシャル群島、クワジュリン時間"], "WDT": ["+09:00", u"オーストラリア西部夏時間"], "MT": ["+08:30", u"モルッカ諸島時間"], "AWST": ["+08:00", u"オーストラリア西部標準時間"], "CCT": ["+08:00", u"中国湾岸時間"], "WADT": ["+08:00", u"オーストラリア西部夏時間"], "WST": ["+08:00", u"オーストラリア西部標準時間"], "JT": ["+07:30", u"ジャワ島時間"], "ALMST": ["+07:00", u"アルマトイ夏時間"], "WAST": ["+07:00", u"オーストラリア西部標準時間"], "CXT": ["+07:00", u"クリスマス島時間"], "MMT": ["+06:30", u"ミャンマー時間"], "ALMT": ["+06:00", u"アルマトイ時間"], "MAWT": ["+06:00", u"南極大陸時間"], "IOT": ["+05:00", u"インドチャゴス時間"], "MVT": ["+05:00", u"モルディブ島時間"], "TFT": ["+05:00", u"ケルゲレン諸島時間"], "AFT": ["+04:30", u"アフガニスタン時間"], "EAST": ["+04:00", u"マダガスカル、アンタナナリボ"], "MUT": ["+04:00", u"モーリシャス島時間"], "RET": ["+04:00", u"レユニオン島時間"], "SCT": ["+04:00", u"マーヘ島時間"], "IRT": ["+03:30", u"イラン時間"], "IT": ["+03:30", u"イラン時間"], "EAT": ["+03:00", u"アンタナナリボ、コモロ時間"], "BT": ["+03:00", u"バクダッド時間"], "EETDST": ["+03:00", u"東ヨーロッパ夏時間"], "EEST": ["+03:00", u"東ヨーロッパ夏時間"], "HMT": ["+03:00", u"ギリシャ、ヘラ地中海時間"], "BDST": ["+02:00", u"英国二重夏時間"], "CEST": ["+02:00", u"中央ヨーロッパ夏時間"], "CETDST": ["+02:00", u"中央ヨーロッパ夏時間"], "EET": ["+02:00", u"東ヨーロッパ時間"], "FWT": ["+02:00", u"フランス冬時間"], "IST": ["+02:00", u"イスラエル標準時間"], "MEST": ["+02:00", u"中央ヨーロッパ夏時間"], "METDST": ["+02:00", u"中央ヨーロッパ夏時間"], "SST": ["+02:00", u"スウェーデン夏時間"], "BST": ["+01:00", u"英国夏時間"], "CET": ["+01:00", u"中央ヨーロッパ時間"], "DNT": ["+01:00", u"デンマーク標準時間"], "FST": ["+01:00", u"フランス夏時間"], "MET": ["+01:00", u"中央ヨーロッパ時間"], "MEWT": ["+01:00", u"中央ヨーロッパ冬時間"], "MEZ": ["+01:00", u"中央ヨーロッパ地域時間"], "NOR": ["+01:00", u"ノルウェー標準時間"], "SET": ["+01:00", u"セイシェル時間"], "SWT": ["+01:00", u"スウェーデン冬時間"], "WETDST": ["+01:00", u"西ヨーロッパ夏時間"], "WEST": ["+01:00", u"西ヨーロッパ夏時間"], "GMT": ["00:00", u"グリニッジ標準時間"], "UT": ["00:00", u"万国共通時間"], "UTC": ["00:00", u"協定世界時間"], "Z": ["00:00", u"協定世界時間"], "ZULU": ["00:00", u"協定世界時間"], "WET": ["00:00", u"西ヨーロッパ時間"], "WAT": ["-01:00", u"西アフリカ時間"], "FNST": ["-01:00", u"フェルナンド・デ・ノローニャ夏時間"], "FNT": ["-02:00", u"フェルナンド・デ・ノローニャ時間"], "BRST": ["-02:00", u"ブラジニア夏時間"], "NDT": ["-02:30", u"ニューファンドランド夏時間"], "ADT": ["-03:00", u"大西洋夏時間"], "BRT": ["-03:00", u"ブラジリア時間"], "NFT": ["-03:30", u"ニューファンドランド標準時間"], "NST": ["-03:30", u"ニューファンドランド標準時間"], "AST": ["-04:00", u"大西洋標準時間"], "ACST": ["-04:00", u"大西洋/ポルトアクリ夏時間"], "EDT": ["-04:00", u"米国東部夏時間"], "ACT": ["-05:00", u"大西洋/ポルトアクリ標準時間"], "CDT": ["-05:00", u"米国中部夏時間"], "EST": ["-05:00", u"米国東部標準時間"], "CST": ["-06:00", u"米国中部標準時間"], "MDT": ["-06:00", u"米国山岳部夏時間"], "MST": ["-07:00", u"米国山岳部標準時間"], "PDT": ["-07:00", u"米国太平洋夏時間"], "AKDT": ["-08:00", u"アラスカ夏時間"], "PST": ["-08:00", u"米国太平洋標準時間"], "YDT": ["-08:00", u"ユーコン夏時間"], "AKST": ["-09:00", u"アラスカ標準時間"], "HDT": ["-09:00", u"ハワイ/アラスカ夏時間"], "YST": ["-09:00", u"ユーコン標準時間"], "MART": ["-09:30", u"マルケサス諸島時間"], "AHST": ["-10:00", u"ハワイ/アラスカ標準時間"], "HST": ["-10:00", u"ハワイ標準時間"], "CAT": ["-10:00", u"アラスカ中央時間"], "NT": ["-11:00", u"ノーム時間"], "IDLW": ["-12:00", u"国際日付変更線の西側"]} def standard_time(DATE, TIME, fZone, tZone): if fZone not in TIMEZONE_TABLE.keys(): print >>sys.stderr, u"変換元の標準時間略名が認識できません:", fZone sys.exit() if tZone not in TIMEZONE_TABLE.keys(): print >>sys.stderr, u"変換先の標準時間略名が認識できません:", tZone sys.exit() h, m = map(int, TIMEZONE_TABLE[fZone][0].split(":")) m *= -1 if TIMEZONE_TABLE[fZone][0].strip()[0] == "-" else 1 fST = datetime.timedelta(hours=h, minutes=m) h, m = map(int, TIMEZONE_TABLE[tZone][0].split(":")) m *= -1 if TIMEZONE_TABLE[fZone][0].strip()[0] == "-" else 1 tST = datetime.timedelta(hours=h, minutes=m) try: d = DATE.split("/") if len(d) == 2: Y = datetime.date.today().year M, D = map(int, d) elif len(d) == 3: Y, M, D = map(int, d) else: raise t = TIME.split(":") if len(t) == 2: h, m = map(int, t) s = 0 elif len(t) == 3: h, m, s = map(int, t) else: raise except: print >>sys.stderr, u"日時のフォーマットが間違っています:", DATE, TIME sys.exit() try: print u"%s(%s)" % (TIMEZONE_TABLE[fZone][1], fZone) print datetime.datetime(Y, M, D, hour=h, minute=m, second=s) print print u"%s(%s)" % (TIMEZONE_TABLE[tZone][1], tZone) print datetime.datetime(Y, M, D, hour=h, minute=m, second=s) + (tST - fST) except: print >>sys.stderr, u"日時に誤りがあります: %s %s %s" % (DATE, TIME, sys.exc_info()[1]) sys.exit() def main(args): if len(args) < 4: print >>sys.stderr, u"Usage: %s 日付 時刻 変換元の標準時間略名 [変換先の標準時間略名=JST]" % os.path.basename(args[0]) print >>sys.stderr, u" 日付: [年/]月/日 (例: 2009/4/3, 11/19)" print >>sys.stderr, u" 時刻: 時:分[:秒] (例: 19:50:23, 9:20)" print >>sys.stderr print >>sys.stderr, u" 使用例: " print >>sys.stderr, u" 米国東部夏時間(EDT)4月30日の午後6時を日本標準時(JST)に変換する場合" print >>sys.stderr, u" %s 4/30 18:00 EDT" % os.path.basename(args[0]) print >>sys.stderr print >>sys.stderr, u" 米国東部夏時間(EDT)4月30日の午後6時を米国太平洋標準時間(PST)に変換する場合" print >>sys.stderr, u" %s 4/30 18:00 EDT PST" % os.path.basename(args[0]) print >>sys.stderr print >>sys.stderr, u" 日本標準時(JST)4月30日の午後6時を米国東部夏時間(EDT)に変換する場合" print >>sys.stderr, u" %s 4/30 18:00 JST EDT" % os.path.basename(args[0]) sys.exit() DATE = args[1].replace("-", "/").replace(".", "/") TIME = args[2] fZone = args[3].upper() if len(args) == 4: tZone = "JST" else: tZone = args[4].upper() standard_time(DATE, TIME, fZone, tZone) if __name__ == "__main__": main(sys.argv)

追記(2009/4/8):

TIMEZONE_TABLEおよび時差計算の修正。

続きを読む...