6.28.2011

Glancing at the code of 'bitarray'

Python: bitarray パッケージ

bitarray のメインモジュールは以下の2つ。

・__init__.py

インポート

from _bitarray import _bitarray, bits2bytes, _sysinfo
ローカルな関数の定義
def _btree_insert(tree, sym, ba):
def _mk_tree(codedict):
def _check_codedict(codedict):
クラス定義
class bitarray(_bitarray):
クラス関数(一部)
    def decode(self, codedict):
        """decode(code)

Given a prefix code (a dict mapping symbols to bitarrays),
decode the content of the bitarray and return the list of symbols."""
        _check_codedict(codedict)
        return self._decode(_mk_tree(codedict))

    def encode(self, codedict, iterable):
        """encode(code, iterable)

Given a prefix code (a dict mapping symbols to bitarrays),
iterates over iterable object with symbols, and extends the bitarray
with the corresponding bitarray for each symbols."""
        _check_codedict(codedict)
        return self._encode(codedict, iterable)

    def search(self, x, limit=-1):
        """search(x[, limit])

Given a bitarray x (or an object which can be converted to a bitarray),
returns the start positions of x matching self as a list.
The optional argument limits the number of search results to the integer
specified.  By default, all search results are returned."""
        return self._search(bitarray(x), limit)

・bitarray.c

Python.hのインクルード

#include "Python.h"
グローバル変数
typedef struct {
    PyObject_VAR_HEAD
    char *ob_item;
    Py_ssize_t allocated;
    idx_t nbits;
    int endian;
    PyObject *weakreflist;   /* List of weak references */
} bitarrayobject;

static PyTypeObject Bitarraytype;
スタティックな関数(ごくごく一部)
static void
setbit(bitarrayobject *self, idx_t i, int bit)
{
    char *cp, mask;

    mask = BITMASK(self->endian, i);
    cp = self->ob_item + i / 8;
    if (bit)
        *cp |= mask;
    else
        *cp &= ~mask;
}
インストール
/*********************** Install Module **************************/

PyMODINIT_FUNC
init_bitarray(void)
{
    PyObject *m;

    Bitarraytype.ob_type = &PyType_Type;
    BitarrayIter_Type.ob_type = &PyType_Type;
    m = Py_InitModule3("_bitarray", module_functions, 0);
    if (m == NULL)
        return;

    Py_INCREF((PyObject *) &Bitarraytype);
    PyModule_AddObject(m, "_bitarray", (PyObject *) &Bitarraytype);
}

http://pypi.python.org/pypi/bitarray

6.26.2011

Code coverage in Python

Python: コード網羅率の可視化ツール

Python における Code coverage ツールは現時点において以下の2種類である。
インストールコマンドと共に記す。
 ・Code coverage (coverage.py)  => easy_install coverage
 ・trace2html (trace2html.py)  => easy_install trace2html

後者の方がより明解なHTMLで表示されるので、こちらを採用する。

・ヘルプ

   1: Usage: trace2html.py [options]
   2:  
   3: Utility to generate HTML test coverage reports for python programs
   4:  
   5: Example usage
   6: -------------
   7:  
   8: Use trace2html to directly compute the coverage of a test suite by
   9: specifying the module you are interested in::
  10:  
  11:   $ trace2html.py -w my_module --run-command ./my_testrunner.py
  12:   $ firefox coverage_dir/index.html
  13:  
  14: Or you can collect coverage data generated with trace.py::
  15:  
  16:   $ /usr/lib/python2.4/trace.py -mc -C coverage_dir -f counts my_testrunner.py
  17:  
  18: Write a report in directory 'other_dir' from data collected in 'counts'::
  19:  
  20:   $ trace2html.py -f counts -o other_dir
  21:   $ firefox other_dir/index.html
  22:  
  23:  
  24:  
  25: Options:
  26:   -h, --help            show this help message and exit
  27:   -f COVERAGE_FILES, --coverage-file=COVERAGE_FILES
  28:                         Use the content of a trace file
  29:   -o REPORT_DIR, --output-dir=REPORT_DIR
  30:                         Directory to store the generated HTML report. Defaults
  31:                         to 'coverage_dir'
  32:   -s CSS, --with-css-stylesheet=CSS
  33:                         Use an alternative CSS stylesheet
  34:   -t, --self-test       Run the tests for trace2html
  35:   -v, --verbose         Set verbose mode on (cumulative)
  36:   -r, --run-command     Collect coverage data by running the given python
  37:                         script with all trailing arguments
  38:   -b BLACKLIST_MODS, --blacklist-module=BLACKLIST_MODS
  39:                         Add a module to the black list
  40:   -B BLACKLIST_DIRS, --blacklist-dir=BLACKLIST_DIRS
  41:                         Add a directory to the black list
  42:   -w WHITELIST_MODS, --whitelist-module=WHITELIST_MODS
  43:                         Add a module to the white list
  44:   -W WHITELIST_DIRS, --whitelist-dir=WHITELIST_DIRS
  45:                         Add a directory to the white list

