11.30.2015

C++/Python: Writing Custom Converters in Boost.Python

C++/Python: Boost.Python でカスタムコンバーターを作る

 

C++ のクラスを Python で扱うとき、std::pair などのクラスはデフォルトでは型変換が行われない。自分でコンバーターを書く必要がある。

 

以下はコードの例。C++11のラムダ式を利用したら綺麗にまとまった。

#include <boost/python.hpp>
#include "your_code.hpp"


namespace yourmodulename {
  namespace py = boost::python;

  /*
   * Converter for result set (std::vector of std::pair => pylist of pytuple)
   */
  namespace detail {
    template <typename T, typename U>
    struct pair_vector_to_tuple_list {
      static PyObject* convert(std::vector<std::pair<T, U> > const& ps) {
        py::list ret;
        for (auto it: ps) ret.append(py::make_tuple(it.first, it.second));
        return py::incref(ret.ptr());
      }

      static PyTypeObject const* get_pytype() { return &PyList_Type; }
    };
  }

  template <typename T, typename U>
  void expose_pair_vector_to_tuple_list() {
    py::to_python_converter<std::vector<std::pair<T, U> >, detail::pair_vector_to_tuple_list<T, U>, true>();
  }

  /*
   * Converter for list parameter (pylist => std::vector)
   */
  template <typename T>
  void expose_pylist_to_vector() {
    typedef std::vector<T> VT;

    auto convertible = [](PyObject* obj_ptr) -> void* { return PySequence_Check(obj_ptr) ? obj_ptr : NULL; };

    auto construct = [](PyObject* obj_ptr, py::converter::rvalue_from_python_stage1_data* data) {
      VT* storage = new (reinterpret_cast<py::converter::rvalue_from_python_storage<VT>*>(data)->storage.bytes) VT();
      for (py::ssize_t i = 0, l = PySequence_Size(obj_ptr); i < l; ++i) {
        storage->push_back(py::extract<typename boost::range_value<VT>::type>(PySequence_GetItem(obj_ptr, i)));
      }
      data->convertible = storage;
    };

    py::converter::registry::push_back(convertible, construct, py::type_id<VT>());
  }

}


BOOST_PYTHON_MODULE(yourmodulename) {
  using namespace boost::python;
  using namespace yourmodulename;

  // expose converters
  expose_pair_vector_to_tuple_list<int, double>();
  expose_pylist_to_vector<int>();

  // expose classes
  ...
}

なかなかに魔力を吸い取られそうなコードだ。

 

 

Related Posts

 

References

11.27.2015

Top N Sorter in Python

Python: トップNソートの実装

 

ソート可能な iterable に対して、降順の上位 N件のソート結果を取得したい。

heapq を使えば効率が良さそうだ。

 

コード

import heapq


class TopNSorter(object):
    def __init__(self, limit):
        self._heap = []
        self.limit = limit

    def insert(self, item):
        if len(self._heap) == self.limit:
            heapq.heappushpop(self._heap, item)
        else:
            heapq.heappush(self._heap, item)

    def result(self):
        h = self._heap[:]
        buf = []
        while h:
            buf.insert(0, heapq.heappop(h))
        return buf

 

実行例

>>> s = TopNSorter(5)
>>> s.result()
[]
>>> s.insert(10)
>>> s.result()
[10]
>>> s.insert(20)
>>> s.result()
[20, 10]
>>> s.insert(10)
>>> s.result()
[20, 10, 10]
>>> s.insert(5)
>>> s.result()
[20, 10, 10, 5]
>>> s.insert(30)
>>> s.result()
[30, 20, 10, 10, 5]
>>> s.insert(15)
>>> s.result()
[30, 20, 15, 10, 10]
>>> s.insert(10)
>>> s.result()
[30, 20, 15, 10, 10]
>>> s.insert(25)
>>> s.result()
[30, 25, 20, 15, 10]
>>> s.insert(1)
>>> s.result()
[30, 25, 20, 15, 10]

 

