12.31.2011

Generating integer partitions with C++

C++: 自然数の分割を列挙する

正の整数 n の分割(integer partition)とは、与えられた正整数 n を正整数の和として表す方法をいう。

例えば、「6」 はこのように11通りの異なる方法で分割できる。

 6  5+1  4+2  4+1+1  3+3  3+2+1  3+1+1+1  2+2+2  2+2+1+1  2+1+1+1+1  1+1+1+1+1+1

この成分(part)の組み合わせを std::vector<int> として順次生成するクラスを作りたい。
以下、この関数を P(n) と呼ぶ。

1. 再帰を利用したアルゴリズム(Python)

Python のジェネレータ機能を使ったコードが、こちらに投稿されている。
http://code.activestate.com/recipes/218332-generator-for-integer-partitions/

処理時間計測用のコードと併せて記載する。

def P(n):
  # base case of recursion: zero is the sum of the empty list
  if n == 0:
    yield []
    return

  # modify partitions of n-1 to form partitions of n
  for p in P(n - 1):
    p.append(1)
    yield p
    p.pop()
    if p and (len(p) < 2 or p[-2] > p[-1]):
      p[-1] += 1
      yield p

def main():
  import timeit
  for n in (15, 30, 45, 60, 75, 90):
    code = 'for _ in P(%d): pass' % n
    print 'n=%d  elapsed=%f' % (
        cnt,
        timeit.Timer(code, 'from __main__ import P').timeit(1))

if __name__ == '__main__':
  main()

手元のPC(Intel Core2Duo E4600 @ 2.40GHz)での実行結果は以下のとおり。(処理時間の単位は秒)

n=15  elapsed=0.000423
n=30  elapsed=0.015092
n=45  elapsed=0.290839
n=60  elapsed=3.473330
n=75  elapsed=31.071480
n=90  elapsed=236.823416

このコードのアルゴリズムは以下のようになる。

①P(n) の計算にあたり、P(n-1) を列挙する。 ※P(0) は空のリストを返す。

②P(n-1) の各出力に対して、末尾に新規の成分「1」を追加したリストを出力する。

③P(n-1) の各出力を k個の成分を持つリスト x1,x2, … ,xk とした場合、
 成分の個数が1個(k=1)であれば、その唯一の成分を インクリメントする。(x1 ← x1 + 1)
 末尾の2成分(xk-1, xk)について、xk-1 > xk が成立する場合、末尾の成分をインクリメントする。(xk ← xk + 1)
 インクリメントしたリストを出力する。
 (言い換えれば、末尾の成分をインクリメントしても要素の降順が守られる場合にのみインクリメント実行)

この結果出力される各成分は降順にソートされている。また、出力結果は辞書順となる。
P(0)~P(5) の処理の様子はこのようになる。

image
緑色の箇所はP(n-1)に対して新規の成分「1」を追加したこと、ピンク色の箇所は既存の成分をインクリメントしたことを表している。

2. 再帰を利用しないアルゴリズム(C++)

以下の文献を参考に、C++で処理を実装してみる。

Antoine Zoghbiu and Ivan Stojmenovic. Fast Algorithms for Generating Integer Partitions. Intern. J. Computer Math., 70, 319-332 (1998) (PDF)
http://www.site.uottawa.ca/~ivan/F49-int-part.pdf

出力は辞書の逆順とするほうがコストが小さい。そのアルゴリズムはこのような感じだ。
尚、この場合も1つの出力における各成分は降順にソートされるようにする。

①n = 0 の場合は空のリストを出力して終了。

②成分が1個だけのリスト {n} を作成し、それを出力する。

③2以上の成分の数を h とおき、1 を代入する。(h ← 1)

# 以下、④~⑦を繰り返す

④最初の成分が1 (x1 = 1) ならば終了。

⑤2以上の成分のうち最も右側にあるもの(xh)をデクリメントし、その値を r とする。(r ← xh-1; xh ← r)

⑥xh より右側にあった成分を全て結合し、{r, r, … , d}  (0 < d ≦ r) という形に再構成する。
 xh より右側の成分は、定義より全て 1 であるから、現在のリストの個数を|{x}|とすると
 |{x}| h + 1 = c × r + d  (0 < d ≦ r)
 という変換を行えばよいことが分かる。

⑦r = 1 の場合は h をデクリメントする。(h ← h - 1)
 r > 1 かつ d = 1 の場合は h に c を加算。(h ← h + c)
 r > 1 かつ d ≧ 1 の場合は h に c+1 を加算する。(h ← h + c + 1)

# ④へ戻る

P(6) の処理の様子を以下に示す。

  ・リスト {n} を作成
・h ← 1
  ・xh = x1 をデクリメント
・1 を 5 単位で再構成: 1 = 0 × 5 + 1
・2 以上の成分の個数(h)は変わらず
  ・xh = x1 をデクリメント
・2 を 4 単位で再構成: 2 = 0 × 4 + 2
・2 以上の成分ができたので h を増加
 

・xh = x2 をデクリメント
・1 を 1以下に再構成
・2 以上の成分が減ったので h を減少

 

・xh = x1 をデクリメント
・3 を 3 単位で再構成: 3 = 1 × 3 + 0
・2 以上の成分ができたので h を増加

 

・xh = x2 をデクリメント
・1 を 2 単位で再構成: 1 = 0 × 2 + 1

 

・xh = x2 をデクリメント
・2 を 1以下に再構成
・2 以上の成分が減ったので h を減少

 

・xh = x1 をデクリメント
・4 を 2 単位で再構成: 4 = 2 × 2 + 0
・2 以上の成分が2つできたので h を2つ増加

 

・xh = x3 をデクリメント
・1 を 1以下に再構成
・2 以上の成分が減ったので h を減少

 

・xh = x2 をデクリメント
・3 を 1以下に再構成
・2 以上の成分が減ったので h を減少

 

・xh = x1 をデクリメント
・5 を 1以下に再構成
・2 以上の成分が減ったので h を減少

・これで、最初の成分(x1)が 1 になったので終了

黄色の箇所は 2以上の数値(=h としてカウントされるもの)を、青色の箇所はデクリメントした結果1となったこと(=hのデクリメントを伴ったこと)を表している。

コーディングにあたっては、簡単のため h を 1-indexed から 0-indexed へ変換する。
xh = 2 のときの再配分処理はリストの末尾に 1 を追加するだけでよい。
また、出力したリストの個数を count 変数として保持することにした。

今回もやはり時間計測用のコードと一緒に掲載する。

#include <vector>
#include <ctime>
#include <cstdio>

// Generator for integer partition.
class Partition {
 public:
  int count;

  Partition(int n) {
    x_ = std::vector<int>(std::min(1, n), n);
    h_ = n > 1 ? 0 : -1;
    count = 0;
  }

  std::vector<int> &next() {
    if (x_.empty()) return x_;
    if (count > 0) {
      if (h_ < 0) {
        x_.clear();
        return x_;
      }
      if (x_[h_] == 2) {
        --x_[h_--];
        x_.push_back(1);
      }
      else {
        int r = --x_[h_];
        int t = x_.size() - h_;
        while (t >= r) {
          x_[++h_] = r;
          t -= r;
        }
        if (t == 0) {
          x_.resize(h_ + 1);
        }
        else {
          x_.resize(h_ + 2, 1);
          if (t > 1) x_[++h_] = t;
        }
      }
    }
    ++count;
    return x_;
  }

 private:
  std::vector<int> x_;
  int h_;
};

int main() {
  // Print each P(6).
  Partition p(6);
  std::vector<int> v;
  while ((v = p.next()).size()) {
    printf("%2d: [", p.count);
    for (int i = 0; i < (int)v.size(); ++i) {
      printf("%s%d", i == 0 ? "" : ", ", v[i]);
    }
    printf("]\n");
  }

  // Measuring time elapsed.
  int n[] = {15, 30, 45, 60, 75, 90};
  for (int i = 0; i < static_cast<int>(sizeof(n) / sizeof(n[0])); ++i) {
    clock_t t = clock();
    Partition p(n[i]);
    while (p.next().size()) {}
    clock_t s = clock();

    printf("n=%d  elapsed=%.6f  count=%d\n", n[i],
        static_cast<double>(s - t) / CLOCKS_PER_SEC, p.count);
  }
  return 0;
}

