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!