Related Posts

11.22.2015

Finding Community Structure in a Big Graph

C++: ビッググラフにおけるコミュニティ抽出のメモ

 

手法

ネットワークにおけるコミュニティ抽出 (グラフのクラスタリング) にはいくつかの手法がある。

こちらを参照 => R seminar on igraph

スパースなグラフに対する Non-overlapping で最も高速なのは、貪欲アルゴリズムを用いた手法 (O(n (log n)^2))。
今回はこちらを採用。

 

実装

R であれば igraph – Network analysis software に既に実装がある。

Python の NetworkX では過去に議論された形跡が見られるものの、取り込まれる見込みは薄そうだ。

GraphX には、もちろん無い。

今回はとにかく消費メモリを節約したかったので、論文作者本人が公開している C++ の実装を使うことにする。

 

ビルド

上記の URL で公開されているソースコードをビルドする。(ライセンスが GPL なので注意)

コンパイルオプションなどが今日のコンパイラに追随していなかったので、若干の修正を要した。

  • Makefile (-fforce-mem オプション削除)
@@ -8,7 +8,7 @@

 # compiler name and flags
 CCC = g++
-CCFLAGS = -O3 -fomit-frame-pointer -funroll-loops -fforce-mem -fforce-addr -fexpensive-optimizations
+CCFLAGS = -O3 -fomit-frame-pointer -funroll-loops -fforce-addr -fexpensive-optimizations

 # loader flags
 LDFLAGS =
  • fastcommunity_mh.cc (iostream.h -> iostream, string.h 追加)
@@ -71,12 +71,13 @@
 //
 ////////////////////////////////////////////////////////////////////////

-#include <iostream.h>
+#include <iostream>
 #include <fstream>
 #include <string>
 #include "stdlib.h"
 #include "time.h"
 #include "math.h"
+#include "string.h"

 #include "maxheap.h"
 #include "vektor.h"
  • maxheap.h (iostream.h -> iostream, namespace std 追加)
@@ -40,7 +40,8 @@
 #if !defined(MAXHEAP_INCLUDED)
 #define MAXHEAP_INCLUDED