実行結果は以下のとおり。(処理時間の単位は秒)

 1: [6]
 2: [5, 1]
 3: [4, 2]
 4: [4, 1, 1]
 5: [3, 3]
 6: [3, 2, 1]
 7: [3, 1, 1, 1]
 8: [2, 2, 2]
 9: [2, 2, 1, 1]
10: [2, 1, 1, 1, 1]
11: [1, 1, 1, 1, 1, 1]
n=15  elapsed=0.000000  count=176
n=30  elapsed=0.000000  count=5604
n=45  elapsed=0.010000  count=89134
n=60  elapsed=0.105000  count=966467
n=75  elapsed=0.818000  count=8118264
n=90  elapsed=5.612000  count=56634173

参考:
http://handasse.blogspot.com/2010/01/blog-post.html

Wikipedia
http://en.wikipedia.org/wiki/Partition_%28number_theory%29
http://ja.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E6%95%B0%E3%81%AE%E5%88%86%E5%89%B2

12.30.2011

How to get current date in Perl

Perl: 現在日付の取得

localtime 関数の戻り値をスライシングすれば、日付だけを取得することができる。
例えば、今日の午前 0:00 を Unix Time で表現する方法は以下のとおり。

use POSIX qw( mktime strftime );
my $time = mktime(0, 0, 0, (localtime)[3..5]);
print strftime('%Y-%m-%d %H:%M:%S', localtime($time));

参考:
http://ebitem.net/program-blog/archives/96

12.27.2011

Etymology of the 'glob'

グロブの語源について

ファイルパスのワイルドカードなどを展開することをグロブとか、グロビングとか言うが
これはどうやらUNIX黎明期の「glob」コマンドが由来らしい。

global を略した言葉のようだ。

http://en.wikipedia.org/wiki/Glob_%28programming%29
http://cm.bell-labs.com/cm/cs/who/dmr/man71.pdf

12.23.2011

Expanding all UNIX environment variables in Perl

Perl: UNIX環境変数を全て展開

正規表現とENVハッシュの組み合わせで実現できる。

sub expand {
    my ($text) = @_;
    $text =~ s{ \$ {? (\w+) }? }
              { exists $ENV{$1} ? $ENV{$1} : $& }gexms;
    return $text;
}

参考:
http://stackoverflow.com/questions/7697216/perl-one-liner-to-expand-unix-environment-variables

12.21.2011

Find out the absolute path from a relative path in Bourne Shell

Bシェル: 相対パスから絶対パスを得る方法

dirname コマンドで得られるディレクトリに cd し、pwd コマンドを行うことで絶対パスを得ることができる。
このときサブシェル内で実行することで、実際のシェルプロセスには影響を与えないようにする。

・例1 自分自身の居場所を特定する

ABSPATH=`(cd \`/usr/bin/dirname $0\` && pwd)`/`/usr/bin/basename $0`

・例2 自分自身の親ディレクトリを特定する

PARENTDIR=`(cd \`/usr/bin/dirname $0\`/.. && pwd)`

プロジェクトごとディレクトリを移動する場合などに便利。

参考:
http://dokonoumanohone.blog47.fc2.com/blog-entry-2.html
http://blog.hansode.org/archives/51481467.html

12.15.2011

XML::TreePP – 100% pure Perl XML parser module

Perl: Pure Perl 実装のXML解析モジュール

Perl モジュールでXML解析を行う場合、XML::Simple では XML::Parsar を要するため、
環境ごとにコンパイルが必要となってしまう。

Pure Perl 実装の XML::TreePP を使えば、.pm ファイルを置くだけで利用することが可能だ。

参考:
http://www.kawa.net/works/perl/treepp/treepp.html
http://search.cpan.org/~kawasaki/XML-TreePP-0.41/lib/XML/TreePP.pm

12.12.2011

Oracle: How to find foreign key constraints

Oracle:外部参照されているテーブルの確認方法

テーブルのトランケートを試み、
エラー「ORA-02266 表には使用可能な外部キーによって参照される一意キー/主キーが含まれています。」
が発生したときに、そのテーブルがどのテーブルから参照されているかを確認するSQL。

トランケートを行うには、外部キー制約を DISABLED にする必要がある。

SELECT
    constraint_name,
    table_name,
    status
FROM
    user_constraints
WHERE
    r_constraint_name IN
        (
        SELECT
            constraint_name
        FROM
            user_constraints
        WHERE
            table_name = ’テーブル名‘
        ); 

参考:
http://yp.xenophy.com/?p=74
http://www.databasejournal.com/features/oracle/article.php/3665591/Finding-Foreign-Key-Constraints-in-Oracle.htm

12.07.2011

Unix time conversion in AWK (with Fliegel-Van Flandern algorithm)

AWK: フリーゲルの公式に基づく Unix time 変換処理

gawk が使える場合を除き、AWKスクリプトにおけるグレゴリオ暦とUnix time(POSIX time)の相互変換処理は自前で準備する必要がある。
そこで今回はフリーゲルの公式を使って実装してみる。

・unix_time.awk ※テスト用コードも実装済み

#!/usr/bin/nawk -f

# Based on Fliegel-Van Flandern algorithm.
# Inputs must be Epoch (1970/01/01 00:00:00) and over.
# Time zone will not be considered.
function to_unix_time(yyyy, mm, dd, hh, mi, ss) {
  if (mm - 2 <= 0) { --yyyy; mm += 12}
  days = int(365.25 * yyyy) + int(yyyy / 400) - int(yyyy / 100) \
      + int(30.59 * (mm - 2)) + dd - 719499  # 1721089 - 2440588(Epoch)
  return ((days * 24 + hh) * 60 + mi) * 60 + ss
}

function to_string(unix_time) {
  ss = unix_time % 60; unix_time = (unix_time - ss) / 60
  mi = unix_time % 60; unix_time = (unix_time - mi) / 60
  hh = unix_time % 24; unix_time = (unix_time - hh) / 24
  j = unix_time + 2472632  # 2440588(Epoch) + 32044
  g = int(j / 146097); dg = j % 146097
  c = int((int(dg / 36524) + 1) * 3 / 4); dc = dg - c * 36524
  b = int(dc / 1461); db = dc % 1461
  a = int((int(db / 365) + 1) * 3 / 4); da = db - a * 365
  y = g * 400 + c * 100 + b * 4 + a
  m = int((da * 5 + 308) / 153) - 2
  d = da - int((m + 4) * 153 / 5) + 122
  yyyy = y - 4800 + int((m + 2) / 12)
  mm = (m + 2) % 12 + 1
  dd = d + 1
  return sprintf("%04d-%02d-%02d %02d:%02d:%02d", yyyy, mm, dd, hh, mi, ss)
}

# test code
{
  x = to_unix_time(substr($1, 1, 4), substr($1, 6, 2), substr($1, 9, 2))
  expected = (NR - 1) * 60 * 60 * 24
  if (x != expected) {
    print "Assertion failed. line " NR " - Expected: " expected ", Received: " x
    exit
  }
  print to_string(x)
}

Python の datetime モジュールの処理結果と比較することで、1970/1/1~9999/12/31 の期間の全日付について連続性および妥当性を検証する。

・unix_time_test.py

#!/usr/bin/env python

import datetime

s = datetime.date(1970, 1, 1)
t = datetime.date(9999, 12, 31)

while True:
  print '%s 00:00:00' % s
  if s >= t: break
  s += datetime.timedelta(days=1)

datetime.date では西暦10000年は表現できないので注意。(Exception が発生)
テスト用のシェルを作るならこのような感じである。

・unix_time_test.sh

#!/usr/bin/ksh

./unix_time_test.py > ./test_in.txt
./unix_time.awk ./test_in.txt > ./test_out.txt
diff ./test_in.txt ./test_out.txt > /dev/null
if [ $? -eq 0 ]; then print 'OK'; else print 'NG'; fi

改行コードがLFの場合、58657940 bytes(≒56MB) のファイルが2個生成される。(test_in.txt, test_out.txt)
Windows 環境なら diff のところを comp で検査。

・出力結果

OK

ただ実際のところ、もう少しわかりやすいコーディングのほうが周囲の理解を得やすいかもしれない。
Perl や Python、Ruby が使える環境であれば尚更である。

参考:
http://www5d.biglobe.ne.jp/~noocyte/Programming/GregorianAndJulianCalendars.html#DateToDayNumber
http://en.wikipedia.org/wiki/Julian_day