基本的な構文は、
 trace2html.py –w Coverageを計測したいモジュール名 [-w モジュール名] –r ユニットテストモジュールのパス
といった塩梅。

・実行例

   1: > trace2html.py -w shogi.state -w shogi.piece -r .\test_state.py
   2: Testing...
   3: .....
   4: ----------------------------------------------------------------------
   5: Ran 5 tests in 5.373s
   6:  
   7: OK
   8: report written to: カレントディレクトリ\coverage_dir\index.html

すると、カレントディレクトリに「coverage_dir」というディレクトリが作成され、配下に計測結果のHTMLが格納される。
image

画面を遷移すると、ソースコードの各行ごとに処理された回数が表示され、未処理の行は赤く表示される。
image

参考:
http://pypi.python.org/pypi/trace2html
http://lab.hde.co.jp/2008/07/pythonunittestcodecoverage-1.html

Bitboards/bitsets in Python (installing .egg file)

Python: ビットボード(またはビットセット)の実装

bitarray パッケージを利用すればよい。
Windows環境におけるセットアップ手順は以下のとおり。

1. setuptools のインストール

以下のURLからexeファイルをダウンロードし実行。(たとえば、setuptools-0.6c11.win32-py2.7.exe
http://pypi.python.org/pypi/setuptools

image 「次へ」

image インストール先が正しいことを確認し、「次へ」

image 「次へ」

image 「完了」

2. bitarray パッケージのインストール

以下のURLからeggファイルをダウンロード。(たとえば、bitarray-0.3.5-py2.7-win32.egg
http://pypi.python.org/pypi/bitarray/

・コマンドプロンプトから、「easy_install eggファイル名」を実行するだけ (easy_install URLでも可とのこと)

   1: >easy_install bitarray-0.3.5-py2.7-win32.egg
   2: Processing bitarray-0.3.5-py2.7-win32.egg
   3: creating e:\python\python27\lib\site-packages\bitarray-0.3.5-py2.7-win32.egg
   4: Extracting bitarray-0.3.5-py2.7-win32.egg to e:\python\python27\lib\site-packages
   5: Adding bitarray 0.3.5 to easy-install.pth file
   6:  
   7: Installed e:\python\python27\lib\site-packages\bitarray-0.3.5-py2.7-win32.egg
   8: Processing dependencies for bitarray==0.3.5
   9: Finished processing dependencies for bitarray==0.3.5
  10:  
  11: >

3. bitarray のテスト

・ユニットテスト

>>> import bitarray
>>> bitarray.test()
bitarray is installed in: E:\Python\Python27\lib\site-packages\bitarray-0.3.5-py2.7-win32.egg\bitarray
bitarray version: 0.3.5
2.7.1 (r271:86832, Nov 27 2010, 18:30:46) [MSC v.1500 32 bit (Intel)]
...........................................................................................
----------------------------------------------------------------------
Ran 91 tests in 3.016s

OK
<unittest.runner.TextTestResult run=91 errors=0 failures=0>
>>> 

・簡単なテスト(論理和、論理積)

>>> from bitarray import bitarray
>>> a = bitarray(10)
>>> a.setall(False)
>>> b = bitarray(10)
>>> b.setall(True)
>>> a
bitarray('0000000000')
>>> b
bitarray('1111111111')
>>> a[1] = True
>>> b[2] = False
>>> a
bitarray('0100000000')
>>> b
bitarray('1101111111')
>>> a & b
bitarray('0100000000')
>>> a | b
bitarray('1101111111')
>>> 


参考:
http://d.hatena.ne.jp/SumiTomohiko/20070609/1181406701
http://peak.telecommunity.com/DevCenter/setuptools

Using multi-byte characters in a Python module

Python: マルチバイト文字列をソースコードに使用する

コメントも含め、Python でマルチバイト文字列をソースに含む場合は、1行目か2行目に以下のようなコメントを書く必要がある。

・UTF-8 を指定する場合

   1: # -*- coding: utf-8 -*-

これはEmacsと互換性のある書き方。
表記は、以下の正規表現にマッチしていればよい。

coding[:=]\s*([-\w.]+)

参考:Python クックブック 第2版 A.2章

6.24.2011

Windows: Run commands!

Windows: 「ファイル名を指定して実行」覚書

マイナーなコマンドのメモ。おそらくWindows XP以降で使用可能。

logoff        ログオフ

shell:personal        マイドキュメントを開く
shell:system        システムフォルダ(system32)を開く
shell:system\drivers\etc\        system32\drivers\etc 配下を開く(パスを「\」で連結可能)

rundll32.exe user32.dll,LockWorkStation        コンピュータのロック

参考:
http://mypchell.com/guides/34-guides/69-156-useful-run-commands
http://suika.fam.cx/~wakaba/wiki/sw/n/shell

6.17.2011

MS Office 2003: SKU011.CAB could not be found

ファイルSKU011.CABからの読み込みに失敗しました

Office 2003 をインストールした後、ユーザの初回アクセス時や
パッチ適用時などに以下のようなメッセージが出現する場合がある。

エラー1309.ファイル(インストールメディアのパス)SKU011.CABからの読み込みに失敗しました。
ファイルが存在するかどうか、また、このファイルへのアクセス権があるかどうかを確認して下さい。

インストールメディアを再度挿入するか、
レジストリの値を変更し、該当のOfficeモジュールのキャッシュを
強制的に無効とすることで解決する。

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Office\11.0\Delivery\{XX-XXXX-XXXX-XXXX-XXXXXXXXXXXX}\CDCache
のデータを「0」に設定
(XXの部分は16進数によるDownloadCode)

参考:
http://www.sku011cab.com/
http://ginolog.blogspot.com/2010/11/ms-office.html
http://support.microsoft.com/kb/896866/en-jp

6.14.2011

C++: Union-Find data structure

Union-Find木の実装

こちらの習作、というかそのまんま。
http://www.prefield.com/algorithm/container/union_find.html

   1: #include <vector>
   2: #include <algorithm>
   3:  
   4: struct UnionFind {
   5:   std::vector<int> data;
   6:   UnionFind(int size) : data(size, -1) {}
   7:   bool Union(int x, int y) {
   8:     if ((x = Root(x)) == (y = Root(y))) return false;
   9:     if (data[y] < data[x]) std::swap(x, y);
  10:     data[x] += data[y]; data[y] = x;
  11:     return true;
  12:   }
  13:   bool IsSame(int x, int y) { return Root(x) == Root(y); }
  14:   int Root(int x) { return data[x] < 0 ? x : data[x] = Root(data[x]); }
  15:   int Rank(int x) { return -data[Root(x)]; }
  16: };
rank がアンダーフローしたらどうなる?

6.12.2011

Vrapper – Eclipse plugin for vi-like editing

vi キーバインドの Eclipse プラグイン

Vrapper をインストールすれば、Eclipse でvi(Vim)ライクのエディタを利用することができる。
Eclipse のインストール場所に「http://vrapper.sourceforge.net/update-site/stable」を追加して実行すればよい。

eclipse のコマンドとの競合を防いだり、新しいコマンドを登録するためには「~/.vrapperrc」を作成する。

少なくともWindows Vistaでは「.vrapperrc」という名前でファイルが作れなかったので、一旦他の名前のファイルを作成してからコマンドプロンプトから「move」した。(保存先は %homedrive%%homepath% 配下)

参考:
http://vrapper.sourceforge.net/home/ (本家)
http://d.hatena.ne.jp/yuroyoro/20100218/1266477264
http://d.hatena.ne.jp/basyura/20100913/p1

6.11.2011

How to disable window resizing in Firefox

Firefox: ウィンドウサイズ変更の無効化

Firefox の以下のオプション設定で、Webページのスクリプトによるウィンドウサイズ変更を無効化できる。

・メニュー => オプション => コンテンツ => JavaScript を有効にする - 詳細設定
image_thumb9

「ウィンドウの移動または大きさの変更」のチェックを外せばよい。

C++: Initialize a multidimensional array with std::fill()

STL の std::fill() アルゴリズムによる多次元配列の初期化

こちら(http://mogproject.blogspot.com/2011/05/c-vector.html)同様、
マクロ+テンプレートで実現。

   1: #define FILL(ptr, value) FILL_((ptr), sizeof(ptr) / sizeof(value), (value))
   2: template <typename T>
   3: void FILL_(void* ptr, size_t size, T value) {
   4:   std::fill((T*)ptr, (T*)ptr + size, value);
   5: }

・使用例

   1: int a[3][3];
   2: char c[2][2][2];
   3: FILL(a, 5);
   4: FILL(c, 'X');
   5:  
   6: for (int i=0; i<3; ++i) for (int j=0; j<3; ++j)
   7:   std::cout << a[i][j] << " ";
   8: std::cout << std::endl;  // "5 5 5 5 5 5 5 5 5 "
   9: for (int i=0; i<2; ++i) for (int j=0; j<2; ++j) for(int k=0; k<2; ++k)
  10:   std::cout << c[i][j][k] << " ";
  11: std::cout << std::endl;  // "X X X X X X X X "

6.10.2011

How to flush memory on an Oracle instance

Oracle: メモリフラッシュのコマンド

性能検証を行う前など、ライブラリ・キャッシュやデータベース・バッファ・キャッシュをクリアしたい場合、
以下のコマンドをSYSDBA権限で発行すれば、インスタンスを再起動する必要はない。

・ライブラリ・キャッシュなど共有プールのフラッシュ

   1: ALTER SYSTEM FLUSH SHARED_POOL ;

・データベース・バッファ・キャッシュのクリア ※Oracle 10g以降のみ

   1: ALTER SYSTEM FLUSH BUFFER_CACHE ;

(注意) 同一インスタンス上で実行中の全てのSQLに影響が発生する。(結果レコードが返されないなど)

参考:
http://www.shift-the-oracle.com/dba_tips_optimizer.html

6.05.2011

C++: Compilation error 'unresolved overloaded function type' in std::transform

C++: transform 関数での unresolved overloaded function type コンパイルエラー

G++で以下のコードをコンパイルするとエラーが発生する。

   1: #include <iostream>
   2: #include <deque>
   3: #include <algorithm>
   4: #include <cmath>
   5:  
   6: using namespace std;
   7:  
   8: int main() {
   9:   deque<double> radians(1, 3.14), sines(1);
  10:  
  11:   transform(radians.begin(), radians.end(), sines.begin(), sin);
  12:   cout << sines[0] << endl;
  13: }

・エラー

   1: error: no matching function for call to 'transform(std::deque<double>::iterator, std::deque<double>::iterator, std::deque<double>::iterator, <unresolved overloaded function type>)'

 

sin関数は、G++の「cmath」において以下のようにオーバーロードされている。

   1: inline float
   2: sin(float __x)
   3:  
   4: inline long double
   5: sin(long double __x)
   6:  
   7: template<typename _Tp>
   8:   inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value, 
   9:       double>::__type
  10:   sin(_Tp __x)

一方、transformのテンプレート引数では、テンプレート関数のsinについて推論することができない。そのため、どのsin関数を使えばいいのか分からない状態となってしまい、エラーが発生する。

以下のように、sin関数の型を指定すれば動作するようになる。

   1: transform(radians.begin(), radians.end(), sines.begin(), (double(*)(double))sin);

参考:
http://2bangai.net/read/c582add4b3ec2e8b617ee5e942e57d68c6418eac78102818fd04c3cf09e42d80/301

6.04.2011

C++: Printing all elements in a vector using operator

C++: vector の全要素の出力

「<<」演算子のオーバーロードによって vector の出力を簡単にできるようにする。

   1: #include <iostream>
   2: #include <vector>
   3:  
   4: template <typename T>
   5: std::ostream & operator<<(std::ostream & stream, std::vector<T> & v) {
   6:   stream << "[";
   7:   for(typeof(v.begin()) i = v.begin(); i != v.end(); ++i) {
   8:     if (i != v.begin()) { stream << ", "; }
   9:     stream << *i;
  10:   }
  11:   stream << "]";
  12:   return stream;
  13: }
  14:  
  15: int main() {
  16:   std::vector<int> iv;
  17:   std::vector<char> cv;
  18:  
  19:   for (int i = 0; i < 5; ++i) {
  20:     iv.push_back(i);
  21:     cv.push_back('A' + i);
  22:   }
  23:  
  24:   std::cout << iv << std::endl;
  25:   std::cout << cv << std::endl;
  26:  
  27:   return 0;
  28: }

・出力結果

   1: [0, 1, 2, 3, 4]
   2: [A, B, C, D, E]