-#include <iostream.h>
+#include <iostream>
+using namespace std;

 /*   Because using this heap requires us to be able to modify an arbitrary element's
        data in constant O(1) time, I use to tricky tactic of having elements in an array-
  • vektor.h (iostream.h -> iostream)
@@ -30,7 +30,7 @@
 #if !defined(vektor_INCLUDED)
 #define vektor_INCLUDED

-#include <iostream.h>
+#include <iostream>

 #if !defined(vektor_INCLUDED)
 #define vektor_INCLUDED

その後、ディレクトリ内で make コマンドを行えば、実行ファイル FastCommunityMH が生成される。

 

実行

まずは有名(?)な空手クラブの派閥争いのデータで動作確認してみる。

$ curl -O http://tuvalu.santafe.edu/~aaronc/hierarchy/karate.pairs
$ ./FastCommunity_GPL_v1.0.3/FastCommunityMH -f ./karate.pairs -l firstRun

以下の 2ファイルが成果物としてカレントディレクトリに出力される。

FASTCOMMUNITY_INFERENCE_ALGORITHM
START-----:     Sun Nov 22 01:54:13 2015
---FILES--------
D_IN------:     ./
D_OUT-----:     ./
F_IN------:     karate.pairs
F_JOINS---:     karate-fc_firstRun.joins
F_INFO----:     karate-fc_firstRun.info
---NET_STATS----
MAXID-----:     34
NUMNODES--:     34
NUMEDGES--:     78
---MODULARITY---
MAXQ------:     0.383136
STEP------:     32
EXIT------:     Sun Nov 22 01:54:13 2015
-1      -1      -0.0498028      0
17      6       -0.0376397      1
6       7       -0.0139711      2
7       1       -0.00147929     3
5       1       0.0177515       4
11      1       0.0490631       5
27      30      0.0612262       6
30      34      0.0784845       7
24      34      0.0946746       8
28      34      0.111111        9
26      25      0.123192        10
25      32      0.145874        11
13      4       0.157709        12
22      2       0.16905 13
31      9       0.180227        14
9       33      0.196992        15
10      3       0.208169        16
18      2       0.219181        17
12      1       0.229372        18
8       4       0.239563        19
4       3       0.253369        20
14      3       0.269149        21
2       3       0.289448        22
29      32      0.29931 23
32      34      0.311144        24
23      33      0.320513        25
19      33      0.329553        26
21      33      0.338264        27
33      34      0.349359        28
16      34      0.362837        29
15      34      0.375986        30
1       20      0.380671        31
20      3       0.383136        32

この *.joins ファイルを追っていけば、Q値の推移、検出されたクラスタの状態を把握することができる。

-c オプション(特定ステップ時点の状態をファイルに出力)や -v --v オプション(詳細表示)も約に立つが、その度に全データの再計算が行われてしまうので、ビッググラフでは扱いづらい。

ノード数が増えたら、*.joins ファイルを解析するためのツールを作る必要があるだろう。

 

ビッググラフへの適用

300万ノード、1300万エッジのグラフに対して、上記のプログラムを実行してみた。

期待どおりメモリ使用量は 10GB 以内とかなり少なく抑えられている。

しかし、並列処理には向いていないアルゴリズムなので、それなりの実行時間はかかりそう。
おそらく、完了までは10日程度を要するであろう。

11.11.2015

Python: How to Avoid 'multiprocessing' TypeError on Exit

Python: multiprocessing TypeError の回避方法

 

Python 2.6 でテスト (python setup.py test) をしたとき、最後に以下のようなエラーが出ることがある。

Error in atexit._run_exitfuncs:
Traceback (most recent call last):
  File "/opt/python/2.6.9/lib/python2.6/atexit.py", line 24, in _run_exitfuncs
    func(*targs, **kargs)
  File "/opt/python/2.6.9/lib/python2.6/multiprocessing/util.py", line 258, in _exit_function
    info('process shutting down')
TypeError: 'NoneType' object is not callable

回避策は、以下に従い setup.py に記述をすること。

try:
    # Work around a traceback on Python < 2.7.4 and < 3.3.1 
    # http://bugs.python.org/issue15881#msg170215
    import multiprocessing  # noqa: unused
except ImportError:
    pass

コメントに noqa を付けると、pep8 などのチェックを回避できる。

11.08.2015

Universal Use of 'subprocess' Module in Python

Python: バージョン・OS 透過的な subprocess モジュールの利用

 

Python のバージョン (2.6 / 2.7 / 3.2 / 3.3 / 3.4 / 3.5) や、OS環境 (Linux / Mac / Windows /CygWin) に依存せずに外部コマンドを実行するコードを書きたい。

 

ワークアラウンド

なかなか一筋縄ではいかない。

Python3.2 + POSIX環境 では、コマンドラインを bytes で渡してはいけない

以下のようなエラーが出る。

>>> import subprocess
>>> subprocess.call(b'echo')
TypeError: expect bytes or str, not int

subprocess モジュールの中で、args が文字列かどうかを判定するときに bytes である場合の考慮が不足しており、bytes の個々の要素(int)に対して分割が行われてしまうため。

対策は、コマンドラインをリストとして渡せばよい。以下のように対策する。(args が bytes である場合)

import sys

if sys.version_info[:2] == (3, 2):
    args = [args]

 

Python3 + Windows環境では、コマンドラインと環境変数のキー・値を bytes で渡してはいけない

以下のようなエラーが出る。

>>> import subprocess
>>> subprocess.call(b'cmd /C echo x')
    needquote = (" " in arg) or ("\t" in arg) or not arg
TypeError: argument of type 'int' is not iterable

bytes に対する in オペレーションに失敗しているが、これといった対策が見当たらない。bytes で渡すのをやめて、str で渡すことにする。(その場合、コマンドライン文字列のエンコードは指定できない)

import sys
import six
if six.PY2 or sys.platform != 'win32':
    # この場合だけ bytes にエンコード

env の指定についても同様。キーだけではなく、値も bytes が許容されていないので注意。

 

POSIX環境 + shell=True のとき、args をリストとして渡してはいけない

リストの2番目以降の引数が評価されない。

>>> import subprocess
>>> subprocess.call(['echo', '3'], shell=True)

0

ワークアラウンドとしては、subprocess.list2cmdline を使って適切な文字列を生成する。

import sys
import subprocess
if shell and sys.platform != 'win32':
    args = [subprocess.list2cmdline(args)]

 

外部コマンドについて

 

sleep

Windows 7 以降は「timeout」というコマンドが標準装備されているが、Python から実行すると標準入力が奪われてしまい不都合だった。


結局、Python の time モジュールを使うのが一番簡便だという結論に。

import subprocess
subprocess.call('python -c "import time;time.sleep(2)"')

 

プロセステーブルの取得

11.04.2015

Python: Terminal I/O Assessment in CygWin

Python: CygWin 環境におけるターミナル I/O 周りの調査

環境

  • OS: Windows Server 2012 R2 日本語版
  • CygWin: 2.873 (64bit)
  • Python: 2.7

 

目的

Python 上で以下の操作が可能か調べる。

  • ターミナルのエンコーディングの自動判別
  • ターミナル画面のクリア
  • ターミナル上のキー入力の検知

 

バリエーション

調査したバリエーションは以下 5 種類。

環境フロントエンドシェルPythonビルドエンコーディング
1 cmd.exe - Windows cp932
2 cmd.exe CygWin bash Windows cp932
3 cmd.exe CygWin bash CygWin UTF-8
4 MinTTY CygWin bash Windows UTF-8
5 MinTTY CygWin bash CygWin UTF-8

 

環境情報

いくつかの方法で情報を取得。(要 import platform,os,sys,locale)

#メソッド環境1環境2環境3環境4環境5
a platform.system() Windows Windows CYGWIN_NT-6.3 Windows CYGWIN_NT-6.3
b os.name nt nt posix nt posix
c os.environ.get('TERM') None cygwin cygwin xterm xterm
d os.environ.get('LANG') None ja_JP.UTF-8 ja_JP.UTF-8 ja_JP.UTF-8 ja_JP.UTF-8
e sys.stdin.isatty() True True True False True
f sys.stdin.encoding cp932 cp932 UTF-8 None UTF-8
g sys.stdout.isatty() True True True False True
h sys.stdout.encoding cp932 cp932 UTF-8 None UTF-8
i locale.getpreferredencoding() cp932 cp932 UTF-8 cp932 UTF-8

明快な判定方法は無いが、sys.stdout.encoding -> 環境変数LANG -> locale.getpreferredencoding() の順に信頼すれば良さそうに思える。

 

画面クリア

以下のメソッドの挙動を確認。(要 import subprocess)

#メソッド環境1環境2環境3環境4環境5
a subprocess.call('cls', shell=True) OK OK - - -
b subprocess.call('cmd /c cls', shell=True) - - OK - -
c subprocess.call('clear', shell=False) - - - - -
d subprocess.call(['echo', '-en', r'\ec'], shell=False) - - OK - OK
e subprocess.call(r'echo -en "\ec"', shell=False) - OK - OK -

なかなか判定条件が悩ましい。

 

キー入力の取得

msvcrt による取得が可能かどうかと、tty、curses が使えるかどうか調査。

#メソッド環境1環境2環境3環境4環境5
a msvcrt.getch() OK OK - - -
b tty.setraw(0) - - OK - OK
b curses.screen#getch() - - OK - OK

環境4 に限っては、1文字単位でキー入力を取得する手段が無いという結論となった。

 

11.03.2015

How to Clear Terminal Screen in Various Systems

ターミナルの画面を消去する方法

 

特別なインストールなしで実現したい。

  • POSIX互換環境(Linux/Unix/Mac): clear
  • Windows
    • コマンドプロンプト (cmd.exe): cls
    • CygWin (2011以前): cmd /c cls
    • CygWin (mintty): echo -en "\ec"

CygWin の闇は深い。

 

 

References

11.02.2015

calendar-cli - Command-line Interface for Google Calendar

calendar-cli - Googleカレンダーを操作するためのコマンドライン・インターフェース

 

Google カレンダーをコマンドラインで操作するニーズがあったので、元々あったスクリプトを CLI として作り変えた。

これを使えば、コマンドラインで

  • 1日単位のサマリーの表示
  • 予定の登録

が、できる。

 

コード

 

セットアップ

Google の API を使う都合上、導入までに少し手間がかかる。

1. API プロジェクトの作成とclient_secret.json の入手
  • Google Developers Console を開く (要Googleアカウントのログイン)
  • 新規プロジェクトを作成
  • Calendar API を有効化
    • API と認証 -> API -> Google Apps API -> Calendar API -> API を有効にする
  • OAuth 2.0 認証のクライアントを作成 (デバイス種別は Other)
    • API と認証 -> 認証情報 -> OAuth 同意画面 -> サービス名 (calendar-cli でよい) を入力し保存
    • API と認証 -> 認証情報 -> 認証情報を追加 -> OAuth 2.0 クライアント ID
      -> アプリケーションの種類: その他として保存
  • 画面から client_secret.json をダウンロードし保存
    • 実際のファイル名はもっと長い可能性あり

認証情報 calendar cli

 

2. calendar-cli のインストール

pip で導入可能。環境によっては要sudo。

$ pip install calendar-cli
$ calendar-cli --version
calendar-cli 0.1.3
$ calendar-cli -h
Usage:
  calendar-cli [options]
                        Print a summary of events on the calendar.

  calendar-cli setup  [--read-only --credential ]
                        Generate a credentials file from the client secret.
                        You need a web browser to proceed.

  calendar-cli create [--date <YYYYMMDD> --start <HHMM> --end <HHMM>
                       --credential <credential_path>] <summary>
                        Create an event onto the calendar.


Options:
  --version             show program's version number and exit
  -h, --help            show this help message and exit
  --calendar=CALENDAR   set calendar id to CALENDAR (default:primary)
  --date=YYYYMMDD       set date to YYYYMMDD in the setup/create command
                        (default:today)
  --credential=CREDENTIAL
                        set credential path to CREDENTIAL
                        (default:/Users/user/.credentials/calendar-cli.json)
  --read-only           create a read-only credential file in the setup
                        command (default: False)
  --start=HHMM          set start time in the create command
  --end=HHMM            set end time in the create command
  --debug               enable debug logging (default: False)

 

3. 認証用ファイルの作成

calendar-cli でセットアップ用のコマンドを用意した。
client_secret.json の部分は、手順1でダウンロードした適切なパスに書き換えること。

$ calendar-cli setup client_secret.json

一度ブラウザ上で OAuth 認証が行われた後、~/.credentials/calendar-cli.json として認証情報が保存される。

 

使い方

 

1. サマリーの表示
  • 今日の予定を表示 (デフォルトのカレンダー)
    $ calendar-cli
  • 指定した日の予定を表示 (デフォルトのカレンダー)
    $ calendar-cli --date 12/6

    日付として指定可能なフォーマットは以下。年を省略すると現在の年で補完される。
    • 20151206 (YYYYmmdd)
    • 2015-12-6, 2015-12-06 (YYYY-m-d)
    • 2015/12/6, 2015/12/06 (YYYY/m/d)
    • 12-6-2015, 12-06-2015 (m-d-YYYY)
    • 12/6/2015, 12/06/2015 (m/d/YYYY)
    • 12-6, 12-06 (m-d)
    • 12/6, 12/06 (m/d)
  • 指定したカレンダーの今日の予定を表示
    $ calendar-cli --calendar xxxxxx@group.calendar.google.com
    [終日] 有給休暇 (James LaBrie)
    [11:00-12:00] ○○様来社 (John Petrucci)
    [14:00-15:00] [外出] △△訪問 (John Myung)
    [17:30-22:00] □□勉強会 (Jordan Rudess)
    [17:30-23:00] ☆☆飲み会 (Mike Mangini)

 

2. イベントの登録
  • 当日または翌日の 10:30 に 15分のイベントを作成
    $ calendar-cli create --start 10:30 内容
    イベントを作成しました: 2015-11-02 月 [10:30-10:45] 内容
    現在時刻が 10:30 以前であれば当日、以降であれば翌日にイベントが作成される。
    時刻指定のフォーマットは以下。
    • 1030 (HHMM)
    • 9:30, 09:30 (H:M)
  • 当日または翌日に 12:00-13:00 のイベントを作成
    $ calendar-cli create --start 12:00 --end 13:00 内容
    イベントを作成しました: 2015-11-02 月 [12:00-13:00] 内容
    現在時刻が 12:00 以前であれば当日、以降であれば翌日にイベントが作成される。
  • 日付を指定してイベントを作成
    $ calendar-cli create --date 12/6 --start 12:00 --end 13:00 内容
    イベントを作成しました: 2015-12-06 日 [12:00-13:00] 内容
    --date オプションのフォーマットはサマリー表示と同じ。
  • 終日イベントを作成
    $ calendar-cli create --date 12/12 内容
    イベントを作成しました: 2015-12-12 土 [終日] 内容

 

Related Posts

11.01.2015

Type Assertion Decorator in Python

Python: 型チェックのデコレータ

 

Python は動的型付けの言語だが、抽象的なライブラリを書こうとすればどうしても型チェックの需要が生じる。

  • PyContracts は非常に良さそうなライブラリだが、独自のクラスには対応していない模様。
  • なので、車輪の再発明と知りつつも自前で実装してみた。

 

コード

 

インストール

mog-commons-python の一部として実験的にリリースしている。

pip install mog-commons

inspect#getcallargs をバックポートしたので、Python 2.6 / 2.7 / 3.2 / 3.3 / 3.4 / 3.5 の全てで動く。

 

使い方

関数定義と一緒に @types デコレータを指定するだけ。

  • 1個以下の可変長引数として、戻り値の型を指定 (省略も可能)
  • 名前付き引数として、パラメータ名=型 と制約を定義
  • ListOf, DictOf などを使えば、コレクションの要素の型もチェックできる
  • チェックに失敗したら、TypeError が発生
>>> from mog_commons.types import *

>>> @types(float, x=int, y=float, z=ListOf(int))
... def f(x, y, z):
...     return x * y + sum(z)
...

>>> f(1, 2, 3)
TypeError: y must be float, not int.

>>> f(1, 2.0, 3)
TypeError: z must be list(int), not int.

>>> f(1, 2.0, [3, 4])
9.0

戻り値だけのチェックも可能。

>>> @types(bool)
... def g(x):
...     return x
...

>>> g(3)
TypeError: must return bool, not int.

>>> g(True)
True

簡便のため、Python バージョンに透過的な String, Unicode, Option も定義した。
可変長引数、名前付き引数をチェックする場合は以下のようにする。

>>> @types(args=VarArg(String), kwargs=KwArg(int))
... def h(*args, **kwargs):
...     return 'ok'
...

>>> h('abc', 5, a=123, b=456)
TypeError: args must be tuple((basestring|str)), not tuple.

>>> h('abc', 'def', a=123, b=456)
'ok'

実際にどの要素の型が異なっているのか、までは表示していない。

 

これで、Typesafe Python にまた一歩近づいた。