12.05.2011

How to show a run-time error message in Eclipse CDT 7.0.2

Eclipse CDT における実行時エラーメッセージの出力

Linux(UNIXも?)環境におけるEclipse Helios CDT 7.0.2のバグ。
例えば以下のようなプログラムを実行(Run)するとSegmentation faultで終了する。

int *x; x[0] = 0;

ところが、Eclipseのコンソール上には何もメッセージが表示されない。

Run configuration を以下のように設定すると実行時のstderrメッセージが表示されるようになる。

Main タブ – Application: /bin/sh
Arguments タブ – Program arguments: –c "Debug/program_name"

Eclipse 自体のバージョンアップによって解消するかは未確認。

参考:
http://stackoverflow.com/questions/3760734/how-to-let-eclipse-cdt-show-runtime-error-e-g-segmentation-fault
http://stackoverflow.com/questions/8099445/eclipse-cdt-running-c-program-show-nothing-in-the-console-why

12.03.2011

Failure probability calculator with Python

Python: 部品故障予測に関する計算

1. 目的

ある期間においてpの確率で故障する部品がn個稼働している。
このとき、期間内の故障発生回数が累計m回よりも多い確率を求めたい。

2. 前提条件

・故障が発生したら、その部品はすぐに新しい部品と交換される。(交換に要する時間は考慮しない)
・交換した部品が故障することもある。その場合も故障回数が加算される。
・故障の発生はポアソン分布とする。

3. 考察

1個の部品の故障率をλとする場合、この部品が期間内にx回故障する確率 P(x) は
ポアソン分布の定義から以下の式で表される。

image … 式(1)

 ※e は数学定数の一つであるネイピア数(Napier's constant)を表す。e = 2.71828…
 ※n! は n の階乗を表す。n! = n × (n-1) × ・・・ × 3 × 2 × 1

部品数がn個になれば、故障の確率はn倍となる。
したがって、故障率pのn個の部品の故障回数の累計がちょうどx回になる確率は以下ように求められる。

image … 式(2)

さて、ここで累計m回よりも多く故障が発生する確率(Q)は

 1-(故障発生回数がm回以下である確率)

と計算できる。つまり、

 故障が一度も発生しない確率(=故障発生回数が0)
 1回だけ故障が発生する確率
 累計2回故障が発生する確率
 累計3回故障が発生する確率
  ・・・
 累計m回故障が発生する確率

の合計を1から差し引いた値が求める確率である。

式で表すとこのようになる。

image … 式(3)

上記の計算を素直に実装すると、階乗の計算が m+1 回発生することとなる。
階乗自体の計算量はO(m)なので、全体の計算量はO(m2)。

mの数値が小さければ問題ないが、10000 程度なら計算不能となってしまうだろう。

 

式(1)をよく見ると、以下の漸化式が成り立つことがわかる。

image … 式(4)

これを利用してDP(Dynamic Programming/動的計画法)を行えば、計算量はO(m)となる。

さらに、このDPは2つの変数を交互に使用することで再利用可能である。
そうすることでメモリ使用量を大幅に節約できる。
これを擬似コードで書くと以下のようになる。

image

4. コード

・関数定義

import math

def FailureProbability(rate, num, times):
  rate *= num
  dp = [math.exp(-rate), 0]
  ret = 1 - dp[0]
  for i in range(1, times + 1):
    dp[i & 1] = dp[i & 1 ^ 1] * rate / i
    ret -= dp[i & 1]
  return ret

・実行例

print FailureProbability(0.03, 18, 0)
print FailureProbability(0.03, 18, 1)
print FailureProbability(0.03, 18, 2)
print FailureProbability(0.03, 18, 3)

 (実行結果)

0.417251747626
0.102567691344
0.0176029961479
0.00230935101263

この例では、故障率3%の部品が18個稼動している場合を想定している。

この結果から、
 41.7%の確率で少なくとも1個の部品が期間内に故障してしまう
 予備部品を2個用意したとしても、1.76%の確率で予備部品不足となる
  (3回以上の故障が発生する)
というようなことが見て取れる。

11.28.2011

One-liner IsPrime & GCD in C++

C++: 素数判定と最大公約数を求める1行関数

ショートコーディング風。

typedef long long LL;

bool IsPrime(LL x){LL i=1;for(;x%++i&&i*i<=x;);return i*i>x&&x^1;}
LL GCD(LL x,LL y){return y?GCD(y,x%y):x;}

普通のやり方(11文字長い)

bool IsPrime(LL x){for(LL i=2;i*i<=x;++i)if(x%i==0)return false;return x!=1;}

11.20.2011

Compare regions in the same file with Sakura Editor

サクラエディタを利用した単一ファイルの部分比較

同じファイルの中にある類似した部分を比較したい場合、サクラエディタで以下のような操作をすると簡便である。

・メニューから「ウィンドウ」-「左右に分割」 (Shift + F4)
・メニューから「設定」-「共通設定」 (Ctrl + 6)
 「ウィンドウ」タブ - 分割ウィンドウ - 「垂直スクロールの同期をとる」をチェックオフ

サクラエディタ
http://sakura-editor.sourceforge.net/

11.13.2011

HttpWatch on Firefox

Firefox 上で HttpWatch を使う場合の Tips

HttpWatch を使えば、http 通信の内容を確認することができる。
http://www.httpwatch.com/

しかし、Firefox でパイプライニングを有効にしていると、次のようなエラーが出て通信内容の取得ができない。

HttpWatch could not start recording because network.http.pipelining is enabled in Firefox
HttpWatch could not start recording because network.http.proxy.pipelining is enabled in Firefox

about:config から以下の設定を「false」に戻す必要がある。

network.http.pipelining
network.http.proxy.pipelining

11.12.2011

M/M/c (M/M/1) queue with Python

Python: M/M/c 待ち行列問題を解く

待ち行列理論の M/M/c モデル(=M/M/c/∞モデル、M/M/1モデルの一般化)の問題を Python で解く。
コードを簡単にするため、ビルトインの float をオーバーライドして0除算を可能にしている。

入力: トランザクション数 {λ∈0以上の浮動小数点数} (=平均到着間隔 Ta の逆数)
    平均サービス時間 {Ts∈0以上の浮動小数点数} (=平均サービス率 μ の逆数)
    サービス窓口数 {c∈1以上100以下の自然数}

出力:arr(arrival rate) = トランザクション数 = λ
   dep(departure rate) = 平均サービス率 = μ
   c = サービス窓口数
   util = サービス利用率 = ρ = λ / cμ
   TmQue = 平均待ち行列時間
   TmSys = 平均応答時間(ターンアラウンドタイム)
   NmQue = 待ち行列の長さの平均
   NmSys = 待ち系の長さの平均   

・mmc_queue.py

# Copyright (c) 2011 Mog Project. All rights reserved.
# -*- coding: utf-8 -*-
"""
In the mathematical theory of random processes, the M/M/c queue is
a multi-server queue model. It is a generalisation of the M/M/1 queue.

    Arrivals are a Poisson process
    Service time is exponentially distributed
    There are c servers
    The length of queue in which arriving users wait before being served is
        infinite
    The population of users (i.e. the pool of users), or requests, available
        to join the system is infinite

This type of system arises in many situations, including lines at a bank,
    phone queueing systems, the application of computer resources, etc...

http://en.wikipedia.org/wiki/M/M/c_queue
"""
import math
from decimal import Decimal

INF = float('inf')
class Float(float):
  def __div__(self, other):
    if other:
      return float.__div__(self, other)
    elif self == 0.0 or math.isnan(self):
      return float('nan')
    return float('inf') if self > 0.0 else float('-inf')

class InputError(Exception): pass
class MMcQueue(object):
  def __init__(self, arrival_rate, service_time, num_servers=1):
    """
    @param arrival_rate: 0 and over
    @param service_time: 0 and over
    @param num_servers: int between 1 and 100, inclusive
    """
    self.c = num_servers  # Number of servers.
    if not (isinstance(num_servers, int) and 1 <= num_servers <= 100):
      raise InputError('num_servers must be int between 1 and 100, inclusive.')
    if arrival_rate < 0 or service_time < 0:
      raise InputError('arrival_time and service_time must be 0 and over.')

    self.arrival_rate = Float(arrival_rate)
    service_time = Float(service_time)
    self.service_rate = Float(1.0) / service_time
    self.util = self.arrival_rate / self.service_rate / self.c

    if self.util == 0.0:
      self.tw = self.lq = self.lw = 0.0
      self.tq = service_time
      return
    if self.util >= 1.0:
      self.tw = self.tq = self.lq = self.lw = INF
      return

    crc = pow(self.c * self.util, self.c)
    factc = math.factorial(self.c)
    x = 0.0
    for i in range(self.c):
      x += pow(self.c * self.util, i) / math.factorial(i)
    x += crc / (factc * (1.0 - self.util))
    x = crc / x / (factc * (1.0 - self.util))

    # Expected number of customers waiting in queue – not in service
    self.lw = x * self.util / (1.0 - self.util)
    # Average waiting time in queue
    self.tw = Float(self.lw) / self.arrival_rate
    # Average time in system (queued + serviced)
    self.tq = self.tw + service_time
    # Expected number of customers in system
    self.lq = self.arrival_rate * self.tq
    return

  def __str__(self):
    return ('arr=%.3f, dep=%.3f, c=%d, util=%.3f, ' +
        'TmQue=%.3f, TmSys=%.3f, NmQue=%.3f, NmSys=%.3f') \
        % (self.arrival_rate, self.service_rate, self.c, self.util,
        self.tw, self.tq, self.lw, self.lq)

def main():
  # boundary values
  print MMcQueue(0, 0)
  print MMcQueue(1, 0)
  print MMcQueue(0, 1)
  print MMcQueue(1, 1)
  print MMcQueue(INF, 0)
  print MMcQueue(INF, 1)
  print MMcQueue(0, INF)
  print MMcQueue(1, INF)
  print MMcQueue(INF, INF)
  print MMcQueue(1, 99, 100)

  # error cases
#  print MMcQueue(-1, 1)
#  print MMcQueue(1, -1)
#  print MMcQueue(1, 1, 0)
#  print MMcQueue(1, 1, 101)

  # loop sample
  i = Decimal(0.0)
  while i <= 2.0:
    print MMcQueue(i, 10, 15)
    i += Decimal(0.1)
  for i in range(1, 10):
    print MMcQueue(2, 2, i)

if __name__ == '__main__':
  main()

・出力結果

arr=0.000, dep=inf, c=1, util=0.000, TmQue=0.000, TmSys=0.000, NmQue=0.000, NmSys=0.000
arr=1.000, dep=inf, c=1, util=0.000, TmQue=0.000, TmSys=0.000, NmQue=0.000, NmSys=0.000
arr=0.000, dep=1.000, c=1, util=0.000, TmQue=0.000, TmSys=1.000, NmQue=0.000, NmSys=0.000
arr=1.000, dep=1.000, c=1, util=1.000, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=inf, dep=inf, c=1, util=nan, TmQue=nan, TmSys=nan, NmQue=nan, NmSys=nan
arr=inf, dep=1.000, c=1, util=inf, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=0.000, dep=0.000, c=1, util=nan, TmQue=nan, TmSys=nan, NmQue=nan, NmSys=nan
arr=1.000, dep=0.000, c=1, util=inf, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=inf, dep=0.000, c=1, util=inf, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=1.000, dep=0.010, c=100, util=0.990, TmQue=87.394, TmSys=186.394, NmQue=87.394, NmSys=186.394
arr=0.000, dep=0.100, c=15, util=0.000, TmQue=0.000, TmSys=10.000, NmQue=0.000, NmSys=0.000
arr=0.100, dep=0.100, c=15, util=0.067, TmQue=0.000, TmSys=10.000, NmQue=0.000, NmSys=1.000
arr=0.200, dep=0.100, c=15, util=0.133, TmQue=0.000, TmSys=10.000, NmQue=0.000, NmSys=2.000
arr=0.300, dep=0.100, c=15, util=0.200, TmQue=0.000, TmSys=10.000, NmQue=0.000, NmSys=3.000
arr=0.400, dep=0.100, c=15, util=0.267, TmQue=0.000, TmSys=10.000, NmQue=0.000, NmSys=4.000
arr=0.500, dep=0.100, c=15, util=0.333, TmQue=0.000, TmSys=10.000, NmQue=0.000, NmSys=5.000
arr=0.600, dep=0.100, c=15, util=0.400, TmQue=0.002, TmSys=10.002, NmQue=0.001, NmSys=6.001
arr=0.700, dep=0.100, c=15, util=0.467, TmQue=0.008, TmSys=10.008, NmQue=0.005, NmSys=7.005
arr=0.800, dep=0.100, c=15, util=0.533, TmQue=0.028, TmSys=10.028, NmQue=0.022, NmSys=8.022
arr=0.900, dep=0.100, c=15, util=0.600, TmQue=0.080, TmSys=10.080, NmQue=0.072, NmSys=9.072
arr=1.000, dep=0.100, c=15, util=0.667, TmQue=0.204, TmSys=10.204, NmQue=0.204, NmSys=10.204
arr=1.100, dep=0.100, c=15, util=0.733, TmQue=0.474, TmSys=10.474, NmQue=0.522, NmSys=11.522
arr=1.200, dep=0.100, c=15, util=0.800, TmQue=1.064, TmSys=11.064, NmQue=1.277, NmSys=13.277
arr=1.300, dep=0.100, c=15, util=0.867, TmQue=2.478, TmSys=12.478, NmQue=3.222, NmSys=16.222
arr=1.400, dep=0.100, c=15, util=0.933, TmQue=7.223, TmSys=17.223, NmQue=10.112, NmSys=24.112
arr=1.500, dep=0.100, c=15, util=1.000, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=1.600, dep=0.100, c=15, util=1.067, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=1.700, dep=0.100, c=15, util=1.133, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=1.800, dep=0.100, c=15, util=1.200, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=1.900, dep=0.100, c=15, util=1.267, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=2.000, dep=0.500, c=1, util=4.000, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=2.000, dep=0.500, c=2, util=2.000, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=2.000, dep=0.500, c=3, util=1.333, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=2.000, dep=0.500, c=4, util=1.000, TmQue=inf, TmSys=inf, NmQue=inf, NmSys=inf
arr=2.000, dep=0.500, c=5, util=0.800, TmQue=1.108, TmSys=3.108, NmQue=2.216, NmSys=6.216
arr=2.000, dep=0.500, c=6, util=0.667, TmQue=0.285, TmSys=2.285, NmQue=0.570, NmSys=4.570
arr=2.000, dep=0.500, c=7, util=0.571, TmQue=0.090, TmSys=2.090, NmQue=0.180, NmSys=4.180
arr=2.000, dep=0.500, c=8, util=0.500, TmQue=0.030, TmSys=2.030, NmQue=0.059, NmSys=4.059
arr=2.000, dep=0.500, c=9, util=0.444, TmQue=0.010, TmSys=2.010, NmQue=0.019, NmSys=4.019
 

参考:
http://en.wikipedia.org/wiki/M/M/c_queue
http://tomari.org/main/java/machim.html

11.03.2011

How to break out of all loops in Python

Python: 多階層のループから抜け出す方法

goto が使えないので例外を発生させるか、このような方法を取る。

for i in range(5000):
    for j in range(3000):
        if should_terminate_the_loop:
           break
    else: 
        continue # no break encountered
    break

参考:
http://stackoverflow.com/questions/438844/is-there-a-label-in-python

10.30.2011

Powers, Factorials, Permutations and Combinations in C++

C++: 累乗、階乗、順列、組み合わせ

これらの計算結果に対するM(通常は10^9付近)の剰余をメモリ上へ格納するクラス。
メモリ使用量が64MB程度以内に収まるよう入力値を制限しているが、取得に関してはチェックしない。

class Power {
 public:
  Power(int num, int modulus=1000000007) {
    if (num > 10000000) { throw std::exception(); }
    data_.resize(num + 1);
    data_[0] = 1;
    for (int i = 1; i <= num; ++i) {
      data_[i] = ((long long)num * data_[i - 1]) % modulus;
    }
  }
  int operator()(int n) { return data_[n]; }

 private:
  std::vector<int> data_;
};

class Factorial {
 public:
  Factorial(int num, int modulus=1000000007) {
    if (num > 10000000) { throw std::exception(); }
    data_.resize(num + 1);
    data_[0] = 1;
    for (long long i = 1; i <= (long long)num; ++i) {
      data_[i] = (i * data_[i - 1]) % modulus;
    }
  }
  int operator()(int n) { return data_[n]; }

 private:
  std::vector<int> data_;
};

class Permutation {
 public:
  Permutation(int num, int modulus=1000000007) {
    if (num > 4000) { throw std::exception(); }
    data_.resize(num + 1);
    for (int i = 1; i <= num; ++i) {
      data_[i].resize(num + 1);
      data_[i][0] = 1;
      for (int j = 1; j <= i; ++j) {
        data_[i][j] = ((long long)(i - j + 1) * data_[i][j - 1]) % modulus;
      }
    }
  }
  int operator()(int n, int r) { return data_[n][r]; }

 private:
  std::vector<std::vector<int> > data_;
};

class Combination {
 public:
  Combination(int num, int modulus=1000000007) {
    if (num > 4000) { throw std::exception(); }
    data_.resize(num + 1);
    for (int i = 0; i <= num; ++i) {
      data_[i].resize(num + 1);
      data_[i][0] = 1;
      for (int j = 1; j <= i; ++j) {
        data_[i][j] =
            ((long long)data_[i - 1][j] + data_[i - 1][j - 1]) % modulus;
      }
    }
  }
  int operator()(int n, int r) { return data_[n][r]; }

 private:
  std::vector<std::vector<int> > data_;
};

10.29.2011

Segment tree in C++

C++: セグメント木の実装

template <typename T, typename Compare=std::less<T> >
class SegmentTree {
 public:
  SegmentTree(int num, T default_value=T())
      : default_(default_value) {
    num_ = 1;
    while (num_ <= num) num_ <<= 1;
    dat_.resize(2 * num_ - 1, default_);
  }

  void Update(int index, T value) {
    index += num_ - 1;
    dat_[index] = value;

    while (index > 0) {
      index = (index - 1) / 2;
      dat_[index] = Compare_(dat_[index * 2 + 1], dat_[index * 2 + 2]);
    }
  }

  // [from, to]
  T Query(int from, int to) {
    return Query_(from, to + 1, 0, 0, num_);
  }
 private:
  std::vector<T> dat_;
  int num_;
  T default_;

  T Compare_(T x, T y) { return Compare()(x, y) ? x : y; }

  T Query_(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return default_;
    if (a <= l && r <= b) {
      return dat_[k];
    } else {
      T vl = Query_(a, b, k * 2 + 1, l, (l + r) / 2);
      T vr = Query_(a, b, k * 2 + 2, (l + r) / 2, r);
      return Compare_(vl, vr);
    }
  }
};

10.28.2011

Visual Studio: Cannot find the resource compiler DLL

Visual Studio: リソースコンパイラDLLが見つかりません

Visual Studio 2010 Pro のインストールの際、インストールパスをデフォルトから変更する。
その後、リソースエディタを開こうとすると『リソースコンパイラDLLが見つかりません。』というエラーが発生する。

実際のファイルはここにあるので、これをコピーすればよい。
C:\Program Files\Microsoft SDKs\Windows\v7.0A\bin
 配下 RC.Exe, RcDll.Dll

参考:
http://connect.microsoft.com/VisualStudio/feedback/details/525412/missing-rcdll-dll-file

10.23.2011

mogmail with Python version 2.2

Python版mogmail バージョン2.2

こちらのスクリプトの改修。
http://mogproject.blogspot.com/2011/10/mogmail-with-python-version-21.html

出力をリダイレクトした場合など、sys.stdout.encoding が None になるケースがあった。
その場合は sys.getfilesystemencoding() から出力先のエンコーディングを取得するよう修正。

mogmail.py

#!/usr/bin/env python
# Copyright (c) 2011 Mog Project. All rights reserved.
# Version: 2.2, Updated: 2011/10/23

POP3_SERVER = 'POP3-Server'
POP3_PORT = 110
POP3_USERNAME = 'UserName'
POP3_PASSWORD = 'Password'
SHOW_LENGTH = 5

import poplib
import email
from email.header import decode_header
from email.utils import parsedate_tz
from email.utils import mktime_tz
import sys
import time

if sys.stdout.encoding:
  OUTPUT_ENCONDING = sys.stdout.encoding
else:
  OUTPUT_ENCONDING = sys.getfilesystemencoding()

def jis_to_sjis(jis):
  esc_seq = (  # pair of (sequense, is_double_bytes)
      ('\x1b(B', False),  # ASCII
      ('\x1b(J', False),  # JIS X 0201-1976 Roman Set
      ('\x1b(I', False),  # JIS X 0201-1976 Katakana
      ('\x1b$@', True),  # JIS X 0208-1978 (old JIS kanji)
      ('\x1b$B', True),  # JIS X 0208-1983 (new JIS kanji)
      ('\x1b&@\x1b$B', True),  # JIS X 0208-1990
      ('\x1b$(D', True)  # JIS X 0212-1990
      )
  chunks = []
  pos = 0
  flg = False
  while pos < len(jis):
    for seq, is_double_bytes in esc_seq:
      if jis[pos:].startswith(seq):
        flg = is_double_bytes
        pos += len(seq)
        break
    else:
      if flg:
        hi, lo = ord(jis[pos]), ord(jis[pos + 1])
        if hi & 1:
          hi = ((hi + 1) >> 1) + 0x70
          lo += 0x1f
        else:
          hi = (hi >> 1) + 0x70
          lo += 0x7d
        if hi >= 0xa0: hi += 0x40
        if lo >= 0x7f: lo += 1
        chunks.append(chr(hi) + chr(lo))
        pos += 2
      else:
        chunks.append(jis[pos])
        pos += 1
  return ''.join(chunks)

class Parser(object):
  def __init__(self, msg):
    self.msg = msg
  def date(self):
    return time.localtime(mktime_tz(parsedate_tz(self.msg['date'])))
  def from_(self): return self.get_item('from')
  def subject(self): return self.get_item('subject')
  def get_item(self, key):
    uchunks = []
    decoded_seq = decode_header(self.msg[key].replace('"', ''))
    for s, charset in decoded_seq:
      if not charset: charset = 'us-ascii'

      # If charset is iso-2022-jp(jis), convert to cp932(sjis)
      #   for platform dependent characters.
      if charset == 'iso-2022-jp':
        s = jis_to_sjis(s)
        charset = 'cp932'
      uchunks.append(unicode(s, charset, 'ignore'))
    return u''.join(uchunks).encode(OUTPUT_ENCONDING)

def main():
  pop3 = poplib.POP3(POP3_SERVER, POP3_PORT)
  try:
    pop3.apop(POP3_USERNAME, POP3_PASSWORD)
    msg_cnt = pop3.stat()[0]
    if not msg_cnt: print 'No message.'
    for i in range(msg_cnt, max(msg_cnt - SHOW_LENGTH, 0), -1):
      p = Parser(email.message_from_string('\n'.join(pop3.top(i, 0)[1])))
      print time.strftime('[%m/%d %H:%M]', p.date()),
      print '%s\n  %s' % (p.from_(), p.subject())
  except poplib.error_proto, detail:
    print 'POP3 Protocol Error:', detail
  finally:
    pop3.quit()

if __name__ == '__main__':
  main()

参考:
http://d.hatena.ne.jp/nagaetty/20090811

mogmail with Python version 2.1

Python版mogmail バージョン2.1

以前作成した、こちらのスクリプトを改良。
http://mogproject.blogspot.com/2011/10/mogmail-with-python-version-20.html

・JISのデコードに失敗した機種依存文字については、一旦SJISに変換してから
 cp932 でデコードすれば正しく表示されることがわかった。
・JISからSJISの変換については、結局自前で実装することに。

mogmail.py

#!/usr/bin/env python
# Copyright (c) 2011 Mog Project. All rights reserved.
# Version: 2.1, Updated: 2011/10/23

import poplib
import email
from email.header import decode_header
from email.utils import parsedate_tz
from email.utils import mktime_tz
import sys
import time

POP3_SERVER = 'POP3-Server'
POP3_PORT = 110
POP3_USERNAME = 'UserName'
POP3_PASSWORD = 'Password'
SHOW_LENGTH = 5

def jis_to_sjis(jis):
  esc_seq = (  # pair of (sequense, is_double_bytes)
      ('\x1b(B', False),  # ASCII
      ('\x1b(J', False),  # JIS X 0201-1976 Roman Set
      ('\x1b(I', False),  # JIS X 0201-1976 Katakana
      ('\x1b$@', True),  # JIS X 0208-1978 (old JIS kanji)
      ('\x1b$B', True),  # JIS X 0208-1983 (new JIS kanji)
      ('\x1b&@\x1b$B', True),  # JIS X 0208-1990
      ('\x1b$(D', True)  # JIS X 0212-1990
      )
  chunks = []
  pos = 0
  flg = False
  while pos < len(jis):
    for seq, is_double_bytes in esc_seq:
      if jis[pos:].startswith(seq):
        flg = is_double_bytes
        pos += len(seq)
        break
    else:
      if flg:
        hi, lo = ord(jis[pos]), ord(jis[pos + 1])
        if hi & 1:
          hi = ((hi + 1) >> 1) + 0x70
          lo += 0x1f
        else:
          hi = (hi >> 1) + 0x70
          lo += 0x7d
        if hi >= 0xa0: hi += 0x40
        if lo >= 0x7f: lo += 1
        chunks.append(chr(hi) + chr(lo))
        pos += 2
      else:
        chunks.append(jis[pos])
        pos += 1
  return ''.join(chunks)

class Parser(object):
  def __init__(self, msg):
    self.msg = msg
  def date(self):
    return time.localtime(mktime_tz(parsedate_tz(self.msg['date'])))
  def from_(self): return self.get_item('from')
  def subject(self): return self.get_item('subject')
  def get_item(self, key):
    uchunks = []
    decoded_seq = decode_header(self.msg[key].replace('"', ''))
    for s, charset in decoded_seq:
      if not charset: charset = 'us-ascii'

      # If charset is iso-2022-jp(jis), convert to cp932(sjis)
      #   for platform dependent characters.
      if charset == 'iso-2022-jp':
        s = jis_to_sjis(s)
        charset = 'cp932'
      uchunks.append(unicode(s, charset, 'ignore'))
    return u''.join(uchunks).encode(sys.stdout.encoding)

def main():
  pop3 = poplib.POP3(POP3_SERVER, POP3_PORT)
  try:
    pop3.apop(POP3_USERNAME, POP3_PASSWORD)
    msg_cnt = pop3.stat()[0]
    if not msg_cnt: print 'No message.'
    for i in range(msg_cnt, max(msg_cnt - SHOW_LENGTH, 0), -1):
      p = Parser(email.message_from_string('\n'.join(pop3.top(i, 0)[1])))
      print time.strftime('[%m/%d %H:%M]', p.date()),
      print '%s\n  %s' % (p.from_(), p.subject())
  except poplib.error_proto, detail:
    print 'POP3 Protocol Error:', detail
  finally:
    pop3.quit()

if __name__ == '__main__':
  main()

Converting Japanese character encodings

日本語文字コードの変換について

http://www.tohoho-web.com/wwwkanji.htm

10.22.2011

mogmail with Python version 2.0

Python版mogmail バージョン2.0

以前作成した、こちらのスクリプトを改良。
http://mogproject.blogspot.com/2011/10/mogmail-with-python-version-11.html

・メールが一通もない場合にメッセージを出すようにした。
・From/Subject に機種依存文字(丸囲み文字等)が入っている場合、文字コードのデコードに失敗していた。
 unicode 文字列を作成するときに errors='ignore' とすれば、ひとまずその文字はスキップされる。
 しかし、email.header モジュールのmake_header ではその指定ができないので仕方なく自分で実装。
・パーザーをクラス化。
・出力する文字コードを自動取得。(sys.stdout.encoding とする)
・通信中の例外発生時にもquit()が行われるようにした。

mogmail.py

#!/usr/bin/env python
# Copyright (c) 2011 Mog Project. All rights reserved.
# Version: 2.0, Updated: 2011/10/22

import poplib
import email
from email.header import decode_header
from email.utils import parsedate_tz
from email.utils import mktime_tz
import sys
import time

POP3_SERVER = 'POP3-Server'
POP3_PORT = 110
POP3_USERNAME = 'UserName'
POP3_PASSWORD = 'Password'
SHOW_LENGTH = 5

class Parser(object):
  def __init__(self, msg):
    self.msg = msg
  def date(self):
    return time.localtime(mktime_tz(parsedate_tz(self.msg['date'])))
  def from_(self): return self.get_item('from')
  def subject(self): return self.get_item('subject')
  def get_item(self, key):
    uchunks = []
    decoded_seq = decode_header(self.msg[key].replace('"', ''))
    for s, charset in decoded_seq:
      if not charset: charset = 'us-ascii'
      uchunks.append(unicode(s, charset, 'ignore'))
    return u''.join(uchunks).encode(sys.stdout.encoding)

pop3 = poplib.POP3(POP3_SERVER, POP3_PORT)
try:
  pop3.apop(POP3_USERNAME, POP3_PASSWORD)
  msg_cnt = pop3.stat()[0]
  if not msg_cnt: print 'No message.'
  for i in range(msg_cnt, max(msg_cnt - SHOW_LENGTH, 0), -1):
    p = Parser(email.message_from_string('\n'.join(pop3.top(i, 0)[1])))
    print time.strftime('[%m/%d %H:%M]', p.date()),
    print '%s\n  %s' % (p.from_(), p.subject())
except poplib.error_proto, detail:
  print 'POP3 Protocol Error:', detail
finally:
  pop3.quit()

10.21.2011

Joining two files in AWK

AWK: 2個のファイルの結合

N行の file0 と M行の file1 を共通のキーを元に結合する。(N, M > 0)
AWKを使い、少ない計算量で実現したい。

・file0

   1: 1 one
   2: 2 two
   3: 3 three
   4: 4 four
   5: 5 five

・file1
   1: 3
   2: 5
   3: 2
   4: 4
   5: 1
   6: 2
   7: 3
   8: 5


この時、組み込み変数「NR(入力行)」と「FNR(ファイルの入力行)」を使用したトリッキーなレシピがある。

・num_to_alpha.awk

   1: #!/usr/bin/nawk -f
   2:  
   3: NR == FNR {
   4:   dict[$1] = $2
   5:   next
   6: }
   7:  
   8: {
   9:   print dict[$1]
  10: }

NR=FNR の場合、現在のレコードは最初のファイルであることと同値。
2個目のファイルであれば、NR=N+FNR となるからだ。

最初のファイルの読み込みでは、データをメモリへ格納するのみ。
2個目のファイルの読み取りの際に、連想配列からデータを参照して出力する。

・出力結果

   1: $ ./num_to_alpha.awk ./file0 ./file1                                          
   2: three
   3: five
   4: two
   5: four
   6: one
   7: two
   8: three
   9: five

これで計算量はO(N + M log N)となる。

参考:
http://www.kt.rim.or.jp/~kbk/gawk-30/gawk_11.html

10.19.2011

SQL tracing using 'EVENT 10046'

'EVENT 10046'  設定によるSQLトレース取得

デバッグ用機能を使ってお手軽に詳細なSQLトレースを取得する方法。

環境変更なく、現行セッションのみにトレースを仕掛けることができる。

   1: SQL> ALTER SESSION SET EVENTS '10046 trace name context forever, level 12';
   2: SQL> チューニング対象SQLの実行
   3: SQL> ALTER SESSION SET EVENTS '10046 trace name context off';

結果は、$ORACLE_BASE/admin/<DB_NAME>/udump 配下に出力される。
内容を確認するためには、TKPROF ユーティリティを使用すればよい。

$ tkprof 出力された.trcファイル 整形後のファイル explain=ユーザ/パスワード sys=no

参考:
http://www.atmarkit.co.jp/fdb/rensai/orasql05/orasql05_1.html
http://www.atmarkit.co.jp/fdb/rensai/orasql05/orasql05_2.html

10.12.2011

mogmail with Python version 1.1

Python版mogmail バージョン1.1


以前作成した、こちらのスクリプトを改良。
http://mogproject.blogspot.com/2011/04/pythonmogmail.html

・ヘッダを得るだけなのに、retr() を行うのは冗漫だった。top(which, 0) で十分。
・Fromにダブルクオーテーションが含まれているとBase64デコードに失敗していた。
 事前に除去する。


mogmail.py

#!/usr/bin/env python
# Copyright (c) 2011 Mog Project. All rights reserved.
# Version: 1.1, Updated: 2011/10/12

import poplib
import email
from email.header import make_header
from email.header import decode_header
from email.utils import parsedate_tz
from email.utils import mktime_tz
import time

POP3_SERVER = 'POP3-Server'
POP3_PORT = 110
POP3_USERNAME = 'UserName'
POP3_PASSWORD = 'Password'
SHOW_LENGTH = 5

f = lambda key: unicode(make_header(decode_header(
    headers[key].replace('"', ''))))
try:
  pop3 = poplib.POP3(POP3_SERVER, POP3_PORT)
  pop3.apop(POP3_USERNAME, POP3_PASSWORD)
  msg_cnt = pop3.stat()[0]
  for i in range(msg_cnt, max(msg_cnt - SHOW_LENGTH, 0), -1):
    headers = email.message_from_string('\n'.join(pop3.top(i, 0)[1]))
    print time.strftime('[%m/%d %H:%M]',
        time.localtime(mktime_tz(parsedate_tz(headers['date'])))),
    print '%s\n  %s' % (f('from'), f('subject'))
  pop3.quit()
except poplib.error_proto, detail:
  print 'POP3 Protocol Error:', detail

10.11.2011

Sudden Eclipse error

Eclipse が突然落ちる

PyDevで開発中に突然Eclipseの画面が消えてしまう現象が何度か発生。(プロセスは残っているが復旧不可)
まずは、workspace/.metadata/.log を確認。

こんなのが出ていた。調査は後日。

!MESSAGE Unhandled event loop exception
!STACK 0
org.eclipse.swt.SWTException: Failed to execute runnable (org.eclipse.swt.SWTError: No more handles)

!MESSAGE Unhandled event loop exception
!STACK 0
org.eclipse.swt.SWTError: No more handles

!MESSAGE An unexpected exception was thrown.
!STACK 0
java.lang.NullPointerException

!MESSAGE Widget disposed too early!
!STACK 0
java.lang.RuntimeException: Widget disposed too early!

9.28.2011

Solaris: How to find if the process is 64-bit or 32-bit

Solaris: 動作中のプロセスが 64bit か 32bit か調べる方法

プロセスが64bitで稼動しているか、32bitで稼動しているかを調べるには pflags コマンドを使えばよい。

# pflags 2594 |grep model
        data model = _ILP32  flags = ORPHAN|MSACCT|MSFORK

データモデルの内容を確認。
_ILP32 => 32bit (int / long / pointer が 32 ビット)
_LP64  => 64bit (long /pointer が 64 ビット)
_LLP64 => 64bit Windows (long long / pointer が 64ビット)

参考:
http://www.ginnokagi.com/2009/02/weblogic.html
http://blogs.oracle.com/yappri/entry/32_or_64

9.26.2011

Format the JavaVM GC log: pt.2

GCログの整形 その2

GCログのタイムスタンプ(JavaVMを起動してからの秒数)をシステム時刻に整形するスクリプト。
ファイルの最終更新時刻と最終エントリのタイムスタンプを突き合わせる発想は凄い。

http://www.theserverlabs.com/blog/2010/05/26/human-readable-jvm-gc-timestamps/

以下転載

#!/usr/bin/env python
  
import sys, os, datetime
  
# true if string is a positive float
def validSeconds(str_sec):
    try:
        return 0 < float(str_sec)
    except ValueError:
        return False
  
# show usage               
if len(sys.argv) < 2:
    print "Usage: %s <gc.log>" % (sys.argv[0])
    sys.exit(1)
  
file_str = sys.argv[1]
lastmod_date = datetime.datetime.fromtimestamp(os.path.getmtime(file_str))
  
file = open(file_str, 'r')
lines = file.readlines()
file.close()
  
# get last elapsed time
for line in reversed(lines):
    parts = line.split(':')
    if validSeconds(parts[0]):
        break
  
# calculate start time
start_date = lastmod_date - datetime.timedelta(seconds=float(parts[0]))
  
# print file prepending human readable time where appropiate 
for line in lines:
    parts = line.split(':')
    if not validSeconds(parts[0]):
        print line.rstrip()
        continue
    line_date = start_date + datetime.timedelta(seconds=float(parts[0]))
    print "%s: %s" % (line_date.isoformat(), line.rstrip())

Format the JavaVM GC log: pt.1

GCログの整形 その1

GCログから数値だけを抽出したい場合、sed で文字を消してしまうのが一番簡単。

sed –e 's/[^0-9.]/ /g'

9.25.2011

Uninstalling Eclipse plugins

Eclipse プラグインのアンインストール

現行のEclipseでは、プラグインのアンインストール機能が装備されている。

「Help」-「About Eclipse SDK」から「Installation Details」。

参考:
http://onlineconsultant.jp/pukiwiki/?Eclipse%20%E3%83%97%E3%83%A9%E3%82%B0%E3%82%A4%E3%83%B3%E3%81%AE%E3%82%A2%E3%83%B3%E3%82%A4%E3%83%B3%E3%82%B9%E3%83%88%E3%83%BC%E3%83%AB

9.24.2011

Overloading constructor in Python

Python: コンストラクタのオーバーロード

・パラメータの型によって挙動を変える

class Widget():
  def __init__(self, arg):
    if isinstance(arg, int): print arg * 10
    elif isinstance(arg, basestring): print arg + '0'

Widget(1234)  # 12340
Widget('1234')  # 12340

・パラメータの数によって挙動を変える

class Widget():
  def __init__(self, *args):
    if len(args) == 1: print '1 arg.'
    elif len(args) == 2: print '2 args.'

Widget(1)  # 1 arg.
Widget(1, 2)  # 2 args.

・個数と型を両方チェック

class Widget():
  def __init__(self, *args):
    def check(*types):
      if len(args) != len(types): return False
      for i, arg in enumerate(args):
        if not isinstance(arg, types[i]): return False
      return True
    if check(int): print args[0]
    elif check(int, int, basestring): print args[2]
    else: print 'other'

Widget(1)  # 1
Widget(1, 2, '3')  # 3
Widget('3')  # other

9.20.2011

Printing to standard error in Python

Python: 標準エラーへの出力

Python 2.x系の場合

>>> import sys
>>> sys.stderr.write('STDERR')
STDERR
>>> print >> sys.stderr, 'STDERR'
STDERR
>>> 

参考:
http://diveintopython.org/scripts_and_streams/stdin_stdout_stderr.html

9.18.2011

UML modeling in Eclipse pt.2

Eclipse で UMLモデリング その2

EclipseUML のFree版を使うという手もある。
http://www.ejb3.org/download.html

jarファイルをダウンロードして実行すると、インストーラーが走る。

eclipse.ini にメモリオプションを追加するのを忘れずに。
javaプロジェクト以外には使えないようだ。

その他のプラグイン一覧。
http://www.eclipsewiki.net/eclipse/index.php?UML%A5%E2%A5%C7%A5%EA%A5%F3%A5%B0%A5%D7%A5%E9%A5%B0%A5%A4%A5%F3

9.16.2011

UML modeling in Eclipse

Eclipse でUMLモデリング

AmaterasUML というプラグインを使えば、Eclipse 上でクラス図やシーケンス図を作ることができる。

前提として、GEFの導入が必要。

・GEF
Eclipse上で「Help」-「Install New Software...」を選択。
「Work with」に http://download.eclipse.org/tools/gef/updates を指定して「Add」。
Nameは「GEF」など適当に。

表示される「GEF SDK x.x.x」(最新版でOK)をインストール。

・AmaterasUML
http://amateras.sourceforge.jp/cgi-bin/fswiki/wiki.cgi?page=AmaterasUML
zip ファイルをダウンロードして、展開したjarファイル群を plugins ディレクトリに入れる。
Eclipse が新しければ、dropins 配下でも構わない。その後、Eclipse を再起動。

参考:
http://www.eclipse.org/gef/

9.10.2011

Python: Exceptions of urllib2 - opener.open

Python: urllib2 – opener.open の例外

opener.open() を行う際、urllib2.URLError だけの把捉だけでは不十分。

予め「import socket」し、「socket.timeout」もキャッチする必要がある。

9.04.2011

Apache: CVE-2011-3192 httpd: multiple ranges DoS

Apache 脆弱性 CVE-2011-3192 のメモ

いわゆるApache Killer 関連について。

複数の(大抵は1バイト・インクリメントな)rangeヘッダ要求によるhttpdプロセスサイズ肥大化の主役は
apr_bucket という構造体。

Apache 2.0系の場合、ソースは srclib\apr-util\include\apr_buckets.h にあった。

/**
 * apr_bucket structures are allocated on the malloc() heap and
 * their lifetime is controlled by the parent apr_bucket_brigade
 * structure. Buckets can move from one brigade to another e.g. by
 * calling APR_BRIGADE_CONCAT(). In general the data in a bucket has
 * the same lifetime as the bucket and is freed when the bucket is
 * destroyed; if the data is shared by more than one bucket (e.g.
 * after a split) the data is freed when the last bucket goes away.
 */
struct apr_bucket {
    /** Links to the rest of the brigade */
    APR_RING_ENTRY(apr_bucket) link;
    /** The type of bucket.  */
    const apr_bucket_type_t *type;
    /** The length of the data in the bucket.  This could have been implemented
     *  with a function, but this is an optimization, because the most
     *  common thing to do will be to get the length.  If the length is unknown,
     *  the value of this field will be (apr_size_t)(-1).
     */
    apr_size_t length;
    /** The start of the data in the bucket relative to the private base
     *  pointer.  The vast majority of bucket types allow a fixed block of
     *  data to be referenced by multiple buckets, each bucket pointing to
     *  a different segment of the data.  That segment starts at base+start
     *  and ends at base+start+length.  
     *  If the length == (apr_size_t)(-1), then start == -1.
     */
    apr_off_t start;
    /** type-dependent data hangs off this pointer */
    void *data;    
    /**
     * Pointer to function used to free the bucket. This function should
     * always be defined and it should be consistent with the memory
     * function used to allocate the bucket. For example, if malloc() is 
     * used to allocate the bucket, this pointer should point to free().
     * @param e Pointer to the bucket being freed
     */
    void (*free)(void *e);
    /** The freelist from which this bucket was allocated */
    apr_bucket_alloc_t *list;
};

参考:
http://www.ipa.go.jp/security/ciadr/vul/20110831-apache.html
http://httpd.apache.org/download.cgi#apache20
http://d.hatena.ne.jp/nice20/20110829/p1

8.29.2011

C++: Matrix class

C++: 2次元行列クラスの作成

とりあえず、行列の積(operator*)と累乗(pow)のみ実装。
全ての値はMの剰余としているが、適宜変更して使用する。

template <typename T>
class Matrix {
 public:
  Matrix(int row, int column, T value=T()) {
    data.resize(row, std::vector<T>(column, value));
  }
  int rows() const { return static_cast<int>(data.size()); }
  int columns() const { return static_cast<int>(data[0].size()); }

  Matrix<T> operator*(Matrix<T> const& rhs) const {
    int m = rows();
    int n = rhs.rows();
    int p = rhs.columns();
    Matrix<T> ret(m, p);
    for (int i=0; i < m; ++i) {
      for (int j=0; j < p; ++j) {
        for (int k=0; k < n; ++k) {
          ret[i][j] = (ret[i][j] + data[i][k] * rhs[k][j]) % M;
        }
      }
    }
    return ret;
  }
  std::vector<T> const& operator[](size_t n) const { return data[n]; }
  std::vector<T> & operator[](size_t n) { return data[n]; }
  std::vector<std::vector<T> > data;
 private:
  static int const M = 10007;
};

template <typename T>
Matrix<T> pow(Matrix<T> mat, long long int n) {
  int m = mat.rows();
  Matrix<T> ret(m, m);
  for (int i=0; i < m; ++i) ret[i][i] = 1;  // identity matrix
  while (n > 0) {
    if (n & 1) ret = ret * mat;
    mat = mat * mat;
    n >>= 1;
  }
  return ret;
}

8.28.2011

Lexical cast in C++ standard

C++標準での文字列<=>数値変換

boost::lexical_cast と同等の処理をC++標準で実現する。
ただしエラーは考慮しない。

・ジェネリック版

#include <sstream>

template <typename T>
T LexicalCast(char const* src) {
  std::istringstream is(src); T x; is >> x; return x;
}
template <typename T>
T LexicalCast(std::string const& src) {
  return LexicalCast<T>(src.c_str());
}
template <typename T, typename U>
T LexicalCast(U src) {
  std::ostringstream os; os << src; return os.str();
}

#define INT(a) LexicalCast<int>(a)
#define STR(a) LexicalCast<std::string>(a)

・省コード版

#include <sstream>

int INT(std::string src) { std::istringstream is(src); int x; is >> x; return x; }

template <typename T>
std::string STR(T src) { std::ostringstream os; os << src; return os.str(); }

・使用例

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  cout << INT("01234") << endl;  // 1234
  string s = STR(56789);
  reverse(s.begin(), s.end());
  cout << s << endl;  // 98765
  cout << INT(s) + 1 << endl;  // 98766
  cout << STR(0)[0] << STR(9)[0] << endl;  // 09
  return 0;
}

8.27.2011

Developing GAE/P with Eclipse

Eclipse 上での Google App Engine/Python の開発

・セットアップはこちらを参照。
http://www.gesource.jp/weblog/?p=1704

「PyDev: Google App Engine」プロジェクトを作ることと、デバッグ設定
 モジュール:デフォルトでは「C:\Program Files\Google\google_appengine\dev_appserver.py」
 引数:「${project_loc}/src」
が必要。

・アップロードは、ツールバーの「Deploy App Engine Project」ではうまくいかず。
 「src」フォルダを右クリックし、「PyDev: Google App Engine」-「Upload」で配信できた。

Starting Google App Engine

Google App Engine の利用開始

導入手順のメモ。

1. 初期登録

・Google App Engine ホームページ
http://code.google.com/intl/ja/appengine/

・登録ページへ移動し、Google アカウントでサインイン
https://appengine.google.com/

image 「Create Application」を押下。
image 携帯電話の認証が必要となる。
国(Japan)およびキャリア(DoCoMo等)を選択し、
ユーザー名(アドレスの@より前の部分)を指定して
「Send」を押下。
image 送信に失敗すると、このような画面となる。
携帯電話側で、「google.com」からの着信を許可すること。
image 携帯電話に送られたメールに書かれているコードを入力し、
「Send」を押下。
image いよいよアプリの登録。
アプリケーションID(Application Identifier)は、ユニークなものを指定する必要がある。

以下の文字を使用し、6~30文字とすること。
 ・英小文字
 ・数字
 ・ハイフン(ただし先頭・末尾は不可)
一度決めたら変更はできない。

タイトル(Application Title)を入力し、利用同意書を許諾して
「Create Application」を押下。
image 無事に作成できたら、このような画面が表示される。

 

2. 開発ツールの入手

・Python 2.x系の入手
http://www.python.org/download/

・Google App Engine SDK の入手
http://code.google.com/intl/ja/appengine/downloads.html

image プラットフォームに応じて、
Google App Engine SDK for Python をダウンロード。
image Windows の場合。
「Next」を押下。
image チェックを付けて「Next」を押下。
image インストールパス、オプションを指定して「Next」を押下。
image 「Install」を押下。
image 「Run Launcher」を選択するとランチャが起動する。
「Finish」を押下。
image ランチャを起動するとこのような画面。
image まずは「File」-「Create New Application…」を実行。
image アプリケーション名と作業ディレクトリを指定し、
「Create」を押下。
image アプリを選択し、「Run」ボタンを押下するとローカルでWebサーバが立ち上がる。
image 「Browse」ボタンで画面の確認、「Deploy」ボタンでサーバへのアップロードができる。
image 配信(Deploy)にはGoogleアカウントの認証が必要。
アップロードの状況は別ウィンドウに表示。

ここまでの作業で、晴れてサーバ側に「Hello world!」が表示されるようになる。

・Google Plugin for Eclipse の入手
http://code.google.com/intl/ja/eclipse/

Eclipse 上でダウンロードサイトを指定すればよい。
「Help」-「Install New Software...」でサイト名に「http://dl.google.com/eclipse/plugin/バージョン」とする。
例えばHELIOSならば、http://dl.google.com/eclipse/plugin/3.6

参考:
http://techblog.ecstudio.jp/tech-tips/freewebsite-with-google-app-engine.html