TekTekBLOG

pypyで何も考えずにpythonを高速化する

2011-05-01T07:21:00.003+09:00

Python公式のCPythonよりも高速という噂のpypyがPython2.7.1相当の機能を実装したというので、その実行速度を測定しました。

■インストール（OSX）

pypyのインストールは非常に簡単で、本家からbzipをダウンロードして解凍したらできあがりです。


$ tar xjvf pypy-1.5-osx64.tar.bz2
$ cd pypy-c-jit-43780-b590cf6de419-osx64
$ ls
LICENSE  README  bin  include  lib-python lib_pypy site-packages

binの中にpypyというコマンドがありますので、それを実行すると起動します。


$ bin/pypy

Python 2.7.1 (b590cf6de419, Apr 30 2011, 03:30:00)
[PyPy 1.5.0-alpha0 with GCC 4.0.1] on darwin
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``how to construct the blackhole
interpreter: we reuse the tracing one, add lots of ifs and pray''
>>>>

>が３つではなく４つ出てくるところが、公式CPythonよりも強そうですよね！

■実測

実際にPython標準のパフォーマンス測定ツールtimeitで、実行速度を比較してみました。

比較のため、OSX上のCPython2.6.1, 2.7,1とpypyを使いました。

まずは単純に配列を作る処理。


-------  CPython 2.6.1
>>> import timeit
>>> t = timeit.Timer(stmt="[x*x for x in xrange(1000)]")
>>> print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
184.11 usec/pass

-------  CPython 2.7.1
>>> import timeit
>>> t = timeit.Timer(stmt="[x*x for x in xrange(1000)]")
>>> print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
153.30 usec/pass

------- pypy 1.5
>>>> import timeit
>>>> t = timeit.Timer(stmt="[x*x for x in xrange(1000)]")
>>>> print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
120.95 usec/pass

CPython2.7は2.6よりもだいぶ速いですが、それをさらにpypyが上回る速度です。

次に、集合(set)の中の検索


-------  CPython 2.6.1
>>> t = timeit.Timer(setup="a=set([x*x for x in xrange(100)])", stmt="[(x in a) for x in xrange(100)]")
>>> print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
23.41 usec/pass

-------  CPython 2.7.1
>>> t = timeit.Timer(setup="a=set([x*x for x in xrange(100)])", stmt="[(x in a) for x in xrange(100)]")
>>> print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
19.59 usec/pass

-------  pypy1.5
>>>> t = timeit.Timer(setup="a=set([x*x for x in xrange(100)])", stmt="[(x in a) for x in xrange(100)]")
>>>> print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
11.97 usec/pass

これも結果は同様に圧倒的にpypyが高速。(2.7の２倍に迫る速度！）

こんなに簡単に高速化できるなら、どこかで試しに使ってみたくなりますよね。

Ajaxを補足するためのPythonによる手軽なマルチスレッド処理

2011-02-08T20:39:00.007+09:00

Webアプリの開発で、重い処理はAjaxで別途処理して取得するという手段が取れない場合があります。

「画面の一部で矢印がぐるぐる回って待たせるのではなく、本当に一瞬で全部表示したい」

などの場合です。

そんなときにお手軽に使えるテクニックとして、サーバー処理のマルチスレッドによる並列化があります。
Pythonのマルチスレッドでは、高度なCPUの並列処理はできませんが（グローバルインタプリタロックと言います）、少なくともI/O待ちの間別の処理を流す程度の事は可能です。[参考]
その特徴を生かして、Webアプリのレスポンスを速めることができます。

これを使う場面ですが、たとえば、以下のようなものがあります。

この画面はうちの会社で作っている特許分析WEBアプリのBiz Cruncherというもので、特許の詳細な内容を表示しているところです。

特許の閲覧というのは企業知財部では古来から「手めくり」と呼ばれ、いかに速く大量の特許の内容を把握するかに心血を注ぎます。
そのため、図などは一瞬で見れるべきだし、電子的な画面であろうと、一瞬で次々表示されなければストレスを感じるものです。

そういう場合は付属情報はAjax化で別リクエストにするにしても、必須の要素だけは泣く泣く１リクエストに押し込んで、極限まで速度を向上させる必要があります。

たとえば、上の特許詳細画面では時間のかかる処理として、テキストマイニング、画像の生成、詳細テキスト（長文）の取得、引用情報・経過情報の取得　etc.をそれこそ一瞬で行う必要がありました。

改良前はこの表示に2.8秒かかっていたのですが、それでも不満ということで、冒頭のマルチスレッド化を行って0.7秒にまで縮めることができました。

具体的には以下の関数 call_async を使います。

import threading
def call_async(target, args=None, kwargs=None):
    u"""
    関数非同期呼び出しツール。
    関数を別スレッドで呼び出して、その後結果を取得できます。

    #使用例
    r = call_async(f,args=(5,))
        #ここで別の処理を片付けます。
    r["thread"].join()  #スレッドが終わるのを待ちます。
    if "result" in r:
        print "RESULT", r["result"]
    else:
        print "ERROR", str(r["exception"])
    """
    res = {}
    def f(*inargs, **inkwargs):
        try:
            inargs[-1]["result"] = target(*(inargs[:-1]), **inkwargs)
        except Exception, e:
            inargs[-1]["exception"] = e
    res["thread"] = threading.Thread(target=f, args=(args+(res,)), kwargs=kwargs)
    res["thread"].start()
    return res

この関数を使うと、関数呼び出しを別スレッドにしながら、その返り値を取得することもできます。
使用方法は上記関数のコメント内にありますが、以下のように、先に遅い処理を実行開始しておき、平行してその他の処理を済ませたあとで、ゆっくりと結果を取得します。


    #使用例 slow1～3という遅い処理の関数がある場合

    #まず冒頭で遅い処理を別スレッドで実行開始しておきます。
    r1 = call_async(slow1,args=(5,))     #遅い処理1を開始！
    r2 = call_async(slow2,args=("ABC","DEF"))     #遅い処理2を開始！
    r3 = call_async(slow3,args=([1,2,3,4]))     #遅い処理3を開始！

        #ここでその他の処理を片付けます。

    r1["thread"].join()  #スレッドが終わるのを待ちます。
    r2["thread"].join()  #スレッドが終わるのを待ちます。
    r3["thread"].join()  #スレッドが終わるのを待ちます。

    if "result" in r1:   #slow1の結果を使う処理
        print "RESULT 1", r1["result"]
    else:
        print "ERROR 1", str(r1["exception"])

    if "result" in r2:   #slow2の結果を使う処理
        print "RESULT 2", r2["result"]
    else:
        print "ERROR 2", str(r2["exception"])

    if "result" in r3:   #slow3の結果を使う処理
        print "RESULT 3", r3["result"]
    else:
        print "ERROR 3", str(r3["exception"])

こうすることで、I/O待ちの発生する処理をいくつも並列で実行でき、実行時間の効果的な短縮を実現できます。

こうした手段としてPython標準のmultiprocessingが検討にあがりますが、あれはより高度な分散処理用ですので、関数の結果を取得しようとすると、とたんに大仰なものになります。

また、もちろんですが、この秒数の短縮で効果的なのはJavascriptの最適化もあるわけです。
それをした後に、さらにどうしてもサーバー側も高速化しないといけない場合は、このお手軽なマルチスレッド化も考慮するとよいと思います。

PythonのUnicode->UTF-8変換はSJISやEUCへの変換よりもちょっと速い

2010-12-04T16:45:00.003+09:00

想像していた通りですが、UnicodeをUTF-8に変換するのは、SJISやEUCに変換するよりもちょっと速いことがわかった。


>>> import timeit
>>> def unicode_henkan(c):
...     t = timeit.Timer("a.encode('%s')" % c, "a=u'\u3042'*10000")
...     print t.timeit(number=1000)
... 
>>> unicode_henkan("utf-8")
0.075012922287
>>> unicode_henkan("sjis")
0.19597196579
>>> unicode_henkan("eucjp")
0.146716833115
>>> unicode_henkan("cp932")
0.21554517746
>>>

ちなみに、timeitは与えられた計測対象のプログラムを内部でpythonのプログラムとして解釈する際に、文字コードのことをあまり考えてくれないようなので、


t = timeit.Timer("a.encode('%s')" % c, "a=u'あ'*10000")

のように書くとUnicodeErrorになります。

関数呼び出しをタプル形式にして遅延させる関数

2010-09-14T11:16:00.002+09:00

関数呼び出しをタプルの情報にして保存するしくみを作った。
これを使えばWEBアプリでリクエストをまたいで関数呼び出しを遅延させることができるようになります。
関数呼び出しをタプル形式にして、memcacheなどに保存しておき、次に来たときに本当に呼び出したり。

# coding: utf-8
import inspect
import imp

def freeze_func(func, *args, **kwargs):
    u"""
    関数呼び出しを保存可能なタプル形式に変換する。
    """
    m = inspect.getmodule(func)
    return m.__name__, func.__name__, args, kwargs

def __importer(m, path):
    a = imp.find_module(m[0], path)
    b = imp.load_module(m[0], *a)
    if len(m) > 1:
        return __importer(m[1:], b.__path__)
    else:
        return b

def _importer(modname):
    modname = modname.split(".")
    return __importer(modname, None)



def unfreeze_func(info):
    u"""
    タプル形式で保存された関数呼び出しを関数に復元して実行する。
    """
    b = _importer(info[0])
    f = getattr(b, info[1])
    args = info[2]
    kwargs = info[3]
    return f(*args, **kwargs)

if __name__ == "__main__":
    import re
    info = freeze_func(re.sub, r"[A-Za-z]", "*", "5-3-1 Asakusabashi")
    print info     # -> ('re', 'sub', ('[A-Za-z]', '*', '5-3-1 Asakusabashi'), {})
    print unfreeze_func(info)  # -> "5-3-1 ************"

Djangoでblogっぽいのを作ったので移動します

2008-05-24T03:51:00.003+09:00

Djangoでblogっぽいのを作ったので移動します。RSSも吐いておりますので宜しくお願いします。
→新TekTekBlog

移動の理由:
1. このBloggerでは一切のJavascriptなどが貼れないので不便。アクセス解析の類も一切無理。
2. データのエクスポート機能もないので、書き溜めても外部に効率的に持ち出せない。
3. 自分で作って自分で設置するほうが面白い。

はてブのホットエントリをなんとなーく分類するPythonスクリプトサンプル

2008-05-23T02:04:00.005+09:00

昨日作った、Ward法のPythonバインディングを使って、はてなブックマークのホットエントリをなんとなーく分類するPythonスクリプトのサンプルを書いてみた。

サンプルプログラムは例によって、CodeReposに置きました。

試しに今の時点(5/23 深夜2:06)のホットエントリを分類した結果は以下のような感じです。
なんとなーく、分類されているような雰囲気。
もっと各エントリの情報を取得すれば精度は上がるんでしょうが、今の所はホットエントリのRSS一枚から取得できる情報(今の所タイトル中の名詞と、タグの単語)だけを使って分類しています。

----- 以下、その結果 -----

Ward法のPythonバインディングを作りました。

2008-05-22T02:00:00.005+09:00

先日から作っていたクラスタリング(Ward法)のPython用バインディングを作りました。Pythonから一応つないで使えるようになりました。

ソースコードの取得とインストール。


$ svn export http://svn.coderepos.org/share/lang/cplusplus/misc/clustercpp
$ cd clustercpp/python/wardcluster
$ python setup.py build_ext --swig-cpp
$ sudo python setup.py install

サンプル実行。
引き続きディレクトリclustercpp/python/wardcluster内で以下を実行してください。


$ python sample.py
1 + 0 => 4 ( 0.244948974278 )
3 + 2 => 5 ( 0.412310562562 )
5 + 4 => 6 ( 4.80645253132 )
$

ちなみに、今上で動いたsample.pyは以下のようなスクリプトで、４本のベクトルをクラスタリングしています。

from wardcluster import Matrix, DoubleVec, Ward

m = Matrix()
m.append(DoubleVec([1.0, 2.0, 3.0]))
m.append(DoubleVec([1.1, 2.2, 2.9]))
m.append(DoubleVec([0.1, 1.2, 5.0]))
m.append(DoubleVec([0.3, 1.0, 5.3]))

w = Ward()

history = w.cluster(m, 4) #この4ってのは、ベクトルの本数

for h in history:
    print h.index1, "+" , h.index2, "=>", h.newindex , "(", h.distance ,")"

メモ--------
* setuptoolsを使ったオシャレなモジュールにするのは断念。（swigの結果ファイルとの調整が難しかった）
* swigのtypemap?とか、そういうのはむずかしくて分からないので、めんどくさいインターフェース。
* あくまで実験的なものですよ。
* 相変わらずswigを理解できていない。
* 今回ベクトルの集合を表すために内部でstd::vector<std::vector<double> >を使うようにしたので、パフォーマンスが落ちています。（将来もとのstd::vector<double>*を使って渡す方式に戻したいものです。。。）

C++のWard法->g++のオプションで驚異的な高速化

2008-05-20T00:02:00.003+09:00

先日から作っているクラスタリングアルゴリズムの一種Ward法のプログラムを今日もいじっていた。

こまごまとしたことをしたのだが、コンパイルオプションをいじると、恐ろしく速くなった。

まず、比較のために、前回の結果。

件数   処理時間(s)    そのうち初期行列作成時間
--------------------------------------------
2352   33.432          6.39

そこに、今回以下のコンパイルオプションをつけてみた。(ちなみにOSX10.4&Intelな白MacBookの環境です。）

g++ -O3 -ffast-math -funroll-loops -Wall -fno-common -march=nocona -o ward -I../include ward.cpp

その結果、以下のように高速化された。

件数   処理時間(s)    そのうち初期行列作成時間
--------------------------------------------
2352   12.628          1.06

シャアではないが、通常の３倍以上の速さである。
C++恐るべし。
分散処理とか考えるのはやはりC++で肝心の部分を書いて、その後なんだろうなと実感しました。

Python -> C++への移植でどれぐらい速くなったか

2008-05-16T22:52:00.008+09:00

先日、Pythonで実装したWard法をC++で再実装し、比較してみた。

まずは、前回のPython版の処理時間を再掲。

件数   処理時間(s)    そのうち初期行列作成時間
--------------------------------------------
196     0.677          0.334
392     2.158          1.356
588     4.636          3.073
1176    18.071         12.088
2352    79.09          49.507

これをC++に移植すると、以下の処理時間に短縮される。


件数   処理時間(s)    そのうち初期行列作成時間
--------------------------------------------
196     0.216          0.04
392     0.842          0.17
588     1.627          0.39
1176    7.086          1.57
2352   33.432          6.39

今回は、まずは行列作成部分に、できるだけC++で可能なチューニングを施してある。
樹形図作成部分は、あまり最適化していない。
標準のstd::mapとかstd::vectorを使用しており、特別な数値計算用ライブラリなどは一切使っていない。
また、コンパイル時の様々なコンパイルオプションでの最適化もまだ行っていない。

C++(C)のいい所は、メモリの使い方などをダイレクトに想像しながらチューニングが行える所だろう。
今回も、３重ループの効率化を行うだけで、ここまで処理時間が短くなった。

しかし、作っていて気づいたのは、最適化を意識しないでC++を書くと、Pythonとたいして変わらない処理時間だったことだ。
その証拠に、上の表での処理時間の短縮分のほとんどは、今回意識して最適化を図った行列作成部分のものである。

次は、実際の樹形図作成部分がネックになっているので、この部分をより速くしていきたいと思う。

今回のソースはcodereposに置いておきました。

行列×行列さえ一瞬でできれば、文書のクラスタリングも一瞬でできそう

2008-05-15T01:00:00.004+09:00

Ward法をここ数日試してみて、十分速くなったのだが、ここまでくるといろいろ思う事がある。

1. 最終的に今ネックになっているのは、一番最初の行列×行列の計算である。
2. その演算であれば、分散処理での高速化が十分研究されている。
3. 最初は樹形図をつくるところがネックかと思っていたが、そうでないのは驚きである。
4. dict使いまくりの富豪プログラミングはアルゴリズムの試作に便利。

ということで、例えば分散処理で行列×行列を一瞬で計算できるようになれば、直前のエントリのクラスタリングアルゴリズムで1000文書であろうとものの数秒で分類できるということになる。

このクラスタリングの計算方法をC++で書き直せば、もっともっと速くなるはずで、たとえばweb経由でアクセスがあった瞬間に分類アルゴリズムを走らせることもできるだろう。

樹形図をどこでちょんぎるかのさじ加減は別途研究の必要があるが。

Ward法さらにキャッシュを効かせて高速に

2008-05-15T00:11:00.008+09:00

さらに昨日の続き。

行列の各行の最小距離成分をキャッシュするようにしてみた。
この改造によって、昨日O(N**2)でネックとなっていた、距離表からの最小値の探索がほぼO(N)になったことになる。
さらにパフォーマンスは向上し、以下のようになった。

件数   処理時間(s)    そのうち初期行列作成時間
--------------------------------------------
196     0.677          0.334
392     2.158          1.356
588     4.636          3.073
1176    18.071         12.088
2352    79.09          49.507

昨日、おとといに比べると、だいぶ速くなった。例えば昨日は588件の処理に19秒かかっていたのが、今日は4.6秒！
しかし、計算は速くなったものの、今度は実は最初の行列作成に大半の時間を使われていることがわかる。

ここが速くなれば、あるいは、行列の作成時間を気にしなくていい状況とかであれば、十分使い物になるパフォーマンスになってきた。
C/C++にはとうていかなわないでしょうけど、Pythonでも工夫次第でいろいろがんばれるものだ。

以下、今日の改造版のソース。

#!/usr/local/python25/bin/python
# _*_ coding: utf-8 _*_
# Copyright (C)  2007 Ayukawa Hiroshi
import sys
import time
from operator import itemgetter
from collections import defaultdict
from itertools import repeat, groupby
from math import sqrt

def distmatrix_by_dict(vectors):
    """
    上三角部分のみの距離表を作ります(ベクトルがdict型のsparseベクトルの場合)
    返り値  (距離, ベクトル番号1, ベクトル番号2) の列
    """
    mat = defaultdict(lambda: defaultdict(float))
    for i in range(len(vectors)):
        dist = []
        for j in range(i):
            d = 0.0
            for k in set(vectors[i].keys()) & set(vectors[j].keys()): #ユークリッド距離
                d += (vectors[i].get(k, 0.0) - vectors[j].get(k, 0.0))**2
            dist.append((j, sqrt(d)))
        mat[i] = dafaultdict(float, dist)
    return mat

def distmatrix_by_list(vectors):
    """
    上三角部分のみの距離表を作ります(ベクトルが通常のリストの場合)
    返り値  (距離, ベクトル番号1, ベクトル番号2) の列
    """
    mat = defaultdict(lambda: defaultdict(float))
    for i in range(1,len(vectors)):
        v = vectors[i]
        dist = []
        for j in range(i):
            dist.append((j, sqrt(sum([(x[0]-x[1])**2 for x in zip(v, vectors[j])])))) #ユークリッド距離
        mat[i] = defaultdict(float, dist)
    return mat

def _initcache(mat):
    """
    距離表の各行ごとの最小値をキャッシュする配列を初期化します。
    """
    cache = []
    for i in sorted(mat.keys()):
        cache.append((i, min(((v, i, j) for j,v in mat[i].iteritems()))))
    return dict(cache)

class _Rap:
    """
    パフォーマンス測定用クラス
    """
    def __init__(self):
        self.t = 0
    def b(self):
        self.start = time.time()
    def e(self):
        self.t += time.time() - self.start

def cluster(vectors, distfunc=distmatrix_by_list):
    """
    クラスタリング（ウォード法）
    返り値 クラスタ結合履歴配列
    """
    rap0 = _Rap()
    rap00 = _Rap()

    #距離表の用意
    rap0.b()
    mat = distfunc(vectors)
    rap0.e()
    
    #距離表の最小値キャッシュを初期化する
    rap00.b()
    cache = _initcache(mat)
    rap00.e()

    size = len(vectors)    #全体のサイズ
    sizes = list(repeat(1, size)) # 各クラスタのサイズ

    #ノードを結合した履歴を保存する配列（この列を最終的に返します）
    hist = [dict(
            joined=None, #joined: この回で結合したインデックス
            dist=0.0,     #dist: この回で結合したインデックス間の距離
            newid=None,  #newid: この回で新設されたインデックス
            )]
    rap1 = _Rap()
    rap2 = _Rap()
    nextnodenum = size   #次に使うクラスタ番号
    kieta = set() #消えた行番号の保存用

    #size-1回繰り返して結合していきます。
    while len(hist) < size:
        #最小距離のものを選ぶ
        rap1.b()
        dist, q, p = min(cache.values())  # p < q
        rap1.e()

        #消えるもの集合を更新
        kieta.add(p)
        kieta.add(q)

        #高速化のための事前計算
        pairsize = sizes[p]+sizes[q]
        r = mat[q][p]
        obj = mat[nextnodenum]
        sp = sizes[p]
        sq = sizes[q]

        #距離の計算しなおし
        rap2.b()
        #キャッシュから、今回消えるものをあらかじめ排除
        if p in cache: cache.pop(p)
        if q in cache: cache.pop(q)
        tmpdist = [] #新ノードからの最小距離を求めるための一時記憶場所
        for i in xrange(nextnodenum):
            if i in kieta: continue #すでに消えているなら何もしない

            #距離の計算  Ward法
            if i < p:
                obj[i] = ((sp+sizes[i])*mat[p][i]+(sq+sizes[i])*mat[q][i]-sizes[i]*r)/float(pairsize+sizes[i])
            elif p < i and i < q:
                obj[i] = ((sp+sizes[i])*mat[i][p]+(sq+sizes[i])*mat[q][i]-sizes[i]*r)/float(pairsize+sizes[i])
                mat[i].pop(p)  #今後使わなくなる成分の消去
            else:
                obj[i] = ((sp+sizes[i])*mat[i][p]+(sq+sizes[i])*mat[i][q]-sizes[i]*r)/float(pairsize+sizes[i])
                mat[i].pop(p)  #今後使わなくなる成分の消去
                mat[i].pop(q)  #今後使わなくなる成分の消去

            #キャッシュ更新
            if i in cache:
                if obj[i] < cache[i][0]: #新ノードとi番目の距離がより近い場合はi行目のキャッシュを置き換えます。
                    cache[i] = (obj[i], nextnodenum, i)
                elif mat[i] and (p in cache[i][1:] or q in cache[i][1:]):
                    cache[i] = min(((v, i, j) for j,v in mat[i].iteritems()))
                if not mat[i]: #i行が空になってたら、iのキャッシュは不要。matからもけずる
                    cache.pop(i)
                    mat.pop(i)
            elif not mat[i]: mat.pop(i)
            tmpdist.append((obj[i], i))
        if p in mat: mat.pop(p)  #今後使わなくなる成分の消去
        if q in mat: mat.pop(q)  #今後使わなくなる成分の消去

        #新ノードからの最小距離をキャッシュに記録
        if tmpdist:
            mindist = min(tmpdist)
            cache[nextnodenum] = (mindist[0], nextnodenum, mindist[1])

        sizes.append(pairsize)  #新クラスタのサイズデータを格納
        rap2.e()
        #履歴情報に今回の結合結果を格納
        hist.append(dict(
                joined=(p,q),  
                dist=dist,
                newid=nextnodenum,
                ))
        nextnodenum += 1 #次のクラスタID    

    print "rap0", rap0.t
    print "rap00", rap00.t
    print "rap1", rap1.t
    print "rap2", rap2.t
    
    return hist

def main(nottest=False):
    """
    引数  nottest  パフォーマンステスト用フラグ Falseの場合はテストのために、結果出力しません。
    """
    ids = []     # データラベル格納用
    vectors = [] # ベクトル格納用
    for line in sys.stdin:  #標準入力からベクトルを読む
        data = line.strip().split("\t")
        ids.append(data[0])
        vectors.append(map(float, data[1:]))

    #クラスタリング実行
    hist = cluster(vectors)            

    if nottest:  #出力処理
        for c, h in enumerate(hist):
            j = h["joined"]
            if not j: continue
            i = "(%s+%s)" % (ids[j[0]], ids[j[1]])
            ids.append(i)
            print c, ":", h["dist"], ":", i

if __name__ == "__main__":
   import optparse
   
   parser = optparse.OptionParser(u"""
   Ward法によるクラスタリング。
   """)
   parser.add_option("-t", "--test", dest="test", help=u"パフォーマンステスト実行", default=False, action="store_true")
   (options, args) = parser.parse_args()

   if options.test:
       #パフォーマンステスト
       import hotshot, hotshot.stats
       prof = hotshot.Profile("cluster.prof")
       prof.runcall(main)
       prof.close()
       stats = hotshot.stats.load("cluster.prof")
       stats.strip_dirs()
       stats.sort_stats('time', 'calls')
       stats.print_stats(20)
   else:
       #通常実行
       main(True)

Ward法再実装で少し速くなった

2008-05-14T02:03:00.004+09:00

PythonでWard法によるクラスタリング
Ward法のパフォーマンスと分散処理のための考察

このシリーズの続き。
プログラムを書き直し、真っ当な行列的データを用意したところ、ずいぶん速くなり、588件でも19秒程度となった。（1100件でも2分程度なので、ずいぶんと自分が想定している実用化に近づいたと思う。）

しかし、真っ当な行列データにすると、今度は最小距離の探索に９割の時間を取られるようになったため、ここを改造すべきと強く思う。

ここまでくれば、常に行列の成分のソート情報をなんらか記憶しておけばいいように思うのだが、そのソート情報の維持にはまたコストがかかるというジレンマ。

今は可変長の行列として、pythonのdefaultdict(lambda: defaultdict(float))を使っている。これで定義した簡易行列クラスは非常に便利なのでそんなにシビアでない計算の目的にはよく使っている。可変長＆メモリ節約というのがとくにすばらしい。

これがC++であったらどうするべきであろうか。
こうした細かい計算アルゴリズムの王道としては最初から使用するメモリをまとめて最小限確保しておき、その上でメモリを上書きしながら計算して行くべきか。
それとも今回のPythonでの実装にならってSTLを使って map<size_t, map<size_t, double>*>* などとするべきか。ああ、こういう場合shared_ptrにするべきなんだっけ、、、。ここはいつも覚えてないので参考書を読み直さなくては。
はたまたboostになんかいいのないかと見ていたら、いつの間にかboostのコンテナ系が増えている！調査しなければ。
うーん、前途多難。

以下、今日の改造版。

#!/usr/local/python25/bin/python
# _*_ coding: utf-8 _*_
# Copyright (C)  2007 Ayukawa Hiroshi
import sys
import time
from operator import itemgetter
from collections import defaultdict
from itertools import repeat, groupby
from math import sqrt

def distmatrix_by_dict(vectors):
    """
    上三角部分のみの距離表を作ります(ベクトルがdict型のsparseベクトルの場合)
    返り値  (距離, ベクトル番号1, ベクトル番号2) の列
    """
    for i in xrange(len(vectors)):
        for j in xrange(i):
            dist = 0.0
            for k in set(vectors[i].keys()) & set(vectors[j].keys()): #ユークリッド距離
                dist += (vectors[i].get(k, 0.0) - vectors[j].get(k, 0.0))**2
            yield (sqrt(dist), i, j)

def distmatrix_by_list(vectors):
    """
    上三角部分のみの距離表を作ります(ベクトルが通常のリストの場合)
    返り値  (距離, ベクトル番号1, ベクトル番号2) の列
    """
    for i in xrange(len(vectors)):
        for j in xrange(i):
            dist = sum([(x[0]-x[1])**2 for x in zip(vectors[i], vectors[j])]) #ユークリッド距離
            yield (sqrt(dist), i, j)

def minmatrix(mat, size):    
    d = min((min(((v, j) for j,v in mat[i].iteritems())), i) for i in mat.iterkeys() if mat[i])
    return (d[0][0], d[1], d[0][1])

def cluster(vectors, distfunc=distmatrix_by_list):
    """
    クラスタリング（ウォード法）
    返り値 クラスタ結合履歴配列
    """
    #距離表の用意
    mat = defaultdict(lambda : defaultdict(float))
    for d in distfunc(vectors):
        mat[d[1]][d[2]] = d[0]        

    size = len(vectors)    #全体のサイズ
    sizes = list(repeat(1, size)) # 各クラスタのサイズ

    #ノードを結合した履歴を保存する配列（この列を最終的に返します）
    hist = [dict(
            joined=None, #joined: この回で結合したインデックス
            dist=0.0,     #dist: この回で結合したインデックス間の距離
     newid=None,  #newid: この回で新設されたインデックス
            )]

    class Rap:
        def __init__(self):
            self.t = 0
        def b(self):
            self.start = time.time()
        def e(self):
            self.t += time.time() - self.start
    rap1 = Rap()
    rap2 = Rap()
    nextnodenum = size   #次に使うクラスタ番号
    #size-1回繰り返して結合していきます。
    kieta = set()
    while len(hist) < size:
        #最小距離のものを選ぶ
        rap1.b()
        dist, q, p = minmatrix(mat, nextnodenum)  # p < q
        rap1.e()

        #消えるもの集合を更新
        kieta.add(p)
        kieta.add(q)

        #高速化のための事前計算
        pairsize = sizes[p]+sizes[q]
        r = mat[q][p]
        obj = mat[nextnodenum]
        sp = sizes[p]
        sq = sizes[q]

        #距離の計算しなおし
        rap2.b()
        for i in xrange(nextnodenum):
            if i in kieta: continue #すでに消えているなら何もしない

            #距離の計算  Ward法
            if i < p:
                obj[i] = ((sp+sizes[i])*mat[p][i]+(sq+sizes[i])*mat[q][i]-sizes[i]*r)/float(pairsize+sizes[i])
            elif p < i and i < q:
                obj[i] = ((sp+sizes[i])*mat[i][p]+(sq+sizes[i])*mat[q][i]-sizes[i]*r)/float(pairsize+sizes[i])
                mat[i].pop(p)  #今後使わなくなる成分の消去
            else:
                obj[i] = ((sp+sizes[i])*mat[i][p]+(sq+sizes[i])*mat[i][q]-sizes[i]*r)/float(pairsize+sizes[i])
                mat[i].pop(p)  #今後使わなくなる成分の消去
                mat[i].pop(q)  #今後使わなくなる成分の消去
        if p in mat: mat.pop(p)  #今後使わなくなる成分の消去
        if q in mat: mat.pop(q)  #今後使わなくなる成分の消去
        sizes.append(pairsize)  #新クラスタのサイズデータを格納
        rap2.e()
        #履歴情報に今回の結合結果を格納
        hist.append(dict(
                joined=(p,q),  
                dist=dist,
                newid=nextnodenum,
                ))
        nextnodenum += 1 #次のクラスタID    
    print "rap1", rap1.t
    print "rap2", rap2.t
    
    return hist

def main(nottest=False):
    """
    引数  nottest  パフォーマンステスト用フラグ Falseの場合はテストのために、結果出力しません。
    """
    ids = []     # データラベル格納用
    vectors = [] # ベクトル格納用
    for line in sys.stdin:  #標準入力からベクトルを読む
        data = line.strip().split("\t")
        ids.append(data[0])
        vectors.append(map(float, data[1:]))

    #クラスタリング実行
    hist = cluster(vectors)            

    if nottest:  #出力処理
        for c, h in enumerate(hist):
            j = h["joined"]
            if not j: continue
            i = "(%s+%s)" % (ids[j[0]], ids[j[1]])
            ids.append(i)
            print c, ":", h["dist"], ":", i

if __name__ == "__main__":
   import optparse
   
   parser = optparse.OptionParser(u"""
   Ward法によるクラスタリング。
   """)
   parser.add_option("-t", "--test", dest="test", help=u"パフォーマンステスト実行", default=False, action="store_true")
   (options, args) = parser.parse_args()

   if options.test:
       #パフォーマンステスト
       import hotshot, hotshot.stats
       prof = hotshot.Profile("cluster.prof")
       prof.runcall(main)
       prof.close()
       stats = hotshot.stats.load("cluster.prof")
       stats.strip_dirs()
       stats.sort_stats('time', 'calls')
       stats.print_stats(20)
   else:
       #通常実行
       main(True)

2ちゃんねる Pythonのお勉強 Part26よりParallel Python関係の議論抜粋

2008-05-13T01:23:00.005+09:00

Pythonのお勉強 Part26
からの抜粋。なんともタイムリーなことに、Parallel Pythonが話題になっている。
この議論で288が指摘している事は、やはり的を得ているのではないだろうか。
Python->C/C++という移植で10倍速くなるなんてことは珍しくない。
（例えば、C++からMecabを利用した時の速度は驚異的ですらあるが、Pythonから利用した場合はちょっとのんびりとしたものになってしまう。）
numpyがうまくハマっているPythonスクリプトとかなら別ですけど。

で、以下その議論抜粋です。。。。
---------------------

169 ：デフォルトの名無しさん：2008/05/06(火) 21:31:30
    threadって計算速度の向上に効果ある？
    a = b1 + b2の計算を（a,b1,b2はarray）
    b1とb2をthreadで計算して，
    それぞれ計算終了後に足すというプログラムを作ったんだけど，
    普通にb1とb2をメインスレッドで順番に求めて足した方が早かった．．．

    ちなみにb1とb2の計算はダミーのforループ10000回です． 

244 ：デフォルトの名無しさん：2008/05/10(土) 04:27:34
    >>169
    Parallel Python というパッケージがあるのを知ったので参考までに紹介しとく。
    http://www.parallelpython.com/
    スレッドじゃなく複数プロセスで並列実行する仕組みらしい。
    Python のみで実装されていて非常にシンプルなパッケージ構成になっている。
    マルチコア環境の場合はスレッドモジュール風に使える。
    クラスタ環境では各ノードで計算サーバ（ppserver.py）をしておく仕組みになっている。
    応用プログラムはどちらの環境でも同じにできるっぽい。

    手元の共有メモリマシンで付属サンプル（sum_primes.py）を実行したら下のようになった。
    素数の和を計算するプログラムなのでプロセス間通信はほとんどないけど、
    並列化のオーバヘッドはあるわけで、なかなか良好な結果だと思う。

    並列度，実行時間（秒），速度向上率
    1，　　17.54，　　1.000
    2，　　8.781，　　1.998
    4，　　4.424，　　3.965
    8，　　2.261，　　7.759 

245 ：169：2008/05/10(土) 13:53:14
    >>244
    おおお，サンクス！
    早速いじってみまふ。 

280 ：244：2008/05/10(土) 23:51:28
    引続き Parallel Python をいじってみたんだけども、このシステムはマスタワーカモデルを前提にしているみたいだ。
    つまり、マスタが仕事の集合を持っていて、有限個のワーカに1つずつ仕事を割り当てる。仕事を終えたワーカは
    マスタから新しい仕事をもらって処理する。これを仕事の集合が空になるまで続ける。

    ワーカ間で通信をする機能は提供されていないし、特定のワーカ（たとえば特定のリモートホスト上のppserver.py）に
    特定の仕事を割り当てることもできないっぽい。Parallel Python が有効かどうかは実現したい並列アルゴリズムが
    マスタワーカモデルに適合するかどうかに依る希ガス。 

283 ：デフォルトの名無しさん：2008/05/11(日) 00:40:31
    >>280
    具体的には、どういう用途に使えそうなんですか？ 

285 ：デフォルトの名無しさん：2008/05/11(日) 01:34:00
    >>283
    最も適しているのは並列処理の分野で embarrassingly parallel と呼ばれるカテゴリに属する種々の計算、
    すなわち入力データを複数の独立した部分に分割できて、各部分について他から独立して計算が行なえる
    タイプの用途に適している。
    http://en.wikipedia.org/wiki/Embarrassingly_parallel
    Wikipediaに例があがっている。フラクタル計算とか3DCGのレンダリング（例：レイトレーシング）とか力任せの
    暗号解読とか色々ある。

    並列処理って概して複雑で長時間計算し続ける必要のある応用が多い。そういう応用には C とか Fortran を
    使うことがほとんどなんだけど、きちんと動くようになるまでの開発時間が長くてデバッグがたいへんだったりする。
    そういう並列プログラムの試作（プロトタイピング）に Python が使えたらいいなーと個人的には思っている。

288 ：デフォルトの名無しさん：2008/05/11(日) 09:43:58
    >>285
    PythonでCPU8個使って並列計算するよりCで書いたプログラムの方が速そうだったり。。。

289 ：デフォルトの名無しさん：2008/05/11(日) 09:57:09
    >>288
    何言ってんだ？

290 ：デフォルトの名無しさん：2008/05/11(日) 10:28:52
    >>289
    あ？ヤンのかコラ 


295 ：デフォルトの名無しさん：2008/05/11(日) 14:39:25
    >>285
    自分も並列化するときのプロトタイプとしてPythonの並列環境を使ってみたいと
    考えているんだけれど、今のところプロトタイプとしての感触はどう？

    データ分割の楽な問題ってCとかFORTRANでもOpenMPを注意深く使うだけでも早くなる事が
    多いし、MPIでも慣れれば苦労せずに書けるけれど、そうでない、スレーブ間での通信が必要
    とかうまく分割できないとかそういう問題はMPIでやろうとするとデバッグが(；ﾟдﾟ)
    なことになりがちで、そういう用途にPythonのプロトタイプが役に立つなら素晴らしいと思う
    実はC並列版とそれほど速度とメモリ使用量が変わらないとかなら最高
    C並列版より速ければ神

296 ：デフォルトの名無しさん：2008/05/11(日) 16:53:12
    Parallel Python だけど pp.Server.__scheduler() を適当に書き直せばワーカと仕事の対応（割り当て）を
    ユーザ側で決められそうな希ガス。問題はワーカ間のプロセス間通信。これが一番面倒なところなんで
    自前で実装となると Parallel Python を使ううまみがほとんどない・・・。

    やっぱ MPI の Python バインディングあたりが一番現実的な解かなー。でもなんか気が重いんだなー。
    もっと Python らしく lightweight なソリューションがないかなー。

    >>288
    Python の並列プログラムより C の逐次プログラムの方が速そうってことだよね。
    そういうことは十分（多分頻繁に）あると思われ。

    >>295
    残念ながらまだ並列プログラムのプロトタイプ用途には使えてなくて感触を得るところまでいってない。
    理由は単純で、Python で手軽に並列プログラミングを実現できる道具を見つけられていないから。
    >>209に書いたようにいろいろ試してるんだけどなかなか・・・。

    ただ、個人的には Python を並列化のプロトタイピングに使うのは大いに有望だと思っている。
    プロトタイピングの場合、欲しいのは並列度やデータ量を上げたときの実行時間の変化であって、
    実行速度が多少遅くて実験に時間がかかるとしても知りたいことは分かるはずだから。
    プロセス間通信にソケットを使うとすると、データ量が大きくなれば Python でも C 等と同じぐらいの
    速度が出る（ハズ）。演算量が多い部分に numpy 等の C/Fortran で書かれた数値カーネルを使うことに
    すれば、プロトタイピング用途には十分な速度とメモリ使用量が得られるのではと思う。

Ward法のパフォーマンスと分散処理のための考察

2008-05-13T00:01:00.002+09:00

昨日実装したWard法の処理だが、200件程度なら２秒で終わるが、詳しく調べると、400件で10秒、700件で60秒と、O(n**2)どころか、「もしかしてO(2^n)？！」ぐらいのできであった(T_T)。。。

その99%は距離計算直し対象の発見と選り分けの部分であり、本来のWard法の距離計算の部分は微々たるもの。

今後はこの選り分け対象の部分でちゃんとインデックスの効いた選り分けができるように変更すべきか。

やはり、まずは王道に従って、きちんとした行列データとして距離を持つべきだろう。

作り直しだ。

PythonでWard法によるクラスタリング

2008-05-12T04:29:00.007+09:00

Pythonで、Ward法によるクラスタリング（デンドログラム作成まで）を実装してみた。
参考にしたのは、岡山大学が公開しているこの資料。
（岡山大学の先生ありがとう！）

今回こんな車輪の再発明をしたのは、距離表と呼ばれる行列データを行列のイメージで保存せず、

[(ベクトル1とベクトル2の距離, ベクトル番号1, ベクトル番号2), ...]

という形式のリストにして、距離でソートしておき、そのソート結果を維持したままこのリストを分割、更新していくという方針で作ったらどうかと思ったからです。

196個の19次元の非スパースなデータのデンドログラム作成に2.5秒だからなかなかのパフォーマンスではないだろうか。
CもC++もNumpy系の数値計算ライブラリも使わないでこれだから、いいですねえ。

使い方
読み込むデータファイルをタブ区切りで用意する。
1カラム目はデータの識別用ID文字列、2カラム目以降にベクトルの数値データを記入。
あとはそのデータを標準入力から流し込むだけ。
例
以下のsample.txtを用意する。

A 1.0 1.1 0.2
B 1.1 0.5 0.3
C 3.1 0.5 0.2
D 4.0 1.1 1.2

以下を実行

ayu@~/work/cluster% ./cluster.py < sample.txt 
1 : (B+A)
2 : (D+C)
3 : ((D+C)+(B+A))

最初にBとAを結合し、次にDとCを結合し、最後に(D+C)と(B+A)を結合していることが分かる。

ソースcluster.py

#!/usr/local/Python25/bin/python
# _*_ coding: utf-8 _*_
# Copyright (C)  2007 Ayukawa Hiroshi
import sys
from collections import defaultdict
from itertools import repeat, groupby
from math import sqrt

def distmatrix_by_dict(vectors):
    """
    上三角部分のみの距離表を作ります(ベクトルがdict型のsparseベクトルの場合)
    返り値  (距離, ベクトル番号1, ベクトル番号2) の列
    """
    for i in xrange(len(vectors)):
        for j in xrange(i):
            dist = 0.0
            for k in set(vectors[i].keys()) & set(vectors[j].keys()): #ユークリッド距離
                dist += (vectors[i].get(k, 0.0) - vectors[j].get(k, 0.0))**2
            yield (sqrt(dist), i, j)

def distmatrix_by_list(vectors):
    """
    上三角部分のみの距離表を作ります(ベクトルが通常のリストの場合)
    返り値  (距離, ベクトル番号1, ベクトル番号2) の列
    """
    for i in xrange(len(vectors)):
        for j in xrange(i):
            dist = sum([(x[0]-x[1])**2 for x in zip(vectors[i], vectors[j])]) #ユークリッド距離
            yield (sqrt(dist), i, j)

def cluster(vectors, distfunc=distmatrix_by_list):
    """
    クラスタリング（ウォード法）
    返り値 クラスタ結合履歴配列
    """
    #距離表の用意
    data = list(distfunc(vectors))
    data.sort()

    size = len(vectors)    #全体のサイズ
    sizes = list(repeat(1, size)) # 各クラスタのサイズ

    #ノードを結合した履歴を保存する配列（この列を最終的に返します）
    hist = [dict(
            data=data,   #data: まだ結合されていない成分一覧(常に距離でソート済みの状態で格納)
            joined=None, #joined: この回で結合したインデックス
            dist=0.0     #dist: この回で結合したインデックス間の距離
            )]

    nextnodenum = size   #次に使うクラスタ番号

    #size-1回繰り返して結合していきます。
    while len(hist) < size:
        #最小距離のものを選ぶ
        firstpair = min([h["data"][0] for h in hist if h["data"]])
        #最小距離のもののインデックスペア
        pairindex = set(firstpair[1:])

        movedata = []  #新クラスタ形成のために計算し直し対象とするもの格納用
        for h in hist: #履歴をさかのぼって、計算しなおしとそうでないものに分ける。
            newdata = [] #計算しなおさない居残り組格納用
            for d in h["data"]:
                if d == firstpair:  #今回結合対象のものは除外
                    continue
                intersect = set(d[1:]) & pairindex
                if intersect:  #今回結合対象とインデックスがかぶるなら、計算しなおし対象へ
                    movedata.append(d)
                else:  #そうでないなら居残り組
                    newdata.append(d)
            h["data"] = newdata  #居残り組に更新

        newdata = []  #計算しなおしデータ格納用

        dpq, p, q = firstpair  #改めて今回の結合ペアをp,qなどと名付ける
        #計算し直しデータを点ごとにグループ化。この点ごとに新距離を計算しなおします。
        movedata = groupby(sorted((((set(x[1:])-pairindex).pop(), x) for x in movedata)), key=lambda x: x[0])
        for r, d in movedata:
            newdist = 0.0 #新距離計算用
            for w in d:  #ward法計算式にしたがって計算
                w = w[1]
                newdist += (sizes[w[1]]+sizes[w[2]])*w[0]
            newdist = (newdist-sizes[r] * dpq) / float(sizes[r]+sizes[p]+sizes[q])
            newdata.append((newdist, nextnodenum, r)) #新距離を格納
        newdata.sort()  #距離データは常にソートして整理整頓
        sizes.append(sizes[p]+sizes[q])  #新クラスタのサイズデータを格納
        nextnodenum += 1 #次のクラスタID
        #履歴情報に今回の結合結果を格納
        hist.append(dict(
                data=newdata,
                joined=(p,q),  
                dist=firstpair[0]
                ))
    return hist

def main(nottest=False):
    """
    引数  nottest  パフォーマンステスト用フラグ Falseの場合はテストのために、結果出力しません。
    """
    ids = []     # データラベル格納用
    vectors = [] # ベクトル格納用
    for line in sys.stdin:  #標準入力からベクトルを読む
        data = line.strip().split("\t")
        ids.append(data[0])
        vectors.append(map(float, data[1:]))

    #クラスタリング実行
    hist = cluster(vectors)            

    if nottest:  #出力処理
        for c, h in enumerate(hist):
            j = h["joined"]
            if not j: continue
            i = "(%s+%s)" % (ids[j[0]], ids[j[1]])
            ids.append(i)
            print c, ":", i
        

if __name__ == "__main__":
   import optparse
   
   parser = optparse.OptionParser(u"""
   Ward法によるクラスタリング。
   """)
   parser.add_option("-t", "--test", dest="test", help=u"パフォーマンステスト実行", default=False, action="store_true")
   (options, args) = parser.parse_args()

   if options.test:
       #パフォーマンステスト
       import hotshot, hotshot.stats
       prof = hotshot.Profile("cluster.prof")
       prof.runcall(main)
       prof.close()
       stats = hotshot.stats.load("cluster.prof")
       stats.strip_dirs()
       stats.sort_stats('time', 'calls')
       stats.print_stats(20)
   else:
       #通常実行
       main(True)

Parallel Pythonで分散処理

2008-05-11T15:02:00.007+09:00

Erlangでなくて、Pythonで分散処理を書く意義はなんだろうかと考えた。
Erlangはたしかに分散処理が得意なんだろうけど、いろいろ調べた感じでは、複雑な数値計算などの分散処理には向いていないというウワサだ。良く知られているTwitterや通信の例のようなシンプルな処理を膨大な量さばくにはいいようだけど。

計算を分散で行う場合、本来はGoogleが採用しているように、C++をベースにすべきだろう。
（ただし、GoogleではSawzallという独自言語で記述し、それをC++に変換して実行するそうな。）

そうなると、「なぜPythonで分散処理？」というのが重要になる訳だが、おそらく以下のようなことだろうか。

既存の豊富なモジュール（しかも多くはCで書かれている）を使える。
C、C++で書かれたルーチンをswig等でPythonに連結し、それを分散させれば、実質C、C++で実行しているようなものだろう。
簡単で読みやすい。(重要！)

そこで、まさに自分が今仕事で考えているものの要件でぴったりの問題があった。

問題
文の列（数十文程度）の各文どうしの総当たりのdiff（通常の行単位ではなく、
単語単位でのdiff）を取り、diffで異なった割合を数値にした総当たり表を
リアルタイムで返す。

都合のいいことに、Pythonには標準でdiffを取るためのライブラリdifflibがついているので、こむずかしいdiff計算はそいつに丸投げできる。
これが、文の数が10、20程度なら分散させずに普通に解いても速度上問題はない。
しかし、これが40、50になってくると、ちょっと「リアルタイム」とは言えなくなってくる。
（文の数をnとすると、対称であることと、自分自身とのdiffは計算しないとしても、n*(n-1)/2回diffを取る必要がある。）

ということで、これを分散処理させてみよう。

準備
Parallel Pythonを使う。インストールは通常のpython setup.py install 一発で完了。
実験に使ったソースdiffdist.pyは本記事末尾に添付した。
以下のように実行できる。
分散処理で働いてもらいたいマシン群で、Parallel Pythonのサーバーを起動しておく。
ppserver.pyコマンドはParallel Pythonをインストールした時に、pythonコマンドと同じディレクトリ(Linux, OSX)又は、c:¥Python25¥Scritpsフォルダ(Windows)に格納されているものです。

$ /PATH/TO/PYTHONBIN/ppserver.py

あとは、diffdist.pyのppservers変数(113行あたり)にサーバー群のアドレスを記入しておいて、

$ ./diffdist.py

で実行。
(※Parallel Python本家ドキュメントに従ってauto discovery機能を使えば、IPアドレスの設定記入を省く事もできる。)
今回は、140文(合計サイズ32kb程度)の英文の総当たり表を計算した。（今回このデータは添付しない。）
英文データファイルの各行どうしで、単語ごとのdiffを取るというサンプルになっている。

結果
まず普通に分散させないコードだとどれぐらいになるかというと、

ayu@~/work/difftest% time ./diffdist.py 
Starting pp with 2 workers
./diffdist.py  26.64s user 0.36s system 97% cpu 27.705 total

ていう感じ。余裕で20秒以上かかります。

これを、自分の手元マシン(MacBook白2GHz Intel Core2 Duo & メモリ2G)でppserverを起動して分散処理させると、

ayu@~/work/difftest% time ./diffdist.py 
Starting pp with 2 workers
./diffdist.py  14.22s user 0.62s system 90% cpu 16.412 total

ここに、さらに別マシン(DELL SC1420、Intel Xeon 2.8GHz & メモリ1G)を追加すると、、、

ayu@~/work/difftest% time ./diffdist.py 
Starting pp with 2 workers
./diffdist.py  9.62s user 0.59s system 89% cpu 11.394 total

順調に速くなっている。。
おまけだが、我が家の物置で眠っていたSharpのメビウス君(AMD Duron 897MHz & メモリ256M)を追加すると、、、

ayu@~/work/difftest% time ./diffdist.py 
Starting pp with 2 workers
./diffdist.py  8.03s user 0.58s system 85% cpu 10.100 total

ほんのちょっとだけど速くなるね！

この調子で、どんどんマシンを追加していけば、この処理はすごく速くなっていくだろう。
明日会社で本格的に試してみよう。

ソース diffdist.py

#!/usr/local/Python25/bin/python
# _*_ coding: utf-8 _*_
# Copyright (C)  2007 Ayukawa Hiroshi
import sys
import difflib
from itertools import islice
from collections import defaultdict

import pp

def getdiffrate(src1, src2):
    """
    diffを取って、異なった割合(diff割合)を返す。
    """
    SPC = " "
    same = 0
    diff = 0
    for x in difflib.ndiff(src1, src2):
        if x[0] == SPC:
            same += 2 #一致部分カウントはsrc1とsrc2の分で+2
        else:
            diff += 1
    return 100 * same / float(same+diff)

def diffrow(src):
    """
    一つの文と、対比する複数の文のdiff割合をバッチ的に計算する。
    
    引数 src
    [(文番号, 原文, [(対比する文1の番号,対比する文1), (対比する文2の番号,対比する文), ..]), ...]
    
    返り値
    [(文番号, 対比する文の番号, 原文と対比文のdiff割合), ...]
    """
    ans = []
    for i1, s1, osrc in src:
        for i2, s2 in osrc:
            rate = getdiffrate(s1, s2)
            ans.append((i1, i2, rate))
    return ans
    
def d_diffmatrix(job_server, srcs, unit=140):
    """
    文一覧を与えて、各文同士の間のdiff割合行列を返す。(分散処理バージョン)

    引数
    job_server 分散処理サーバー
    srcs 文一覧（文字列の配列）
    unit バッチ処理する単位（文の数）

    返り値
    行列データ(dict型データで、res[1][2]のようにdiff割合を格納しています。）
    ただし、対角線成分上には、同じ文同士のdiff割合を格納すべきですが、計算を省略するため、
    0.0を格納しています。
    """
    #各タスク実行に必要なデータを作成する。
    task = [] #タスクに与えるデータ格納用
    subtask = [] #サブタスクとりわけ用
    sublen = 0   #サブタスクの分量計算用
    #全タスクを、文の数に従って、サブタスクに分割します。
    #サブタスクごとに分散処理させます。
    for i1, s1 in enumerate(srcs):
        osrc = list(islice(enumerate(srcs), i1))
        subtask.append((i1, s1, osrc))
        sublen += len(osrc)
        if sublen > unit: #文の数がunitを超えたら、一回分としてtaskに格納。
            task.append(subtask)
            subtask = []
            sublen = 0
    if subtask:
        task.append(subtask)

    #分散処理します。
    jobs = []  #実行ジョブ格納用
    for t in task:
        jobs.append(job_server.submit(diffrow,(t, ), (getdiffrate,), ("difflib",))) 
        
    #結果を取得して格納
    diffrates = defaultdict(lambda: defaultdict(float))
    for job in jobs:
        for i1, i2, rate in job():
            #行列状に格納
            diffrates[i1][i2] = rate
            diffrates[i2][i1] = rate
    return diffrates

def diffmatrix(srcs):
    """
    文一覧を与えて、各文同士の間のdiff割合行列を返す。(比較のための通常処理バージョン)

    引数
    srcs 文一覧（文字列の配列）

    返り値
    行列データ(dict型データで、res[1][2]のようにdiff割合を格納しています。）
    ただし、対角線成分上には、同じ文同士のdiff割合を格納すべきですが、計算を省略するため、
    0.0を格納しています。
    """

    #全タスクのジェネレーター
    def gen():
        for i1, s1 in enumerate(srcs):
            osrc = list(islice(enumerate(srcs), i1))
            yield (i1, s1, osrc)
    #処理しながら、結果を行列に格納
    diffrates = defaultdict(lambda: defaultdict(float))
    for i1, i2, rate in diffrow(gen()):
        diffrates[i1][i2] = rate
        diffrates[i2][i1] = rate
    return diffrates

if __name__ == "__main__":
    ppservers = ("192.168.1.21","192.168.1.22","192.168.1.23")

    if len(sys.argv) > 1:
        ncpus = int(sys.argv[1])
        job_server = pp.Server(ncpus, ppservers=ppservers)
    else:
        job_server = pp.Server(ppservers=ppservers)

    print "Starting pp with", job_server.get_ncpus(), "workers"

    src = file("samplepatent.txt").readlines()
    res = d_diffmatrix(job_server, [x.split(" ") for x in src])

    #比較用
    #res = diffmatrix([x.split(" ") for x in src])

Erlangでベクトルの集合をクラスタリング（k-means）

2008-05-10T22:11:00.004+09:00

Erlang本を買ったので、k-means法によるクラスタリングをサンプル的に作ってみた。
Erlang簡潔でいいですね。

使い方
データファイルをタブ区切りで用意する。
1カラム目はデータの識別用ID文字列、2カラム目以降にベクトルの数値データを記入。改行コードは¥nで。

ayu@~/work% /usr/local/erlang_R12B_2/bin/erl
Erlang (BEAM) emulator version 5.6.2 [source] [smp:2] [async-threads:0] [kernel-poll:false]
Eshell V5.6.2  (abort with ^G)
1> c(kmeans).
{ok,kmeans}
2> Src = kmeans:read_line("sampledata2.txt").
[{"1",[1,9,2,4,4,163.5,54,3,1,4,4,2.5,1,1,1,4,3,3,3,2,5]},
 {"2",[2,7,1,5,5,154.2,42,2,2,4,3,24.5,1,1,4,3,4,3,5,2,4]},
 {"3",[2,8,2,5,3,153.8,44.8,3.5,1,2,5,24,1,1,5,3,2,5,4,3,2]},
  .....
3> {L, R} = kmeans:splitvectorset(Src).
{[{"210",[2,4,2,3,3,156,42,3,2,3,4,2,2,2,3,2,3,5,4,1,3]},
  {"205",[1,6,1,3,5,170,54,2.5,2,3,3,1.5,1,1,4,3,4,1,2,3,5]},
  {"203",[1,2,1,2,3,163,53,2,2,4,4,24,2,1,3,2,2,1,3,1,3]},
  ....
4>

以上で、LとRに二分割された集合が格納される。

ソース

-module(kmeans).
-import(lists, [map/2, zip/2, sum/1]).
-import(math, [sqrt/1]).
-export([splitvectorset/1, read_line/1]).

%ベクトルのノルム
norm(X)->
    sqrt(sum(map(fun(Y)->Y*Y end, X))).

%ベクトル集合の重心
median([],_)->
    [];
median(X, L)->
    First = lists:nth(1,X),
    if
    First == [] -> [];
    true -> [sum(map(fun erlang:hd/1, X))/L | median(map(fun erlang:tl/1, X), L)]
    end.
median(X)->
    median(X, length(X)).

%ベクトルの差
sub([], _)->
    [];
sub(X, Y) ->
    [hd(X)-hd(Y)|sub(tl(X), tl(Y))].

%二つのベクトル間の距離
distance(X, Y) ->
    norm(sub(X,Y)).

%与えられた二点X,YのどちらにベクトルZは近いか？
% Xに近ければ'Right', Yに近ければ'Left'を返す。
which(_,_,[])->   
    ok;
which(X, Y, Z) ->
    DX = distance(X,Z),
    DY = distance(Y,Z),
    if
    DX > DY -> 'Left';
    true  -> 'Right'
    end.

%[{'Right/Left', ベクトル}, ...]というリストを'Right'/'Left'に従って二つの
%リストに分けて返す。
splitvector([], R, L)->
    {R, L};
splitvector([{D,Z}|T],R,L) ->
    case D of
    'Right' -> splitvector(T, [Z|R], L);
    'Left'  -> splitvector(T, R, [Z|L])
    end.

%集合ZSの２元からなる部分集合列を返す
pairs([])->
    [];
pairs([Z|T]) ->
    lists:append(map(fun(X)->{Z,X} end, T), pairs(T)).
%ベクトル集合の距離＆ベクトルペアの列を作る
pairdistance([])->
    [];
pairdistance(ZS) ->
    map(fun({X,Y})->{distance(X,Y), X, Y} end, pairs(ZS)).

%ベクトル集合の最大距離を持つ２点を選ぶ
maxdistance(ZS)->
    Pairs = pairdistance(ZS),
    {_, MX, MY} = maxdistance(Pairs, hd(Pairs)),
    {MX, MY}.   
maxdistance([], M)-> M;
maxdistance([Z|T], M)->
    {D1,_,_} = M,
    {D2,_,_} = Z,
    if
    D2 > D1 -> maxdistance(T, Z);
    true -> maxdistance(T, M)
    end.
       
   
%二点X,Yのどっちに近いかで、ベクトル集合ZSを二分割する。
splitvectorset(X,Y,ZS, Thre)->
    {R,L} = splitvector(zip(map(fun({_,W})->which(X,Y,W) end, ZS), ZS), [], []),
    IdRmv = fun ({_, V})->V end,
    CR = median(map(IdRmv, R)),
    CL = median(map(IdRmv, L)),
    MinDist  = lists:min([distance(X,CR)+distance(Y, CL), distance(Y, CR)+distance(X, CL)]),
    if
    MinDist > Thre -> 
        splitvectorset(CR, CL, ZS, Thre);
    true -> {R, L}
    end.

%公開関数その１  
%ベクトル集合ZSを二分割する。
%集合ZSは、もう一つの公開関数read_lineで読み込んだデータです。
splitvectorset(ZS)->
    Threshold = 0.1,
    case length(ZS) of
    0 -> [[],[]];
    1 -> [ZS|[[]]];
    2 -> [[lists:nth(1, ZS)], [lists:nth(2, ZS)]];
    _ ->
         {X, Y} = maxdistance(map(fun ({_, X})->X end, ZS)),
         splitvectorset(X, Y, ZS, Threshold)
    end.

%分析するデータファイルを読んで{ID, ベクトル}のリストとして返します。
% データファイル仕様
%   データファイルはタブ区切り、先頭カラムはレコードID文字列、次カラム以降が数値データ
%   改行コードは\n
read_line(File) ->
    {ok, IoDevice} = file:open(File, read),
    ANS = read_line(IoDevice, 1, []),
    file:close(IoDevice),
    ANS.

read_line(IoDevice, LineNumber, Buf) ->
    case io:get_line(IoDevice, "") of
    eof ->
        Buf;
    Line ->
        Data = string:tokens(lists:delete(10, Line), "\t"),  % 10 = "\n"
        if
        length(Data) == 0 -> ok;
        true -> Vec = {hd(Data), map(fun(X)-> parse_num(X) end, tl(Data))},
            read_line(IoDevice, LineNumber + 1, lists:append(Buf, [Vec]))
        end
    end.

%数値を表す文字列をinteger又はfloatに変換します。   
parse_num(X)->
    case string:str(X, ".") of
    0 -> list_to_integer(X);
    _ -> list_to_float(X)
    end.

pythonで英語の同義語などを取得する

2008-05-08T02:05:00.006+09:00

nltkにはwordnetが組み込まれているので、nltkひとつをインストールするだけで、同義語、上位語、下位語などを自由に取得できる。

>>> from nltk import wordnet
>>> dog = wordnet.N["dog"]
>>> dog.synsets()
[{noun: dog, domestic_dog, Canis_familiaris}, {noun: frump, dog}, 
{noun: dog}, {noun: cad, bounder, blackguard, dog, hound, heel}, 
{noun: frank, frankfurter, hotdog, hot_dog, dog, wiener, 
wienerwurst, weenie}, {noun: pawl, detent, click, dog}, 
{noun: andiron, firedog, dog, dog-iron}]

英語の検索エンジンの検索クエリ入力画面を作ったときなんかに、このデータでクエリーを膨らませて検索することとかも考えてみると使い手がありそうですね。

より詳しい使い方はnltkのデモでざっと眺める事ができます。

nltkのインストール方法は、自分の過去記事にあります。

日本語テキストのトピック分割

2008-05-04T03:03:00.010+09:00

先日からcodereposに置いている自動要約モジュールに、日本語テキストのトピック分割のソースをコミットしました。
(->そのソース)

このスクリプトでは、与えられた日本語のテキストを、トピックごとに分割する機能を提供しています。

基本的には論文"Advances in domain independent linear text segmentation"を参考にしています。
この論文では
1. 文ごとにTFベクトルを計算し、
2. そのベクトル間でcos正規化された内積を計算して文間の類似度を算出、
3. 近接する文同士の類似度の変化具合を見て、トピックの変わり目を決定。
という方式をとっています。
ですが、今回の実装では、上記を日本語にも適用するためにさらに以下の改良を加えています。

動詞も使うことにした。

日本語のテキスト、特にブログの記事などは、名詞だけでなく、「節約する」とか「怒る」とかの動詞も考慮にいれたほうがよかろうと思い、動詞も使っています。ただし、動詞は活用しますので、mecabでの処理結果の品詞情報の行から動詞の原型を取得して使うことにしました。
（->対応するソースの部分）

表記揺れ対策

原論文では英語のporter stemmingをしていましたが、日本語では独自の表記揺れ対策をしなければいけません。
表記揺れ対策には以下の方針をとりました。

1. カタカナ語は地道に辞書を作る。
カタカナ語の表記揺れ辞書データは本職で半自動生成したことがありますので、近いうちに作ろうと思います。大量の生テキストデータが必要ですので、どこかからテキストを取得せねばなりません。wikipediaデータでもいいかもしれませんが、できればあんなきれいな文章ではないほうがいいので考えます。
(->対応するソースHyokiyureData.py)

2. 漢字の単語はunigramも生成する
名詞＆未知語の場合のみ、漢字の単語の表記揺れは、その語のunigramもTFカウントすることで対応します。
例えば、通常「人」と「人々」は異なる語と認識されてしまいますが、「人々」の方を文字単位で分割し、「人」と「々」それぞれについてもカウントすることにより、「人」と「人々」が互いに多少は類似していると判定できるようになります。
(->対応するソース)

語の重みのバリエーション

語の重みを以下のように変えて計算しています。
* 名詞、未知語: 1語 = 重み1
* 名詞、未知語unigram: 1語(1文字) = 重み0.3
* 動詞: 1語 = 重み0.5
これは、一文でTFベクトルを作っても、たいていはTF=1の語ばかりで、あまりその文の特徴を表しているとも思えませんでしたので、unigramや動詞も考慮に入れた上で、それらの重みの間に差を付けることで、文の間により特色の違いをだせないかという試みです。検証してませんが、まあ、見たかんじ結果がよくなったように思うので、ひとまずこれで行きます。
(->対応するソース)

TFベクトルではなく、TFIDF的ベクトルを使用

ブログ記事のような中程度の長さの文を扱うことを想定していますので、より文の間の特徴を鋭く認識したほうがいいかと思いました。
そこで、文全体でまんべんなく頻出している単語の効果を間引くために語が現れた文の数の逆数をかけることで、ベクトルの重みを調整しています。
(->対応するソース）

まだまだ先は長いですが、こつこつ作って行きます。

coderepos

2008-05-04T02:33:00.002+09:00

codereposに自分のページを作った。今後ここに開発中のライブラリのマニュアルなどを書いていこうと思います。

http://coderepos.org/share/wiki/Committers/ayu

Jython本を注文した

2008-05-01T00:35:00.002+09:00

Jython本を注文しました。

まだAmazonのレビューはない見たいだけど、ブログでは話題になっているようだ。

随所で最高の評価を受けているようなので、とても楽しみです！

今度「Python禁止！JAVAだけで書け！」みたいなプロジェクトに無理矢理入れられそうなので、ちょっとJythonの準備しとくかな。。。

Python用の自動要約モジュールをcodereposにimportしたよ

2008-04-30T23:57:00.002+09:00

けっこう前からのんびり作っていた自動要約モジュールをCodereposにimportしました。

http://coderepos.org/share/browser/lang/python/yoyaku

この自動要約モジュールはまだあまり精度はよくないです。
が、どのぐらい良くないかを知るには、以下のサイトでいちおうサービスとして設置していますので、お試しいただけます。

自動要約サービス Civory

今の所は単純なMMRアルゴリズムで文を抜粋するだけのものですので、まあ、あまり、、、。

今取り組んでいるのは、英文の自動要約の際に、文をまずトピックごとに分割して、その上で要約をかけようとしています。
トピックに分けるアルゴリズムは以下の論文を参考にしています。
Advances in domain independent linear text segmentation
いちおうこれの実装はひとまず終わっていて、それに対応するソースは以下になります。
TopicSegmentationEN.py
今後これにバグがないか注意しながらいろんな例で実験を重ねていく予定です。

NLTKでstemming

2008-04-30T23:15:00.001+09:00

nltkにはステミングの有名なアルゴリズムであるporterアルゴリズムが用意されている。

>>> import nltk
>>> nltk.PorterStemmer().stem("application")
'applic'
>>>

自分のサイトでのユーザーの視線の流れを調べてみる

2008-04-23T19:45:00.005+09:00

プレゼンにも最適、ページ内のユーザーの視線をシミュレートする -Feng GUI heatmap

Feng GUI heatmapは、独自のアルゴリズムに基づいて、ユーザーの視線がどのようにページ内で移動するかとその頻度を表示するヒートマップを作成するサービスです。

ということなので、自分のサイトTekTekでもユーザーの視線をシミュレートしてみました。
対象ページ: 書籍「ハイパフォーマンスWebサイト」の詳細ページ

ぱっと見、書籍の画像とAmazonへのリンクに視線が集中するようだ。
しかし、このページのメインはレビューを眺めてもらうことなので、そちらがもっと読みやすくなるようにすべきかもしれない。
なんかよいアイデアはないだろうか。

ついでだが、上記書籍がまだ手元に届かない。早くしてよ〜。

NLTKで英文の文末判定

2008-04-20T09:20:00.004+09:00

英文の文末を判定する簡易なルールベースのアルゴリズム。

Separating sentences

１年前にこの手のアルゴリズムを実装しようとしたが、この問題は非常にやっかいです。
たとえばこんな例:

CELLULAR COMMUNICATIONS INC. sold 1,550,000 common shares at $21.75 each
yesterday, according to lead underwriter L.F. Rothschild & Co.

"INC."の直後や"$21.75"、"L.F."などのピリオドを文末と認識しては大間違いになるのです。

この問題を解決するのに自分が１年前に着目していた論文は以下のもの。

Unsupervised Multilingual Sentence Boundary Detection

この論文では、特に言語を英語だけに限定しない方法を提案しています。
大規模な生のテキストデータから得られる統計情報のみで、文末判定を行えます。
難点はルールベースなどとは違って、事前の綿密な統計の作成、統計処理後の各種特別処理の実装が面倒くさいこと。
昨年途中まで実装したが、Python用の自然言語処理ライブラリNLTKでどうも実装予定との情報を見つけて半端でやめていました。

それで久しぶりに調べてみたら、このアルゴリズムがすでにNLTKで実装されて公開されているではないですか！

早速インストールして使ってみました。

インストール

% wget http://prdownloads.sourceforge.net/nltk/nltk-0.9.2.tar.gz
% tar zxvf nltk-0.9.2.tar.gz
% cd nltk-0.9.2
% sudo python setup.py install
% cd ..
% sudo mkdir /usr/share/nltk
% cd /usr/share/nltk
% sudo wget http://prdownloads.sourceforge.net/nltk/nltk-data-0.9.2.zip
% sudo unzip nltk-data-0.9.2.zip
% sudo chmod -R g+r data
% export NLTK_DATA=/usr/share/nltk/data
% python
>>> import nltk
>>> nltk.corpus.brown.words()
['The', 'Fulton', 'County', 'Grand', 'Jury', 'said', ...]
>>>

ここまでできればインストール完了。

生テキストデータを用意
例えば、Google News（英語版）などからリンクをたどって、ひたすらニュース本文をファイルnews.txtにコピペする。
実験でやるんであれば１０００行程度で十分でした。

実験！！
まず生テキストを食わせて学習

>>> from nltk.tokenize import PunktSentenceTokenizer
>>> p = PunktSentenceTokenizer()
>>> fp = file("news.txt")
>>> p.train(fp.read())

次に実際に判定してみる。
判定に使うテキストは次のような少々意地の悪い例

The Finland-based company expects a weaker dollar and slower economic growth in the U.S. and parts of Europe to dampen the overall handset market this year. About half of Nokia's (NOK) sales are in dollars or currencies tied to it; a weaker dollar makes imports more expensive.

"What spooked us was its outlook for the industry in general," said Rick Franklin, equities analyst at Edward Jones.

Nokia reiterated projections that the industry shipments of handsets will grow 10% this year over last. In the first quarter, though, global shipments rose 17%, suggesting a slowdown in the remainder of the year.

For the quarter that ended March 31, Nokia earned $1.9 billion (1.2 euros), up 25% from the same quarter last year but short of an expected $2.3 billion. Overall sales rose 28% to $20.1 billion (12.6 billion euros), roughly in line with views.

>>> a=p.tokenize("""The Finland-based company expects
a weaker dollar and slower economic growth in the U.S. and parts of Europe to
dampen the overall handset market this year. About half of Nokia's (NOK) sales
are in dollars or currencies tied to it; a weaker dollar makes imports more
expensive.

"What spooked us was its outlook for the industry in general," said Rick Franklin,
equities analyst at Edward Jones.

Nokia reiterated projections that the industry shipments of handsets will grow 10%
this year over last. In the first quarter, though, global shipments rose 17%,
suggesting a slowdown in the remainder of the year.

For the quarter that ended March 31, Nokia earned $1.9 billion (1.2 euros), up 25%
from the same quarter last year but short of an expected $2.3 billion. Overall
sales rose 28% to $20.1 billion (12.6 billion euros), roughly in line with views.""")
>>> for x in a:
...    print x
...    print "-"*20
The Finland-based company expects a weaker dollar and slower economic growth
in the U.S. and parts of Europe to dampen the overall handset market this year.
--------------------
About half of Nokia's (NOK) sales are in dollars or currencies tied to it;
a weaker dollar makes imports more expensive.
--------------------
"What spooked us was its outlook for the industry in general," said Rick Franklin,
equities analyst at Edward Jones.
--------------------
Nokia reiterated projections that the industry shipments of handsets will
grow 10% this year over last.
--------------------
In the first quarter, though, global shipments rose 17%, suggesting a slowdown
in the remainder of the year.
--------------------
For the quarter that ended March 31, Nokia earned $1.9 billion (1.2 euros), up
25% from the same quarter last year but short of an expected $2.3 billion.
--------------------
Overall sales rose 28% to $20.1 billion (12.6 billion euros), roughly in line
with views.
--------------------
>>>

きちんと、ピリオドで文をわけつつも、"U.S."や、"1.2 euros"などで区切るのは避けていることが分かります。

精度を上げるには、もっともっと大量の生テキストを食わせる必要があります。

モンティ・ホール問題

2008-04-20T07:20:00.002+09:00

以下のリンク先の問題が興味深い。

Python: モンティ・ホール問題

「プレイヤーは、三つのドアを見せられる。ドアの一つの後ろにはプレイヤーが獲得できる車(アタリ)があり、一方、他の二つのドアには山羊(ハズレ)が入っている。ホストであるモンティは、それぞれのドアの後ろに何があるか知っているのに対し、もちろんプレイヤーは知らない。

プレイヤーはまず三つのドアの一つを選ぶ。次にモンティは他の二つのドアのうち一つを開け、山羊をみせる。そしてモンティはプレイヤーに、初めの選択のままでよいか、もう一つの閉じているドアに変更するか、どちらかの選択権を提供する。プレイヤーは、選択を変更すべきだろうか?」

変更しない場合: 普通に３つのうちの一つが当たりなので、当たる確率は1/3

変更する場合:
　最初の選択でもしも当たっていたら、(これは1/3の確率でおこる)->変更するためかならずはずれになる。
　最初の選択でもしもはずれていたら、(これは2/3の確率でおこる)->モンティがもう一つのはずれを引いていてくれるので、変更することで必ず当たりになる。
　そのため、変更する場合に当たる確率は2/3

なので、変更したほうが当たる確率が二倍になる！！！

partty

2008-04-14T00:17:00.004+09:00

parttyが面白い。

自分のterminalを晒すことができるwebサービスだそうです。

面識がないにも関わらずtwitterでこっそりfollow している西尾さんが使っているのを見てシビレました。

自分はMacOS 10.4.11だが、上記サイトで配布されているparttyソフトがbus errorとやらで起動しなかったので、ソースをconfigure & makeしました。

gnu screen で複数画面を立ち上げていても、それらがきちんと公開されます。
mysql -uaaa -pxxx somedb
などとうっかり打つと、パスワードが晒されますのでご注意を。

Google App Engineが待ち遠しすぎる。。。

2008-04-10T02:12:00.002+09:00

TekTekのGoogle App Engine対応は完了したのだが、まだ登録の順番が回ってこない！！

なので、ちょっとメモなど

* Google App Engineではdjangoのauth、sessionは使えないようだ。sessionが使えないのは、djangoのsessionがdjangoのmodelに依存しているからだそうな。この制限は厳しいが誰かが簡単な解決を探してくれるんじゃないかな。
* TekTekでは、sessionをやめて、できる限りCookieに保存するようにした。

Google App Engine と格闘中

2008-04-09T08:25:00.002+09:00

昨晩、数時間ほどGoogle App Engineで自作のdjangoアプリを移植していた際に気づいたこと。

* printデバッグをしていると、HTTPヘッダの前にprintの結果が出力され、HTTPヘッダもろともブラウザに表示されてしまう。
* urlopenは使えず、Googleが用意したURL Fetch APIを用いる。
* 手元のマシンのpythonのsite-packagesはそのままではどうも見てくれないようだ。
* django の ContextProcessorは通常内部的にrequest.userを使っているようで、以下のようにしてTEMPLATE_CONTEXT_PROCESORSからauthを外す必要がある。

TEMPLATE_CONTEXT_PROCESSORS = (
"django.core.context_processors.debug",
"django.core.context_processors.i18n",
"django.core.context_processors.media"
    )

早く本登録来い！！

Google App Engine SDKインストール編

2008-04-09T01:15:00.006+09:00

TekTekで使えたらいいなと思って、Google App EngineのSDKをインストールしてみた。
(まだ登録は順番待ちなのです。(T_T)
ひとまずHello worldまで実験完了したので書いておきます。

1. SDKのダウンロード
http://code.google.com/appengine/downloads.html

2. インストール
ダウンロードしたパッケージをひたすらクリックしてインストールして行きます。
その間表示されるメッセージには、以下のようなことが書いてあります。

開発用サーバーは、/usr/local/bin/dev_appserver.py にインストールされます。
その他の部品は /usr/local/google_appengine へインストールされます。

開発サーバーの起動
/usr/local/bin/dev_appserver.py [options] <application root>

"application root"は、文字通りアプリケーションのルートディレクトリで、
正式なフォーマットのapp.yamlかapp.ymlファイルを置いていなければならない。

追加で、以下のコマンドを実行し、各アプリをPythonにインストール。

% sudo ln -s /usr/local/google_appengine/google /usr/local/Python25/lib/python2.5/site-packages/google
※上記"/usr/local/Python25/lib/python2.5/site-packages/"の部分は、
あなたがお使いのPythonのインストールパスに合わせてください。

% cd /usr/local/google_appengine/lib/webob
% sudo python setup.py install
% cd /usr/local/google_appengine/lib/yaml
% sudo python setup.py
※djangoをインストールしていない方は、さらに
% cd /usr/local/google_appengine/lib/django
% sudo python setup.py

3. 確認

% python
>>>  from google.appengine.ext import webapp
※このimportで何もエラーがでなければ、OKのようだ。
>>> ^D

4. Hello worldを書く。

% mkdir helloworld
% cd helloworld
※ここでこのディレクトリに以下の２ファイルを作成。
% cat helloworld.py
print 'Content-Type: text/plain'
print ''
print 'Hello, world!'

% cat app.yaml
application: helloworld
version: 1
runtime: python
api_version: 1

handlers:
- url: /.*
  script: helloworld.py

5. hello worldアプリを起動
先ほどのhelloworldディレクトリ内にいる場合は、その上の階層へ

% cd ..

そして、以下を実行

ayu@~/work% /usr/local/google_appengine/dev_appserver.py helloworld
Allow dev_appserver to check for updates on startup? (Y/n): n  
※上でdev_appserver.pyのアップデートをするかを聞かれるが、あせってnを選びました。。。

WARNING  2008-04-09 01:31:55,128 datastore_file_stub.py] Could not read datastore data from /tmp/dev_appserver.datastore
WARNING  2008-04-09 01:31:55,128 datastore_file_stub.py] Could not read datastore data from /tmp/dev_appserver.datastore.history
INFO     2008-04-09 01:31:55,131 dev_appserver_main.py] Running application helloworld on port 8080: http://localhost:8080

ここまでできたら、以下のURLをブラウザで開く。

http://127.0.0.1:8080/

これでhello world!が画面に表示されるはず！！！

MySQL5のFederatedはまだまだ使えないという話

2008-04-08T13:40:00.002+09:00

Every query to a federated table results in a full scan of MyISAM table.

Federatedエンジンでselect count(*) from ...をすると、いちいちテーブルの全レコードをリモートに送り込むというバグがあるそうで、期待のFederatedであったがまだまだ使い物にはならない。
5.1以上で直すことになると見えるが、現時点ではChange logにその修正の旨は発見できず。

PythonでLatent semantic analysis

2008-04-08T00:52:00.003+09:00

Latent Semantic Analysis in Python

興味深い。

【要点】
* TFIDFをベクトルの成分とする。
* scipy のsvdルーチンを使う。（次元が１００万とかになっても大丈夫なんだろうか？Lanczos法のような手法を内部で使っているか？）

Blogの記事のような、極端に短い内容の記事も大量にあるような文書集合だと、こういった手法でぼかした検索ができるといいのかもしれません。

でもこういうのは実運用の場合はC++で書くべきと思うよ。

optparseのhelp文で改行を生かす方法

2008-04-07T11:23:00.001+09:00

pythonのoptparseモジュールは便利だが、help文に改行を使ってもうまく表示されない。
解決の参考になるのはここの議論だろう。
以下にそのソースを抜粋。

import optparse
import textwrap

class IndentedHelpFormatterWithNL(optparse.IndentedHelpFormatter):
  def format_description(self, description):
    if not description: return ""
    desc_width = self.width - self.current_indent
    indent = " "*self.current_indent
    bits = description.split('\n')
    formatted_bits = [
      textwrap.fill(bit,
        desc_width,
        initial_indent=indent,
        subsequent_indent=indent)
      for bit in bits]
    result = "\n".join(formatted_bits) + "\n"
    return result

  def format_option(self, option):
    """
     The help for each option consists of two parts:
       * the opt strings and metavars
       eg. ("-x", or "-fFILENAME, --file=FILENAME")
       * the user-supplied help string
       eg. ("turn on expert mode", "read data from FILENAME")
    
     If possible, we write both of these on the same line:
       -x    turn on expert mode
    
     But if the opt string list is too long, we put the help
     string on a second line, indented to the same column it would
     start in if it fit on the first line.
       -fFILENAME, --file=FILENAME
           read data from FILENAME
    """
    result = []
    opts = self.option_strings[option]
    opt_width = self.help_position - self.current_indent - 2
    if len(opts) > opt_width:
      opts = "%*s%s\n" % (self.current_indent, "", opts)
      indent_first = self.help_position
    else: # start help on same line as opts
      opts = "%*s%-*s  " % (self.current_indent, "", opt_width, opts)
      indent_first = 0
    result.append(opts)
    if option.help:
      help_text = self.expand_default(option)
      help_lines = []
      for para in help_text.split("\n"):
        help_lines.extend(textwrap.wrap(para, self.help_width))
      result.append("%*s%s\n" % (
        indent_first, "", help_lines[0]))
      result.extend(["%*s%s\n" % (self.help_position, "", line)
        for line in help_lines[1:]])
    elif opts[-1] != "\n":
      result.append("\n")
    return "".join(result)

if __name__ == "__main__":
    parser = optparse.OptionParser(
      formatter=IndentedHelpFormatterWithNL(),
      usage=u"""....""")
    ....

「ケータイマルチキャリア高機能テスター」を使ってみるよ。

2008-04-05T18:14:00.002+09:00

ケータイマルチキャリア高機能テスター P1エミュレーター
を使ってみる事にした。

ほとんどの最近のケータイのエミュレーターになるそうで、携帯用サイトの作成に役立ちそうです。

これでTekTekのi-mode版、SB版も作ってみることにしよう。

Amazon.comから尻を叩かれた話

2008-04-04T00:43:00.004+09:00

TekTekを作った時に、米国のAmazon.comのアフィリエイトにも加入したのだが、今日、そのAmazon.comから「売り上げが上がってないぞ！」ということをやんわりと伝えるメールが来た。

Hello Associate,
We noticed that you were accepted to the Amazon.com Associate Program 
several weeks ago but have yet to refer a sale. Here are a few quick 
and easy steps to help you get started:

訳:

こんにちは、
数週間前にAmazon.comのアソシエイトプログラムに加入させてあげましたが、
まだ売り上げが上がってないようですねえ。助け舟として、すぐに＆簡単に
できることを教えておきます、、、

あ、、、ありがとう、、、。がんばるよ。米国かーーー、、、どうやって宣伝すればいいものか。

TekTekモバイル for EZwebをオープンしました！

2008-04-02T02:17:00.003+09:00

TekTekのモバイル版TekTek mobile for EZwebをオープンしました。
今の所はEZwebのまあここ２〜３年ぐらいの機種のみ対応です。（古い機種での動作は確認していませんので保証できません。）

URLは以下になります。
http://www.tektek.in/d/tk/m/　　　→ TekTek mobile for EZweb

TekTekを最初に作ろうと思った動機が、本屋で本を選ぶ時にAmazonの書評と評価点数をすばやく見たいからでした。
また、場合によってはその場で本を買わずに、Amazonに注文して届けてほしいと思う事もあります。
そんな用途を考えて、このモバイル版を作っています。

今後さらなる機能追加も行って行きますが、これでひとまず自分が使いたい最低ラインに到達です。

TekTekを作った時にお世話になったものリスト＋手のうち公開

2008-03-29T14:07:00.003+09:00

TekTekにはまだ今後も追加機能をたくさん考えていますが、ここまででお世話になったものを感謝の気持ちを込めてここに書いておきます。

デザイン系
自分は絵心がないので、いろいろな素材にお世話になりました。

Open Source Web Design
サイトのデザインはここで配布されているオープンソースのデザインを拝借し、それに修正を加えて使用しています。非常に洗練されたものばかりで、すごく助かります。

PI Diagona Pack
アイコンはここから頂きました。すっきりしたかわいいアイコンで、気に入っています。

フリー素材　シンプルな吹き出しのイラスト・アイコン
吹き出し画像をここから頂きました。こういうのを作るのって、絵心がない自分にはなかなかむずかしいんですよ。

Seashore
画像の編集にはSeashoreというGIMPのMac版を使いました。

英語
英辞郎 on the WEB
英語サイトの制作のためにここで何度も何度も辞書を引いています。

プログラミング
開発は全てPythonとJavascriptで行いましたが、以下のライブラリのお世話になりました。

Django
WEBアプリのフレームワークとしてDjangoを使いました。

json.py
JSONの処理にはjson.pyを使っています。

Universal Feed Parser
RSSの処理に使いました。このライブラリはすばらしい。

pyaws
Amazon Webサービスのラッパーライブラリとして、pyawsを使いました。

jQuery 開発者向けメモ
Javascriptのライブラリとして、JQueryを使っていますが、ここのリファレンスなどには大変お世話になりました。

PopBox
書籍画像が飛び出す部分にはPopBoxというライブラリを使用しました。

API
各種大手サービスのAPIをふんだんに利用させていただきました。

Amazon WEBサービス
これはメインで使用しています。

Google ブログ検索
Googleのブログ検索のRSSを使って、TekTekの書籍紹介画面右のブログ一覧を生成しています。

Google Ajax Search API(+はてなブックマーク)
Googleの検索APIを使って、はてなブックマークの検索を行うことで、書籍紹介右の注目のレビューを表示しています。

TekTekをオープンしました

2008-03-29T12:38:00.003+09:00

TekTek

書評が気になってしょうがない人のための書籍情報閲覧サービスTekTekをオープンしました。

こういう全日本＆全世界公開型のサービスを作るのは経験不足ですが、まだいろいろ改善していきたいと思います。

ちなみにPythonとdjangoで作っています。

djangoのi18nのset_languageリダイレクトビュー

2008-03-12T23:41:00.003+09:00

またしても国際化ではまった。

djangoの国際化機能で用意されている、言語選択のビューset_languageは、公式ドキュメントではPOSTで渡すことになっているようだが、これはおそらく開発版での話で、今自分が使っている0.97preの段階ではGETで渡さないといけないようだ。
djangoの開発とその文書への反映速度の速さはすばらしいと思う。

djangoの国際化アプリをOSXで作る時にはまる事。

2008-03-02T13:20:00.003+09:00

OSXでdjangoの国際化アプリを作る場合、メッセージファイルの作成make-messages.pyでこける。
これはgettextのバージョンが古いから。最新のgettextを入れるとなおる。
gettextのインストールは、これに従った。

djangoのgeneric viewsのobject_listでPythonの普通のlistを表示する

2008-03-01T08:22:00.003+09:00

（以下、あまり詳しく既存の情報を調べず、手元のdjangoのコードを読んで適当に作ったもの。。）

djangoのgenericviewsのobject_listは便利だが、デフォルトではmodelのレコードしか表示できない。
一般のリストの中身などを表示する場合は、リストオブジェクトを適切にラップしてあげる必要がある。
そういう状況はマッシュアップサイトなどを作っていると、model以外からアイテムリストを取得したりするので、よくありますね。

以下、そのサンプル。
※get()メソッドでの例外の投げ方はあまり詳しく調べてないので、いい加減です。エラーが出るかも。
※まだpagenationさせて動かしていないので、その辺はこれからテストします。

from django.views.generic.list_detail import object_list
from django.core.exceptions import ObjectDoesNotExist
    
def list2genericviews(lst):            
    class GenList(list):
        model = "GenList"
        DoesNotExist = ObjectDoesNotExist
        def __init__(self, lst):
            self.extend([{"id": i, "value": x} for i, x in enumerate(lst)])
        def _clone(self):
            return self
        def filter(self, pk=None):
            return self[pk]
        def count(self):
            return len(self)
        def get(self):
            if len(self) == 0:
                raise self.DoesNotExist("No item found in GenList")
            if len(self) > 1:
                raise AssertionError("There are multiple items in GenList")
            return self[0]
    return GenList(lst)

def show_list(request):
    items = ["apple", "banana", "orange"]

    #引数template_nameは必須です。
    return object_list(request, queryset=list2genericviews(items), template_name="itemlist.html")

テンプレートitemlist.htmlはこんな感じ。

{% if object_list %}
  <ul>
  {% for item in object_list %}
    <li>{{ item.value }}</li>
  {% endfor %}
  </ul>
{% endif %}

Macのある生活（現実）

2008-02-04T01:15:00.000+09:00

Macのある生活

こんなにオシャレなMacもしがない三十路独身男性の手にかかると、、、、

最初はもっと引いて撮ってましたが、あまりにもMacがかわいそうな部屋なので容赦してこの範囲だけ撮影。

mod_pythonでLD_LIBRARY_PATHの設定

2008-01-29T18:27:00.000+09:00

http://www.troches.jp/content/view/131/66/

mod_pythonの設定をapacheのhttpd.confに書くときに、SetEnvでLD_LIBRARY_PATHなどを設定しても効き目がないそうだ。

/etc/init.d/httpd にexport LD_LIBRARY_PATH = ... と書くとよいとのこと。

ハイフンっぽい文字を一括で半角マイナスに変換

2008-01-29T17:01:00.000+09:00

元ネタはこちら。 http://d.hatena.ne.jp/koseki2/20070927/unicodehyphen

hihuns = (u"\u002d", u"\u2212", u"\uff0d", u"\u30fc", 
    u"\u2012", u"\u2013", u"\u2014", u"\u2015", u"\u2500")
def to_han_hihun(s):
        for x in hihuns:
                s = s.replace(x, u"-")
        return s

[メモ]djangoのnewformsで半角英数のみのフィールド

2008-01-28T11:07:00.000+09:00

以下のような感じでCharFieldを定義すると一応できるが、作法的にOKなのだろうか。
なんかいちいちこういう書式の制限を書かなければならないわけはないと思うのでもっと簡単な方法があるはずじゃないかなあ。

class AsciiCharField(forms.CharField):
    def clean(self, value):
        if not re.match(ur"^[A-Za-z0-9_\-\.]+$", value):
            raise forms.ValidationError(u'半角英数字のみを使用してください。')
        return forms.CharField.clean(self, value)

[メモ]シェルでファイル名を数字でソート（２桁まで）

2008-01-24T11:26:00.000+09:00

２桁までの数字のついたファイルfile**.txtをgrepしたい。ただし、ファイルについている番号順にgrepをかけていきたい。
そういう場合は、ワイルドカード{?,??}を使うと、数字順にソートした上で処理できる。(1の次が10にならないようにソートできる。）

grep searchword file{?,??}.txt

ただし、lsコマンドでファイル一覧を表示する場合は、lsコマンドがデフォルトで名前でのソートを行うので、-vをつけないといけない。

[ayu@home]~/tmp% ls -l -v file{?,??}.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file1.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file2.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file3.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file4.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file5.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file6.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file7.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file8.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file9.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file10.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file11.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file12.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file13.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file14.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file15.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file16.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file17.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file18.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file19.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file20.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file21.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file22.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file23.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file24.txt
-rw-r--r--  1 ayu ayu 0 Jan 24 11:28 file25.txt

[メモ]djangoからloggingを使う場合のタイムゾーンはsettings.TIME_ZONEで決まる

2008-01-22T13:06:00.000+09:00

djangoのsettings.pyのTIME_ZONEはいつも適当にデフォルトで放置していましたが、loggingモジュールでログを出力する場合のタイムゾーン設定として、きちんと効いているので、ちゃんと以下のように書こう。

TIME_ZONE = 'Asia/Tokyo'

[日記]過去の認識

2008-01-20T02:18:00.000+09:00

リアル84歳だけど質問ある？
興味深い。


506 名前：以下、名無しにかわりましてVIPがお送りします。：2008/01/16(水) 18:20:49.46 ID:gixHjhq+0
    ヒトラーとムッソリーニはどう思った？

    >>506
    ヒトラーはドイツの首相だな
    若い人にはわかりにくい感覚だと思うが聞いてくれ
    当時は今みたいに情報がなかった
    だから、ただ日本の友好国の首相だとしか思ってなかった
    ユダヤ人の虐殺とかもあまり知らなかった
    ただ、ヒトラーはあの人なりに正しいことをしようとしただけだと思うよ
    今のアメリカとイラクだってそうだ
    お互いに正しいと思ったことをやってるだけだ
    後から、あの人は悪い人って決めつけるのは簡単だけど、特別ヒトラーが悪人だとは思わんよ
    真面目過ぎるとは思うけど  

517 名前：84 ◆5HOOEYijHo ：2008/01/16(水) 18:34:05.69 ID:W45St2r1O
    続き
    若い人の中には戦争に否定的な人も多いし、戦争に関わった人を憎む人も多いね
    気持もわかる
    でも、今の生活や政治や平和も戦争の過去があるからある
    軍人に感謝しろなんて言う馬鹿な老人にはなりたくないが、当時の人もみんな真面目に家族や国の平和を
　　願っていたんだよ
    ただ勝ち負けがあるだけで
    だから、過去を知ることは大切だけど、60年も昔のことを憎むのは馬鹿らしいことだ

[メモ]PILの良サンプル

2008-01-11T12:29:00.000+09:00

サンボマスタージェネレーターのソースはPILのサンプルとしてとてもバランスがよい。

[メモ]TODO: プログラミングGaucheを入手すること

2008-01-04T10:27:00.000+09:00

書籍 -- プログラミングGauche

2008年2月発売予定との事。非常に待ち遠しい。

Gaucheが相当に"電池内蔵"という話

2008-01-04T00:28:00.000+09:00

自分がPythonを使えるようになって思い上がっているのをいさめるために始めたSchemeの練習を今年も続けて行こうと思います。
帰省から帰ってきたら自分が年末に書いたコードすら読めなくなっててびびりましたが。

先日ここに書いた（汚い）ソースに、Gaucheの作者様から直々に添削を頂きました！ありがとうございます！本当にありがとうございます。感激しております！

そこでまずは、以下の二点を勉強しつつ修正してみた。
* デフォルト値つきのassoc -> util.listのassoc-ref
* Pythonで言うgroupby -> gauche.collectionのgroup-collection

さらにそのコメントにはパフォーマンスを考慮した工夫や、末尾再帰を簡易に書くヒントまでも頂いておりますが、そこは一晩寝てから続きをします。

ありがとうございます！

（上記二点による修正で、コードの行数が100行 -> 78行に激減！）

;; coding: utf-8
(use mecab)
(use srfi-1)
(use srfi-13)
(use gauche.collection)
(use util.list)

;;名詞の列を抽出する関数
(define (takenowns node)
  (let impl ((node node) (buf '()) (ans '()))
  (if (mecab-node-null? node) 
      (if (null? buf) ans (append ans (list buf)))
      (if (string-prefix? "名詞" (mecab-node-feature node))
   (impl (mecab-node-next node) (append buf (list (mecab-node-surface node))) ans)
   (impl (mecab-node-next node) '() (if (null? buf) ans (append ans (list buf))))))))
   
(define (countgroup data)
  (define (iter data buf)
    (if (null? data)
 buf
 (if (null? (car data))
     (iter (cdr data) buf)
     (iter (cdr data) (cons (cons (car (car data)) (length (car data))) buf)))))
  (reverse (iter data '())))

(define (has l n)
  (cond ((zero? n) #t)
 ((pair? l) (has (cdr l) (- n 1)))
 (#t #f)))

;; bigram生成関数
(define (bigram data)
  (define (iter data buf)
    (if (has data 2)
 (iter (cdr data) (cons (list (car data) (cadr data)) buf))
 buf))
  (iter data '()))

(define (count-bigram data keyf)
  (map (lambda (x) (cons (car x) (length x)))  
       (group-collection (map keyf data) :test equal?)))

;;スコア計算式
(define (calc-score word all left right)
  (* (assoc-ref all (string-join word) 1.0)
     (expt 
      (let loop ((restword word) (weight 1.0))
   (if (null? restword)
       weight
       (loop (cdr restword) 
      (* weight (+ 1 (assoc-ref left (car restword) 0))
         (+ 1 (assoc-ref right (car restword) 0))))))
      (/ 1 (* 2 (length word))))))

;;複合語抽出メイン関数
(define (calc-mword mecabobj body)
  (let* ((words (takenowns 
  (mecab-sparse-tonode mecabobj body)))
  (tandoku-hindo (countgroup (group-collection words :test equal?)))
  (uniq-bigram 
   (map car 
        (group-collection (concatenate (map bigram words)) :test equal?)))
  (left-hindo (count-bigram uniq-bigram cadr))
  (right-hindo (count-bigram uniq-bigram car))
  (tandoku-hindo-map (map (lambda (x) (cons (string-join (car x)) (cdr x))) tandoku-hindo)))
    (sort 
     (map 
      (lambda (x) (cons (string-join (car x)) (calc-score (car x) tandoku-hindo-map left-hindo right-hindo))) 
      tandoku-hindo)
     (lambda (a b) (> (cdr a) (cdr b))))))

(define m (mecab-new2 ""))

(time  (map print (calc-mword m
      "日本ハムが来秋のドラフト上位候補に、ホンダの長野（ちょうの）久義外野手（２３）＝日大出＝
をリストアップしていることが２７日、分かった。昨年１１月の大学生・社会人ドラフトで４巡目指名しな
がら入団拒否された“恋人”に、再度アタックする。　１度フラれても、あきらめきれない。日本ハムが再
び、長野の獲得に向けて動いている。「去年は（入団を）断られたけど、今年１年見て順調にきている。改
めて推薦したい選手の１人」と球団関係者。“恋人”の高評価は変わらない。　２年越しのラブコールだ。
日本ハムは、昨年のドラフトで巨人入りを志望していた長野（当時日大）を大学生・社会人ドラフト４巡目
で強行指名。だが、希望球団でないことを理由に入団を断られた。　その後、長野は社会人のホンダへ進
み、１年目から外野の定位置を獲得。３月の社会人東京大会で新人賞を受賞し、日本代表として出場した
１１月のワールド杯（台湾）ではチーム最高打率（．４５７）をマーク。０７年の社会人野球ベストナイン
にも選出された。来秋のドラフトでは上位指名確実の逸材だ。　入団拒否後も、日本ハムの担当スカウトが
再度の獲得へ向けて誠意をみせている。関係者を通じて、巨人オンリーだった長野の心変わりをキャッチし
た。指名を拒否されながら、再び指名するのは過去数例（別項）あるが、極めて異例だ。「来年も（長野
を）注目していきたい」と球団関係者。熱い思いが届く日まで、密着マークする。")))

(mecab-destroy m)

末尾再帰重要

2007-12-29T16:37:00.000+09:00

非常に貴重な突っ込みをいただきました。

odz buffer -- [Python][Scheme]tail call

教訓
* 時々は末尾再帰を意識して書こう。（特にこういう頻繁に呼び出す関数では。）
* lengthは遅い。（リストをつらつらたどって毎回計算するのかな？）
* Gaucheは関数の再帰呼び出しでスタックを使い尽くすとヒープに移す。ただしそうなるとちょっと遅くはなるかも。
* Pythonはやはり配列の添字番号をうまく使い、ジェネレーターを活かすと吉。
* Pythonのrange関数は、schemeではsrfi-1のiota

ほんとうにたすかります。ありがとうございます。
でも、このツッコミで示された最速の関数bigram3を読み解けないという悲しい状況。がんばって読もうと思います。

追記-------
bigram3理解できました。
同様の方針でこれまで自分が書いていた他の関数も末尾再帰になるようにしてみたりした。

Schemeで重要語抽出を書いた感想

2007-12-29T15:22:00.000+09:00

重要語抽出をSchemeで書いてみて、一応できたのだけど、ソースが汚い。だれか添削してくれないものだろうか。
つい数時間前にsrfiのマニュアルを初めて見ていろいろとがっくり来た。（というぐらい低レベルな自分）

今リファクタリングを重ねながら、思い知らされるのはやはり自分の今のSchemeの低レベルぶりだ。

他の要因として、Pythonだと細かい気の利いた標準関数、メソッドなどがあらかじめ用意されているが、Schemeの標準は自由度を尊重(というか「各自自力で」推奨？)しているためPythonほどガチガチではないから、そういうのを自分で書かないといけないというのもあるんじゃなかろうか。

Pythonのdictのgetメソッドがデフォルト値を指定できたり、itertoolsのgroupbyとかは地味に便利だが、Schemeの場合はそういうのは自分で用意しないといけない。

以下、その汚いソース。アルゴリズムは毎度のことながらhttp://gensen.dl.itc.u-tokyo.ac.jp/から拝借。
mecabへの接続には、先日書いたやつを使用した。
let*を使っている部分からレベル２の匂いが。

;; coding: utf-8
(use mecab)
(use srfi-1)
(use srfi-13)

;;名詞の列を抽出する関数
(define (takenowns node)
  (let impl ((node node) (buf '()) (ans '()))
  (if (mecab-node-null? node) 
      (if (null? buf) ans (append ans (list buf)))
      (if (string-prefix? "名詞" (mecab-node-feature node))
   (impl (mecab-node-next node) (append buf (list (mecab-node-surface node))) ans)
   (impl (mecab-node-next node) '() (if (null? buf) ans (append ans (list buf))))))))

;;文字列のリストの比較関数
(define (compare-string x y) (if (and (null? x) (null? y)) #t 
    (if (null? x) #t
        (if (null? y) #f
     (if (eq? (car x) (car y))
         (comp (cdr x) (cdr y))
         (string<? (car x) (car y)))))))
   
(define (groupby data eqfunc)
  (let impl ((data data) (buf '()) (ans '()))
    (if (null? data) 
 (if (null? buf) ans (append ans (list buf)))
 (let ((head (car data)) (tail (cdr data)))
   (if (null? buf) 
       (impl tail (list head) ans)
       (if (eqfunc (car buf) head)
    (impl tail (append buf (list head)) ans)
    (impl tail (list head) (append ans (list buf)))))))))

(define (countgroup data)
  (if (null? data) 
      '()
      (if (null? (car data))
   (countgroup (cdr data))
   (cons (cons (car (car data)) (length (car data)))
  (countgroup (cdr data))))))

;; bigram生成関数
(define (bigram data)
  (if (< (length data) 2) 
      '()
      (cons (list (car data) (cadr data)) (bigram (cdr data)))))   

(define (count-bigram data keyf)
  (map (lambda (x) (cons (car x) (length x)))  
       (groupby (sort (map keyf data) string<?) equal?)))

;;デフォルト値付きのassoc
(define (defassoc k ary d)
  (let ((a (assoc k ary)))
    (if (eq? #f a) d (cdr a))))

;;スコア計算式
(define (calc-score word all left right)
  (* (defassoc (string-join word) all 1.0)
     (expt 
      (let loop ((restword word) (weight 1.0))
   (if (null? restword)
       weight
       (loop (cdr restword) 
      (* weight (+ 1 (defassoc (car restword) left 0))
         (+ 1 (defassoc (car restword) right 0))))))
      (/ 1 (* 2 (length word))))))

;;複合語抽出メイン関数
(define (calc-mword mecabobj body)
  (let* ((words (takenowns 
  (mecab-sparse-tonode mecabobj body)))
  (tandoku-hindo (countgroup (groupby (sort words compare-string) equal?)))
  (uniq-bigram 
   (map car 
        (groupby (sort (concatenate (map bigram words)) compare-string) equal?)))
  (left-hindo (count-bigram uniq-bigram cadr))
  (right-hindo (count-bigram uniq-bigram car))
  (tandoku-hindo-map (map (lambda (x) (cons (string-join (car x)) (cdr x))) tandoku-hindo)))
    (sort 
     (map 
      (lambda (x) (cons (string-join (car x)) (calc-score (car x) tandoku-hindo-map left-hindo right-hindo))) 
      tandoku-hindo)
     (lambda (a b) (> (cdr a) (cdr b))))))

(define m (mecab-new2 ""))

(map print  (calc-mword m
      "日本ハムが来秋のドラフト上位候補に、ホンダの長野（ちょうの）久義外野手（２３）＝日大出＝を
リストアップしていることが２７日、分かった。昨年１１月の大学生・社会人ドラフトで４巡目指名しなが
ら入団拒否された“恋人”に、再度アタックする。　１度フラれても、あきらめきれない。日本ハムが再
び、長野の獲得に向けて動いている。「去年は（入団を）断られたけど、今年１年見て順調にきている。改
めて推薦したい選手の１人」と球団関係者。“恋人”の高評価は変わらない。　２年越しのラブコールだ。
日本ハムは、昨年のドラフトで巨人入りを志望していた長野（当時日大）を大学生・社会人ドラフト４巡目
で強行指名。だが、希望球団でないことを理由に入団を断られた。　その後、長野は社会人のホンダへ進
み、１年目から外野の定位置を獲得。３月の社会人東京大会で新人賞を受賞し、日本代表として出場した
１１月のワールド杯（台湾）ではチーム最高打率（．４５７）をマーク。０７年の社会人野球ベストナイン
にも選出された。来秋のドラフトでは上位指名確実の逸材だ。　入団拒否後も、日本ハムの担当スカウトが
再度の獲得へ向けて誠意をみせている。関係者を通じて、巨人オンリーだった長野の心変わりをキャッチし
た。指名を拒否されながら、再び指名するのは過去数例（別項）あるが、極めて異例だ。「来年も（長野
を）注目していきたい」と球団関係者。熱い思いが届く日まで、密着マークする。"))

(mecab-destroy m)

実行結果

ayu@~/work/Gauche-mecab% gosh sample.scm | nkf -e | head -n 20
(長野 . 6.0)
(指名 . 5.656854249492381)
(ドラフト . 4.898979485566356)
(日本ハム . 4.0)
(球団 関係 者 . 3.563594872561357)
(１ 人 . 3.309750919646873)
(１ 年 目 . 3.1072325059538586)
(獲得 . 3.0)
(入団 . 2.8284271247461903)
(０ ７ 年 . 2.6671682753399955)
(今年 １ 年 . 2.5873402367724454)
(４ ５ ７ . 2.5697965868506505)
(４ 巡 目 指名 . 2.413690382068065)
(社会 人 ドラフト . 2.2894284851066637)
(社会 人 ドラフト ４ 巡 目 . 2.2894284851066637)
(２ 年 越し . 2.220906154852325)
(社会 人 . 2.2133638394006434)
(上位 指名 確実 . 2.1398263878673256)
(２ ７ 日 . 2.1398263878673256)
(１ 度 フラ . 2.075781631112427)

[日記]Schemeのレベル

2007-12-29T09:11:00.000+09:00

私家版、Schemeプログラマのレベル10

SICPのambで挫折している自分はレベル4に踏み込んだばかりのレベルだ。
レベル４の「クロージャーうんぬん」はPythonを使っていて自然に身に付いたおかげで、今とても助かっているんだなあと再認識。

きっとambを使いこなせるようになれば、今会社で書いている複雑なPythonのプログラムもずいぶんすっきり書けるんだろうなあ。

[メモ]再帰を使うとn-gramはすっきり書ける

2007-12-29T08:36:00.000+09:00

例として、bigramを生成する関数。

再帰を使わないバージョン(Python)

def bigram(data):
    if len(data) < 2:
        return
    prev = data[0]
    for x in data[1:]:
        yield [prev, x]
        prev = x

再帰を使ったバージョン(Scheme)

(define (bigram data)
  (if (< (length data) 2) 
      '()
      (cons (list (car data) (cadr data)) (bigram (cdr data)))))

Pythonだと再帰の深さの制限があるので、このような書き方はできませんが。
補: 念のためやってみた。

def bigram2(data):
    if len(data) < 2:
        return []
    return [[data[0], data[1]],] + bigram2(data[1:])

↑Pythonでこう書ければいいんだけど、すぐに"maximum recursion depth exceeded"になるよ。

補: 実際にschemeでエラーにならないことも確認。

(define (bigram data)
  (if (< (length data) 2) 
      '()
      (cons (list (car data) (cadr data)) (bigram (cdr data)))))   

(define (range x)
  (let loop ((ini 0))
    (if (= ini x)
 '()
 (cons ini (loop (+ ini 1))))))

(print (bigram (range 10000)))

Pythonのrange関数相当のものがschemeにも標準であるはずだと思うんだけどなあ。

[メモ]MySQLでテーブル一覧でビューかどうか調べる方法。

2007-12-28T14:52:00.000+09:00


select TABLE_NAME, TABLE_TYPE from INFORMATION_SCHEMA.TABLES 
where TABLE_SCHEMA="データベース名";

Gaucheの練習: 連続する名詞の抽出

2007-12-14T00:43:00.000+09:00

連続する名詞の抽出を書いてみた。Gauche(というかScheme)素人なのでとても時間がかかる。


;; coding: utf-8

(use mecab)

(define (takenowns node buf ans)
  (if (mecab-node-null? node) 
      (if (null? buf) ans (append ans (list buf)))
      (if (equal? "名詞" (substring (mecab-node-feature node) 0 2)) 
   (takenowns (mecab-node-next node) (append buf (list (mecab-node-surface node))) ans)
   (takenowns (mecab-node-next node) '() (if (null? buf) ans (append ans (list buf))))))
)

(define m (mecab-new2 ""))

(map print 
     (takenowns 
      (mecab-sparse-tonode m "並み居る共和党候補たちのはるか後方で何カ月も低迷していた
ハッカビー氏は、アイオワ州の支持率でついに、ミット・ロムニー氏についで２位となった")
       '() '()))

(mecab-destroy m)

実行結果


ayu@~/work/Gauche-mecab% gosh sample.scm | nkf -e
(共和党 候補 たち)
(はるか 後方)
(何 カ月)
(低迷)
(ハッカビー 氏)
(アイオワ 州)
(支持 率)
(ミット・ロムニー 氏)
(ついで ２ 位)

自分で書いておいてなんだが、非常に読みづらいコードだと思う。
もっときれいに書けるようになるにはあと何年かかるだろうか。
Pythonできれいにかけるようになるのにも数年かかったからなあ。

以下を調べておく事------
[done] Pythonのリストのように後ろに追加していけるリストはないのだろうか。
Python文字列のstartswithメソッド相当を作る。

Schemeのmecabバインディング

2007-12-13T03:30:00.000+09:00

関数型言語を勉強して来たが、実用を考えるとマルチバイト文字を扱えることが必須になる。
その時点で早くもHaskellは立場が弱くなるのだが、その点Gaucheはすばらしいということに改めて気づいた。（Schemeでは破壊的代入ができますが、そういう細かいことは自分のような初心者にはまあ、いいでしょう。）

そこで、自分の分野でガリガリ使ってGaucheの勉強をするために、Gaucheからmecabを使ってみようと思った。

この点での先人のすばらしい記事を発見。
その記事「Gauche:MeCab」に、自分としてはparseToNode相当の機能がほしかったので、Gaucheのバインディングの細かい事を勉強せずに推測で機能追加してみた。

Gauche-mecab.tar.gz

いちおう下のようなプログラムで動くようになる。

（ただし、mecabの文字コードとGaucheの内部encodingをそろえておく必要あり。）


;; coding: utf-8

(use mecab)

(define (allnodes node)
  (if (mecab-node-null? node) 
      '() 
      (cons node (allnodes (mecab-node-next node))))
)

(define m (mecab-new2 ""))

(let ((node (mecab-sparse-tonode m "太郎は極悪です。")))
  (map 
   (lambda (x) 
     (print (mecab-node-surface x)) 
     (print (mecab-node-feature x))) 
   (allnodes node))
)
  
(mecab-destroy m)

実行結果


ayu@~/work/Gauche-mecab% gosh sample.scm | nkf -e

BOS/EOS,*,*,*,*,*,*,*,*
太郎
名詞,固有名詞,人名,名,*,*,太郎,タロウ,タロー
は
助詞,係助詞,*,*,*,*,は,ハ,ワ
極悪
名詞,形容動詞語幹,*,*,*,*,極悪,ゴクアク,ゴクアク
です
助動詞,*,*,*,特殊・デス,基本形,です,デス,デス
。
記号,句点,*,*,*,*,。,。,。

BOS/EOS,*,*,*,*,*,*,*,*

PythonでHarwell-Boeing matrix

2007-11-28T01:19:00.000+09:00

C++のような本気言語ではなく、"バッテリー内蔵言語"であるPythonでHarwell-Boeing matrixのようなシビアな世界のデータ構造を書いたらどのぐらいになるかと試した。

このぐらいになる。


#!/usr/bin/python
# _*_ coding: euc_jp _*_
# Copyright (C)  2007 Ayukawa Hiroshi
from array import array
from itertools import izip, islice
from collections import defaultdict

class Hwmatrix(object):
    def __init__(self, rownum_type="I", colnum_type="I", val_type="I"):
        self.rowindex = array(rownum_type)
        self.colindex = array(colnum_type)
        self.val = array(val_type)
        self.rowindex.append(0)

        if val_type in ("f", "d"):
            self.val_type = float
        else:
            self.val_type = int
        
    def addrow(self, row):
        row = dict(row)
        cols = row.keys()
        cols.sort()
        vals = [row[k] for k in cols]
        self.colindex.extend(cols)
        self.val.extend(vals)
        self.rowindex.append(self.rowindex[-1] + len(cols))

    def getrow_as_pair(self, n):
        rownum = self.rowindex[n]
        rowlen = self.rowindex[n+1] - rownum
        return islice(izip(self.colindex[rownum:], self.val[rownum:]), rowlen)

    def __rmul__(self, vector):
        if isinstance(vector, dict):
            answer = defaultdict(self.val_type)
            for k in vector.keys():
                weight = vector[k]
                for i, v in self.getrow_as_pair(k):
                    answer[i] += weight * v
            return answer

def test():
    """
                  1 1 0 0 0
                  0 1 1 0 0
    (0 2 3 0 1) * 0 0 1 1 0  =  (0 2 5 3 1)
                  0 0 0 1 1
                  0 0 0 0 1
    """
    mat = Hwmatrix()
    mat.addrow({0:1, 1:1})
    mat.addrow({1:1, 2:1})
    mat.addrow({2:1, 3:1})
    mat.addrow({3:1, 4:1})
    mat.addrow({4:1})

    print {1:2, 2:3, 4:1} * mat

test()

これはひょっとして実用的に使えたりしないだろうか。
会社ではC++で書いたものを使っていますが、自宅の趣味にはこういうのでもいいかも。

追記---
でも、よく考えると、ベクトルとの積__rmul__での処理なんかで、いちいち内部でPyObjectを作って参照カウンタをごにょごにょやっているんだと想像すると、一気に使う気が失せました。
やはりこういうのはC++じゃないといやだな。

djangoのせいで

2007-11-27T22:48:00.000+09:00

S2StrutsのクイックスタートのGreetingのサンプルを見たが、なんかめまいが。

djangoをここ3ヶ月ほど使っていたおかげで、もうJAVAでのWEB開発には戻れない体になってしまいました。

S2Strutsでの開発が自分に回ってきそうになっているが、どうしようか悩み中。

ユークリッドの互除法

2007-11-17T01:01:00.000+09:00

ユークリッドの互除法のような簡単なものだと、さすがにHaskellもPythonもそんなに差はなく、どちらもきれいに書ける。

Haskell

euc m 0 = m
euc m n | m < n = euc n m
        | m `mod` n == 0 = n
        | otherwise = euc n $ m `mod` n

main = do print $ euc 1071 1029

Python

def euc(m, n):
    if m < n: return euc(n, m)
    if n == 0: return m
    if m % n == 0 : return n
    return euc(n, m % n)

print euc(1071, 1029)

[メモ]数学の記述ではやはりHaskellがPythonよりも上手ですが、変態的Pythonなら肉薄できそう

2007-11-16T00:31:00.000+09:00

エラストテネスのふるいという素数生成アルゴリズムがあるが、これを（平方と素数の間に成り立つ不等式を考慮せずシンプルに）Haskellで書くと３行で書ける。

removenum x xs = filter (\a -> a `mod` x /= 0) xs
hurui (x: xs) = x : (hurui $ removenum x xs)

main = do  print $ take 100 $ hurui [2..]

これを標準的な作法に従ったPythonで書くと少し行数が増える。（けっこうがんばったのですが。。。）

from itertools import ifilter, count, islice

def hurui(xs):
    first = xs.next()
    yield first
    for x in hurui(ifilter(lambda x: x % first != 0, xs)):
        yield x

for i in islice(hurui(count(2)), 100):
    print i,

しかも、10000個ぐらい素数を出力させようとすると再帰呼び出しのスタックがあふれてしまう。
Haskellの場合は10000個でも大丈夫だし、きっといくつでも大丈夫なんだろう。（だからこそ関数型なんだろうし）

Pythonで無理矢理遅延評価を実現すれば、以下のようにも書けて、再帰であるのにスタックあふれもなくなる。

from itertools import ifilter, count, islice, takewhile, tee, dropwhile

def hurui(xs):
    first = xs.next()
    return (first, lambda : hurui(ifilter(lambda x: x % first != 0, xs)))

first, func = hurui(count(2))
for i in range(10000):
    print first,
    first, func = func()

こういうテクニックって、一般にはなんて言うんだろう。末尾再帰？

追記
コメントで頂いたのだが、以下のサイトによりエレガントな方法が。
http://4topcoder.blogspot.com/2007/07/python-generator.html
なるほどすごい。

[メモ]MySQLのプロセス監視

2007-11-15T14:58:00.000+09:00

これは便利。

watch -n 15 'mysql -u*** -p*** -e "show processlist"'

[メモ]MySQLの最適なテーブル定義を知る方法

2007-11-15T12:54:00.000+09:00

既存のテーブルの無駄に長いフィールドなどを調整したい場合は以下のクエリーで最適なフィールドの長さなどの情報を表示できる。

SELECT * FROM table_name PROCEDURE ANALYSE()

参考: MySQL Presentations: Optimizing MySQL

[日記]まだまだアッカーマン関数

2007-11-13T23:54:00.000+09:00

いまだにアッカーマン関数が原始的でないことの証明をやっている。
あと１パターンの不等式を証明できればできあがりなんだけど。
ここの日記に最初にアッカーマン関数の事を書いてからもう８日がすぎています。
もしこれが大学の授業の宿題とかだったりしたら、自分は
「１週間やってたけどできませんでした。」
という、まじめはまじめなんだけど、できない子みたいだなあ。

すべて完成したら、次にもう一度この証明を見直すときのために証明の要点をここの日記に整理して書こうと思います。
しかし、まずは残りをやらなければ。

[雑談]「これから一からプログラミングを覚えようと考えています。」

2007-11-09T08:31:00.000+09:00

これから一からプログラミングを覚えようと考えています。
様々な言語がありますが、どれを覚えるべきでしょうか？

PHPすごい人気ですね。
初心者に最適という評価はあるようだ。

でも初心者でなくなったときにPHPに感じる落胆もでかいんだよなあ。

数年PHPを使い込んだ過去のある自分としてはおすすめできない。
LL等のイベントでPHPの重鎮の発表の自虐的な雰囲気を見てから判断してもいいと思った。

（このブログにトラックバック機能があれば、トラックバックしたかったが、残念ながらないみたい。。）

Pythonはこういう時に自信を持って勧めていいものかどうか迷います。
他の言語にあらかた疲れた時に、ふと使ってみるとはまるという性質もあるからねえ。

[日記]まだアッカーマン関数

2007-11-08T22:45:00.001+09:00

毎日少ししか勉強時間が取れないので、アッカーマン関数の演習問題から抜け出せていない。

２日悩んだ問題「アッカーマン関数をNプログラムで計算する方法を考えよ」は、スタックをNプログラムで書ければうまくいきそうだとわかったが、それには次の章以降の知識がいるようだ。。。スタックを書く方法を一日考えていたがやはり自力では思いつかないので素直に次章へ進むしかないか。
しかし、「考えよ」ということだから、（「書け」というわけではないから、）ここまでできれば完了なんだろうか。なんともすっきりしない。

次の問題はアッカーマン関数が原始的関数でないことの証明問題なので、着々と進んでいるが、長いので時間がかかりそうだ。

アッカーマン関数やばい

2007-11-06T23:29:00.000+09:00

アッカーマン関数を計算論の教科書の演習問題で見て、問題がうまく解けないのでためしにアッカーマン関数の計算結果の一部を一覧にして眺めようと思った。
でも、計算量が多すぎてすぐにとんでもないことになるんだね。お願いだから教科書に書いておいてくださいと思いました。

f 0 y = y + 1
f x 0 = f (x - 1) 1
f x y = f (x - 1) (f x (y - 1))

main = do print $ f 4 2

これをHaskellで実行すると死ぬ。
f 3 2 ぐらいはまだ大丈夫だが。

どのぐらい計算量がやばいことになるかを、f 2 2 の場合で置換モデルでノートに書き下していったら、なんと２７行もノートを使うということが判明。
f 4 2なんか、そりゃとんでもないことになってるんだろうなあ。

[メモ]正規表現モジュール re のscanner機能

2007-11-06T10:26:00.000+09:00

Pythonのドキュメントには書かれていないが、正規表現モジュール(re)にはscannerという機能がある。
一旦作成した正規表現オブジェクトで、長い文章中をスキャンしていくような感じで、全てのマッチする部分を検出していく機能だ。
便利なんだが、使いたい時に毎回使い方を忘れているのでこの際ここにメモしておこう。

>>> a="aaabbbcccdddaaa111fffsss"
>>> import re
>>> pat = re.compile(r"aaa(...)")
>>> dir(pat)
['__copy__', '__deepcopy__', 'findall', 'finditer', 'match', 'scanner', 
'search', 'split', 'sub', 'subn']
>>> scanner = pat.scanner(a)
>>> dir(scanner)
['match', 'search']
>>> m = scanner.search()
>>> m
<_sre.SRE_Match object at 0x2a98006210>
>>> m.groups()
('bbb',)
>>> m = scanner.search()
>>> m.groups()
('111',)
>>> m = scanner.search()
>>> m
>>>   #もう候補がないので m = None となっている。

[メモ]有機ＥＬ

2007-11-01T16:25:00.000+09:00

EUCで「有機ＥＬ」という語の「機」の後半バイトと「Ｅ」の前半バイトはくっつけると「。」と同じコードになる。

>>> s = lambda x: map( lambda y: hex(ord(y)) , unicode(x, "utf-8").encode("euc_jp"))
>>> s("有機ＥＬ")
['0xcd', '0xad', '0xb5', '0xa1', '0xa3', '0xc5', '0xa3', '0xcc']
>>> s("。")
['0xa1', '0xa3']

[メモ]djangoのmodelのカスタムSQLでujisのトラブル回避

2007-10-29T17:18:00.000+09:00

MySQLでujisを使っている場合、djangoのカスタムSQLで日本語を使おうとすると、以下のエラーがでる。

UnicodeEncodeError at /***/***/
'latin-1' codec can't encode characters in position 170-172: ordinal not in range(256)
Request Method:  GET
Request URL:  http://**.**.**.**/***/***/
Exception Type:  UnicodeEncodeError
Exception Value:  'latin-1' codec can't encode characters in position 170-172: ordinal not in range(256)
Exception Location:  /usr/local/python25/lib/python2.5/site-packages/MySQL_python-1.2.2-py2.5-linux-x86_64.egg/MySQLdb/cursors.py in execute, line 149
Python Executable:  /usr/local/python25/bin/python
Python Version:  2.5.0

ぐぐると自分が過去にTurboGearsMLに投稿した記事が出てきた。
http://groups.google.com/group/turbogears-ja/browse_thread/thread/69bc1ff4d86eca33/d18807e59a924bb3

ここではみなさんうまくきれいに解決されたようだが、相変わらず自分はうまくいかないので、以下をsettings.pyに書いて解決。

DATABASE_OPTIONS = dict(charset="ujis", read_default_file="/etc/my.cnf")

(ただし、/etc/my.cnfにデフォルトcharsetをujis指定で設定しておく。）

本当は↓みたいなのでうまくいけばいいんだけど、なんかそうならない。

DATABASE_OPTIONS = dict(charset="ujis", use_unicode=1)

言語の比較記事

2007-10-11T23:38:00.000+09:00

Ruby に比べて Python の面倒なところ
こういう他の言語を深く知っている方の感想は読んでためになる。
自分が無意識に適応してるけど、実はめんどうなことをやっているんではないかというふうに相対化した視点を得るきっかけになるのはいいことだ。

で、挙げてある「Pythonの面倒なところ」もたしかに的を得たものばかり。
printが文であることなどは自分も含めたPythonを日頃使う人も違和感を感じることもあるんじゃないだろうか。

ただ、そういう疑念が湧いたとしても、Pythonのようにそれなりに多くの先人の知恵が集まってできている言語では、たとえばprintが文になっているのもそれなりの利点があったからなのかもしれないと想像している。（うろ覚えだがPython3系ではprintが関数になるんじゃなかったけ？たぶんまた考え直したんだろうか。）

たとえば、代入が値を返さないというのは、


if a = 10:
    ....

のようなケアレスミスを直ちに検出できたりするから個人的にはすごく好きな点だったりする。

selfをいちいち書くのも、そのクラスの名前であることが強烈に分かるのでとても愛すべきポイントだったりする。逆にC++を書くときはthis->を書きたくて書きたくてしょうがなく感じるときもある。（がまんしてできるだけ書きませんが。）

importも、これを日々いちいち書く事で、予約語が少なく済んでいるということを骨身に沁みて感じることができたり、関数やクラスをモジュール単位で整理して思い出せるので好きなポイントだ。

returnも、どこで値が返っているかをエディタの検索で色付き反転させて一気に見る事ができてすごくいい。

ああ、なんかこうして書いていくとほんとにきりがなくて、自分はPythonに魂をうばわれているんじゃないかと思うよ。

あるPython信者がたどったHaskellの入り口までの道のり

2007-10-05T23:24:00.000+09:00

Haskellの勉強がついにその入り口の敷居を超えた気がするので、ここまでの経緯を記録しておく。

* １年ほど前、、、「入門Haskell」を購入して一読するも理解できず。

* その１ヶ月後、、、「ふつうのHaskell」を購入して一読。途中まで写経。全体像がぼんやり見えてくるも未だ「代数的データ型」とか「型クラス」とかが一体何のためにあるか理解できず。モナドに至っては全くわからない状態。

* それからしばらくして、「モナディウスの解説ページ」を発見。Haskellでのプログラミングの進め方が、これまでのプログラミングとはずいぶんと違うことを発見。「代数的データ型」とか「型クラス」とかがわかり始める。

* それからしばらくして、仕事で作ったPythonの短いスクリプトをHaskellに移植してみる。やっぱりPythonのほうが楽だし実行時のパフォーマンスもはるかにいいし、Haskellを勉強する意欲が失せる。

* それからしばらくして、「SICP」を読み始めるも、途中のambが出てきたあたりで挫折。写経せずに電車内での読書にしていたのが敗因か。しかし、そこまででもいろいろ深い内容でためになる。この時期、自分のPythonのプログラムにやたらとmap、filter、lambdaが増え始め、そのPythonにあるまじき傾向に自制の必要を感じる。

* それからしばらくして、OCamlに手を出すも、データ型の扱いがシビアすぎて萎える。

* しばらくは時々Haskellに思いを馳せるだけの日々。結局どういうときに「代数的データ型」を使って、どういうときにただのリストとかpairで済ませるのかにうじうじと思い悩む。。。

* 数日前、「Haskellのお勉強」の写経を始める。いろいろわかり始める。敷居を超えた感を初めて味わう。

* 二日前、モナドの定義やモナド則を、チラシの裏に書いて試行錯誤してなんとか理解。モナドの演算の「m >>= k」は、「(>>= k)がmに右から作用する」と読む事で理解が深まることに気づいた。（←この視点で可換図式を書いてモナド則を理解するのがいいようだが、合っているかの自信はない。）ただこれが実際にプログラミングでどう役に立つのか、特にdo式をどういう文脈で理解すべきか、IOモナドの詳細とか、Listモナドをモナドと見なすことのご利益の理解はこれから。

* 今日、仕事であるバッチの複雑な計算処理をHaskellで書いてみた。ベクトルの各種演算とか、ファイルのIOがたらふくあるようなやつです。でも予想外にすんなり書けて驚いた。６０行ぐらいの規模のプログラム。こんなに短くなるとは予想していなかった。可読性はPythonには劣るものの、なんだか気持ちいいプログラムになって満足。でも、あちこちでmap, filter, zip系を使うので、書いてある内容の密度はすごい。

ここまで１年かかっているが、昔３回ぐらい挫折を繰り返しながら数年のレンジでC++を身につけたのに比べると、まだましな道のりだろう。

[メモ]Python信者から見た、Javaを使いたくない理由

2007-10-04T09:24:00.000+09:00

ちょっとメモしておきます。
* generatorがない。
* 関数を返す関数とか、関数の配列を作ったり、それらを活用することが推奨されていない。
* lambdaがない。無名クラスのような大げさな書き方が必要。
* map, filter系関数がない。imapやifilterはもちろんない。
* 動的配列、ハッシュマップ、集合などの便利なコンテナをコンパクトに記述できない。1.4系では取り出すたびにキャストが必要なので不便。
* 最近、業界標準になってしまった某IDEが重過ぎる。
* catchを必ず書く必要がある。
* sortでcomparatorを書くのが面倒くさい。
* 大げさなライブラリは外付けでたくさんあるが、細かい気の利いたライブラリがない。(CSV読み込みとか、簡易に使えるXMLRPCサーバーとか)

「Pythonをはじめよう」という記事が指摘しているPythonの良い点

2007-09-12T22:46:00.000+09:00

Codezine: Pythonをはじめよう
という記事の以下の一節が目をひいた。

中括弧等を打たなくて良い分ロジックの打ち込みだけに集中できますし

たしかにそうだ。
言われてみて気づいた。
他の言語では、括弧の対応が合っているかどうかをエディタの補助機能を使いながら確認しなければいけないが、Pythonの場合は縦にざっと眺めるだけでその対応（＝インデント）が見通せてしまうというのは、いいことだ。

Pythonのそもそもの思想に、「コードは書かれることより、読まれることのほうが多い」というのがあったような気がしますが、インデントは「読まれること」を非常に重視したとてもいい仕様だと思う。

django searchというのを見つけた

2007-09-12T09:51:00.000+09:00

django search
というのがあるのを見つけた。
django関連の話題の検索サイトのようだ。
Google custom searchを使っているみたいだが、これはすごく便利そうです。

[メモ]popen2

2007-09-07T18:44:00.000+09:00

以下の記述はうそ。popen2.pyを見ると、bufsizeにはデフォルトで-1が指定してある。自分の環境で止まっているのは、別の理由のようだ。
popen2でプロセスを起動して、返事がなかなか返ってこないなと思っていたら、popen2の引数に渡すbufsizeを超えてデータを渡していたようだ。
このサイズを超えると、無反応でとまってしまうのではまる。

[メモ]sqlalchemyとloggingを同時に使う場合は、loggingという名前がかぶるよ。

2007-09-07T18:05:00.000+09:00

import logging
from sqlalchemy import *

というふうにすると、loggingという名前が、sqlalchemy.loggingで上書きされて、loggingが動かなくなる。
import順を逆にするとよい。

[メモ]django.dbでmysqlの文字コード指定。

2007-09-07T10:16:00.000+09:00

settings.pyで

DATABASE_OPTIONS = dict(charset="ujis")

参考: http://groups.google.com/group/django-ja/browse_thread/thread/26ff26fccc6258c3
selectはうまくいくことを確認済み。

[メモ]defaultdictの引数はうまく使えば便利に違いない

2007-09-06T12:47:00.000+09:00

defaultdictの引数には普通はintやfloatを入れるもんだが、"lambda :[0,0]"のような無名関数を入れることもできる。

>>> from collections import defaultdict
>>> a = defaultdict(lambda :[0,0])
>>> a["AA"]
[0, 0]
>>> a["AA"][0] += 1
>>> a
defaultdict(<function <lambda> at 0x2a95666938>, {'AA': [1, 0]})
>>> a["aa"][1] += 1
>>> a
defaultdict(<function <lambda> at 0x2a95666938>, {'AA': [1, 0], 'aa': [0, 1]})

[メモ][TODO]Django+SQLAlchemy調べ物

2007-08-30T18:03:00.000+09:00

以下を調べること。

djangoをSQLAlchemyで使う場合、
* djangoのsqlalchemyブランチとやらは必須なのか？
* model.pyをいきなりsqlalchemyの記述に差し替えて、影響範囲はどれぐらい？
　* 認証とか大丈夫？
　* 汎用ビューはあきらめる？
　* adminツールもあきらめないといけないのか？
追記 ---
http://django.g.hatena.ne.jp/perezvon/20070211
この日記の記事が参考になる。
やっぱりユーザー認証は独自実装ですか、、、。
しかし、SQLAlchemyを使うことで、これほどまでに失うものが多いのであれば、いったいそもそもdjangoである必要があるのかどうかという疑問がでてきた。

sqlalchemyブランチを取ってきたがsqlalchemy使ってるかどうかさえ不明な感じ。（ひょっとしてただ本家をコピーしてきただけ？）
結局自分でなんとかしないといけないみたい。

Directory Queue便利そう。

2007-08-29T08:55:00.000+09:00

Directory Queue
ファイルベースのキュー実装。

ファイルベースなので、データはファイルの中に書く。
ファイルベースなので、途中でプログラムがクラッシュしても、キューの中身は残るんだろうか。（きっとそうだよね。。）
面白いのは「メタデータ」を別途持たせることができること。

これはJMSのMessageの仕様を参考にしているのかな？

こういうプロジェクトがきちんと育ってくれたら、自分が今の仕事で使っているJMS地獄からいくぶん解放されるんじゃないだろうか。

追記---
「ファイルベース」というよりは、「ディレクトリベース」というほうが適切か。
キュー内の1アイテムは、1ディレクトリで表されている。そのディレクトリの中に、データを表す"file.data"というファイルと、メタデータを表す"meta.data"というファイルを置くようだ。

キューからのアイテムの取得は、os.listdirでディレクトリ内の一覧を取得して、ディレクトリ名のソートで先頭を取得するようだ。
これはキュー内に大量のメッセージを格納したときにパフォーマンスが心配である。
とは言っても、メッセージが大量にならない場合には問題ないだろう。

[メモ]SQLAlchemyのPrecompiling a Query

2007-08-29T08:30:00.000+09:00

Precompiling a Query

SQLAlchemyであらかじめSQLを構成しておいて引数だけを差し替える方法。
ループの内側でSQLをいちいち作り直す時間をはぶきたいときに使えそうだ。

this.pyのソースは文字を巡回させているのに気づいたよ。

2007-08-28T12:12:00.000+09:00

こんなふうに。

s = """Gur Mra bs Clguba, ol Gvz Crgref

Ornhgvshy vf orggre guna htyl.
Rkcyvpvg vf orggre guna vzcyvpvg.
Fvzcyr vf orggre guna pbzcyrk.
Pbzcyrk vf orggre guna pbzcyvpngrq.
Syng vf orggre guna arfgrq.
Fcnefr vf orggre guna qrafr.
Ernqnovyvgl pbhagf.
Fcrpvny pnfrf nera'g fcrpvny rabhtu gb oernx gur ehyrf.
Nygubhtu cenpgvpnyvgl orngf chevgl.
Reebef fubhyq arire cnff fvyragyl.
Hayrff rkcyvpvgyl fvyraprq.
Va gur snpr bs nzovthvgl, ershfr gur grzcgngvba gb thrff.
Gurer fubhyq or bar-- naq cersrenoyl bayl bar --boivbhf jnl gb qb vg.
Nygubhtu gung jnl znl abg or boivbhf ng svefg hayrff lbh'er Qhgpu.
Abj vf orggre guna arire.
Nygubhtu arire vf bsgra orggre guna *evtug* abj.
Vs gur vzcyrzragngvba vf uneq gb rkcynva, vg'f n onq vqrn.
Vs gur vzcyrzragngvba vf rnfl gb rkcynva, vg znl or n tbbq vqrn.
Anzrfcnprf ner bar ubaxvat terng vqrn -- yrg'f qb zber bs gubfr!"""

d = {}
for c in (65, 97):
    for i in range(26):
        d[chr(i+c)] = chr((i+13) % 26 + c)

print "".join([d.get(c, c) for c in s])

django一日目の感想

2007-08-24T18:37:00.000+09:00

今日は数時間ほどユーザー登録周りのコードを書いていた。
こうしてチュートリアル以外で、まともにdjangoをさわるのはほぼ初めてです。

基本的にはdjango-registrationを、公式リリースであるdjango0.96で使えるように改造する作業。

いくつか気づいた点

* djangoのデフォルトのテーブルauth_userのフィールドemailはuniqueではない。なので、同じメールアドレスのユーザーをじゃんじゃん登録できる。
* ↑これは別にいいんじゃないと思うが、こうなっていると、複数ユーザーが同じemailアドレスを使っている場合パスワードのリセット機能が動かない。（これはすでに公式のバグレポートに上がっているようだ。）
* なので、登録時にemailの重複チェックを追加実装する必要がありました。初心者なので汚い実装方針でしたが一応チェックできるようになった。

* パスワードリセットフォームがadmin標準のものだったので、自分の用意したテンプレートに差し替えた。
* urls.pyの書き方が難しい、全てのリンクがうまくつながるようになるために、いろんな箇所を微調整。
* メールで送られてくるURLを正しいものにするには、siteテーブルを書き換える必要があることに気づくのにしばらくかかった。

djangoを使う人たちはこういうのは普通にすぐに自作してしまうんだろうか。
Turbogearsならこういうのはコマンド一発で完了してしまうのとは対照的。
しかしdjangoの勉強になったのでよかったと思う。

なんだかいろいろわかってきたよ。

[メモ]Intel Mac OSX 10.4でstackless pythonをビルド

2007-08-24T09:03:00.000+09:00

stackless pythonのOSXバイナリもあるのですがインストール先を変えたりしたかったので、自分でビルドした。
途中１カ所つまずいたのでメモしておく。
（これが正しいのかはよくわからないですが。）
参考にしたのはこの記事。

./configure --prefix=/usr/local/stackless-python251 --enable-universalsdk --enable-framework

そして、できあがったMakefileにて -DSTACKLESS_FRHACK=0 という記述がある部分が１カ所あるので、そこを -DSTACKLESS_FRHACK=1 に書き換える。（←これがほんとにこれでいいのか自信ないのだが、上の参考記事と同様の効果を得るにはこのフラグの変更でいいようだ。）
そんで、

make
sudo make install

サンプルのfactorial.pyをダウンロードして、実行。

ayu@~% /usr/local/stackless-python251/bin/python factorial.py 
0.0117838382721

ひとまずうまく動いたみたい。

[メモ]django-registrationの疑問

2007-08-22T15:52:00.000+09:00

django-registrationは、djangoのSVN最新版でないと動かないようだ。
みなさんどうしているんだろう。自作？それともみんなSVN最新版を使うのが普通なんだろうか。。。

[メモ]【訂正】TurboGearsのwidgets-based formのpre-fill

2007-08-22T09:13:00.000+09:00

昨日のエントリーに、TurboGears×Pythonのatsさんからじきじきにアドバイスが！

以下のように、フィールド名:値という内容のdictを渡し、、

class SomethingFields(widgets.WidgetsList):
    code = widgets.HiddenField()
    query = widgets.TextField(label=u"検索")

class SomethingSchema(validators.Schema):
    code = validators.String(not_empty=True, max=9)
    query = validators.String(not_empty=True, max=5)

class SomethingForm(widgets.TableForm):
    fields = SomethingFields()

something_form_obj = SomethingForm(fields=SomethingFields(), validator=SomethingSchema())

class SomeController(controllers.Controller):
    @expose(template='kid:somepackage.SomeController.templates.detail')
    def detail(self, code, **kw):
        #........
        return dict(form=something_form_obj, value={"code": code})

kidのほうで、value=でその辞書を指定してやるといいのだということ。

<span>
${form(action='search', submit_text = "Search", method="get", value=value)}
<p py:if="defined('message')">${message}</p>
</span>

やはり、正統なやり方はきれいです。
ありがとうございました！

[メモ]TurboGearsのwidgets-based formのpre-fill

2007-08-21T12:45:00.000+09:00

TurboGearsの公式FAQページで"Answers wanted for the following questions"という欄に未だ回答なしとして載っているFAQの一つに

「widgets-based formにあらかじめ値を埋め込むにはどうすればよい？」

というのがあがっている。

多分こんな感じでどうだろう。

class SomethingFields(widgets.WidgetsList):
    code = widgets.HiddenField()
    query = widgets.TextField(label=u"検索")

class SomethingSchema(validators.Schema):
    code = validators.String(not_empty=True, max=9)
    query = validators.String(not_empty=True, max=5)

class SomethingForm(widgets.TableForm):
    fields = SomethingFields()

something_form_obj = SomethingForm(fields=SomethingFields(), validator=SomethingSchema())

class SomeController(controllers.Controller):
    @expose(template='kid:somepackage.SomeController.templates.detail')
    def detail(self, code, **kw):
        #........
        something_form_obj.fields[0].attrs["value"] = code
        return dict(form=something_form_obj)

この最後から二行目のように、


フォームオブジェクト.fields[0].attrs["value"] = "あらかじめ入れたい値"

とすればいいようだ。fields[0]というふうに番号で指定するのが気持ち悪いけれど。

[メモ]Turbogearsのidentity.currentはthread safeなのか？

2007-08-17T20:25:00.001+09:00

turbogears/identity/__init__.pyのモジュールのグローバルに以下の記述がある。


current= IdentityWrapper()

この変数currentはthread safeでいてくれるんだろうか。
IdentityWrapperの中では、cherrypy.request.identityを参照していて、cherrypyまでは追ってないけど、cherrypy.request.identityがthread localな仕組みになっていたとすれば大丈夫なんかなあ。。。
なんか自信ないなあ。調査してみるか、、、大変。

追記---
大丈夫のようだ。
cherrypyのコードを追うのが面倒だったので、テスト的なアプリを作って実験をし、変数currentがthread safeらしいことを確認した。

というか自分はなぜ週末の夜の自宅で、仕事で出会ったバグの原因つぶしなぞしているのだろう。こういうのはまずい。

[メモ]TurboGears + SQLAlchemyはthread safeなんだろうか？

2007-08-17T19:44:00.000+09:00

SQLAlchemyのSessionはthread safeではない。
thread safeにするには、SessionContextを使いなさいとのこと。

だが、Turbogearsのソース中にSessionContextを使っている箇所がないのはどういうことでしょう。。。。

この件調査中。

追記---
使っているのをturbogears/database.pyに発見。

from sqlalchemy.ext import activemapper, sessioncontext
....
session = activemapper.Objectstore(create_session)

Objectstoreはsqlalchemy/ext/activemapper.pyで以下の定義。

class Objectstore(object):
    def __init__(self, *args, **kwargs):
        self.context = SessionContext(*args, **kwargs)
    def __getattr__(self, name):
        return getattr(self.context.current, name)
    session = property(lambda s:s.context.current)

たしかにこれならthread safe。安心した。

追記---
この記事投稿後15分でGoogleのインデックスに入っている。Google恐るべし。（Bloggerだからか？）

[メモ]名前付きlet

2007-08-17T07:05:00.000+09:00

全エントリの反省を受けて勉強。

Scheme入門 7. 繰り返し

名前付きletの解説に、「Schemeで繰り返しを表す標準的な方法です。」とのことだけどとても気持ち悪い。
素人考えだけど、繰り返しは再帰関数一本にしてしまったほうがいいんではないだろうか。
再帰で書いた方が一行少なくなりそうな例しか自分には思いつかないが、こういった仕様があるということは、この記法が自然だったり役立ったりする場面があるということだろう。奥が深いなあ。

[メモ]Pythonによる英字の半角全角変換

2007-08-16T15:12:00.000+09:00

↓これもっと簡潔できれいな書き方はないものだろうか。

from itertools import izip
#半角英字->全角英字変換
HAN_CHARS = map(chr, range(ord('A'), ord('Z')+1) + range(ord('a'), ord('z')+1))
ZEN_CHARS = map(lambda x: unichr(0xff00 + x),range(0x21, 0x21+ord('Z')-ord('A')+1) +
                   range(0x41, 0x41+ord('Z')-ord('A')+1))
def han2zen(word):
    """
    Unicodeで与えられた文字列の半角英字を全角英字に変換する。
    """
    for c, cc in izip(HAN_CHARS, ZEN_CHARS):
        word = word.replace(c, cc)
    return word

追記----
多少ましなものになった

import re
HAN_UPPER = re.compile(u"[A-Z]")
HAN_LOWER = re.compile(u"[a-z]")
def han2zen(word):
    word = HAN_UPPER.sub(lambda m: unichr(ord(u"Ａ") + ord(m.group(0)) - ord("A")), word)
    word = HAN_LOWER.sub(lambda m: unichr(ord(u"ａ") + ord(m.group(0)) - ord("a")), word)
    return word

追記----
調子に乗って一般化してみた。上のような変換関数を大量生産できる関数だ。
Unicodeの列を平行移動するようなイメージの変換を生成します。

#!/usr/bin/python
# _*_ coding: euc_jp _*_
import re

def replace_sequence(*transform_rules):
    """
    Unicode文字コードで連続した文字の列を対応する別の連続する文字に変換する関数を作る。

    引数:
    transform_rules 変換ルールを表す文字列を任意個の引数で与える。
    一つの変換ルールは３文字のUnicode文字で表現されます。

    変換ルール記述例
    u"AZＡ"  一文字目は変換元の文字列の先頭、二文字目は変換元文字列の末尾、三文字目は変換先文字列の先頭を表します。

    この変換ルールを引数に並べます。
    
    """
    rules = map(lambda x: (re.compile(u"[%s-%s]" % tuple(x[:2])), x[2], x[0]), transform_rules)
    def henkan(word):
        for pattern, start, src_start in rules:
            word = pattern.sub(lambda m: unichr(ord(start) + ord(m.group(0)) - ord(src_start)), word)
        return word
    return henkan

if __name__ == "__main__":
    num_han2zen = replace_sequence(u"09０")
    num_zen2han = replace_sequence(u"０９0")
    alpha_han2zen = replace_sequence(u"AZＡ", u"azａ")
    alpha_zen2han = replace_sequence(u"ＡＺA", u"ａｚa")

    print num_han2zen(u"0120-116")
    print num_zen2han(u"１８８−００１３")
    print alpha_han2zen(u"ABCを習いました。")
    print alpha_zen2han(u"世界のＳＯＮＹ")

この関数replace_sequenceを使うと、上で必死こいてつくってた半角英字->全角英字関数はこの一行で作成できる。


alpha_han2zen = replace_sequence(u"AZＡ", u"azａ")

使う時はこのalpha_han2zenを関数として呼び出し、


print alpha_han2zen(u"ABCを習いました。")

で行ける。

上のプログラムの実行結果。

ayu@~/work% ./sample.py
０１２０-１１６
188−0013
ＡＢＣを習いました。
世界のSONY

これはちょっと便利かも。会社に持っていこう。
こういうプログラムを書いていると、今更関数型言語を勉強しなくても、Pythonで、まあいいのかなという気にもなり、またしても自分の進歩が阻害されてしまう気がする。

Turbogearsピンポイントドキュメント一覧

2007-08-11T09:07:00.000+09:00

前エントリで触れたんだが、「ドキュメント重要」ということなので、自分が目を通すことの多いTurbogears関連のドキュメントの目次だけでも作っておこう。（日本語訳までできないのが残念ですが。）
Turbogearsはコードの大半をツールが自動生成してくれますので、ちょっとした作法なんかは自動生成された部分をチラ見するだけで、自分なりに追加機能を書き始めることも可能です。
ですが、やはり一貫した知識も必要なので、そのときはこういったドキュメントを読みます。

* Python Workshop the Edge 2007での柴田さんのハンズオン資料(PDF/日本語です)
入門記事です。自分がTurbogearsを使うきっかけになったのがこれでした。

* Turbogears公式リファレンス
Turbogearsの公式リファレンスです。Turbogearsでは各種デコレーターを使いますのでその使い方はここでよく見ることになります。

以下、各論。
* ユーザー登録機能のためのregistrationパッケージ
このトップページに文書が掲載されている。最近のWEBアプリでは、まずユーザー登録はどうしようかと考えるので、このすぐ使える機能一式のパッケージは重宝。
（登録、メールでの認証、ログイン、ログアウト、パスワード忘れ対策全部入り。）

* Modelを作る際に使うSQLAlchemyのドキュメント
モデルの作成は奥が深い。そのぶん、ドキュメントもちょっと規模が大きめです。
　* 低レベルなSQLを意識した使い方
　　SQL脳から完全に脱却できない自分のための機能。。。

　* 高レベルなMapperを使った操作
　　テーブルのリレーションを事前に定義して楽したい場合はこちら。
　　パフォーマンスを改善するには、
　　lazy=True
　　deferred設定
　　

* 各modelのCRUDを作るためのtgcrud
モデルを定義したら、これで一気にCRUDを作成する。

* Formのバリデーターについて
Formの扱いは、上に挙げているregistrationやtgcrudが生成するコードを見るとだいたいわかるのですが、ちゃんと知りたいならこのページがおそらくいいのでは。

* Kidテンプレート書式一覧
* その日本語訳を発見！
一通り仕組みができてきたら、実際のモデルのデータをページに埋め込んだりする段階にくるはず。その頃には、このテンプレートの書式一覧が必要です。
（柴田さんの日本語訳があることを今調べてて知った。。。。）

自分はSQLAlchemyとKidを使っていますので、上のようなラインナップです。
でもKidはXML的に妥当なテンプレートを書く必要があって、ちょっと厳しいなと思う。できれば差し替えたいところ。
SQLAlchemyには大満足。やりたいことが全てきれいにできる。パフォーマンスの調整も思いのまま。このツールはすばらしい。（普段仕事でJAVAのS2Daoも使うが、SQLAlchemyを知ってからはS2Daoがしんどくてしょうがない。。。）

自分もTurbogearsはまだここ１ヶ月ぐらいしか使ってませんので全くの素人レベルです。今後ここに役立つ文書のページを追記していきます。。。

ドキュメントが重要

2007-08-11T08:21:00.000+09:00

最近職場でTurbogearsでつくった社内ツールを公開している。
いろいろな機能を次々追加しているので、けっこうな規模のツールになる予感がしてきた。

やはりこういうフレームワークを使うと仕事がとても早いので、うちの職場全体でもこういうPythonのフレームワークをつかっていったらどうだろうかという話も出てきた。

ただそうなるとTurbogearsの文書のラインナップでは仕事に使っていくにはちょっときついかなと思った。

まず職場の全員が英語に慣れているわけでもないので、公式文書の日本語訳がないのはつらい。

次に、Turbogearsのような「詳細は他の(KidなりSQLALchemyなりの）文書を見てね」という文書体系では、ドキュメント内の探索の仕方を、各部品ごとに変える必要がある。

こういうのは慣れなので日々Pythonに興味を持って情報を自ら集める人にとってはなんてことない。
文書が英語だろうと、ちょっとふぞろいだろうと、サンプルコードやいろんな人のblog記事を探索しながらなんとかなる。
ただ、職場では「本来はJAVAが一番好きだけど、仕事なのでしょうがなくPython使うよ」という人も当然のように存在する。
そういった人のための情報を用意できたときに初めてフレームワークが「実務に使える」という形で浸透していくんじゃないかなあと思った。

こういったことを考えるとdjangoの文書の日本語訳の存在はすばらしいことと思う。
自分の場合はこれから勉強していかないといけないけれど。

（休日に仕事のことを考えるのはほどほどにしなければ、、、）

[メモ]SQLAlchemyのMSEnum型

2007-08-09T09:08:00.000+09:00

MSEnumは引用符内にさらに引用符を書かねばならないという罠。


Column('myenum', MSEnum("'foo'", "'bar'", "'baz'"))

[メモ]最近気に入っている方法

2007-08-09T08:13:00.000+09:00

1. Gnu Screenの0番目に常にemacsを開いておく。
2. 仕事の進捗はemacsのChangelogでメモ。
3. 一日の仕事が終わるときにもChangelogにメモ。
4. Screenのデタッチで閉じて帰宅。
5. 次の日出社したらscreen -r でChangelogが即開いて見える。

こういうのっていいですね。
サーバーがずっと動きっぱなしの会社だから可能な方法。
emacsはまだまだ便利に使えそうなのでもっと勉強していこう。。。

SQLAlchemyでMySQLのyear型が使えない

2007-08-08T16:06:00.001+09:00

MSYearというmysql用の型のクラスがあるのだが、実際にcreate table文を作ると、VARCHAR型として作られてしまう。

この件調査中。

追記----
これがSQLAlchemyの方針にとって正しいのか不明なんだけど、sqlalchemyのソースのsqlalchemy/databases/mysql.pyのMSYearに以下のget_search_list(self)メソッドを追記すれば一応解決する。


class MSYear(sqltypes.String):
    """MySQL YEAR type, for single byte storage of years 1901-2155"""

    def get_col_spec(self):
        if self.length is None:
            return "YEAR"
        else:
            return "YEAR(%d)" % self.length

    def get_search_list(self):
        return [self.__class__]

year型がMySQLの型の中でもすごく特殊な実装なので、非常に難しい部分なんだろう。
ちょっとSQLAlchemyの作者の方々にメールを送ってみようかなあ。

追記---
メールを送ってみた。
こういうのを送るのはどきどきするなあ。英語きっとぐちゃぐちゃだし。通じればいいんだけど。

追記---
返事がきた。
0.3のメンテナンスブランチ＆0.4では修正済みとのことです。
あああ、こういう最新版をチェックせずに指摘メールを送ったり、（さらには自分で修正を試みたり）というのはいけないことだなあと思った。

[メモ]Mac OSXにgtagsをインストール

2007-08-05T13:43:00.000+09:00


$ sudo port install global

これで、/opt/local/bin/gtags にインストールされる。

[メモ]LL魂感想

2007-08-05T12:22:00.000+09:00

今思い出せるものだけメモ。

== Language Update ==
Python::
「Pythonは１０年使える言語」というポイントは、今まで意識していなかった。
これまで５年ぐらいPythonを使っていますが、ずっと安定して使えていたり、新バージョンが出た時に、当たり前のように後方互換だったりしたことに、陰ながら支えてもらっていたことに気づき、感謝の気持ちを覚えた。

Ruby::
Lazy collectionの話は思わず「おおお！」と思ってメモを取ったのだが、その後手厳しい修正が。でもああやって言及したということは、実装したいってことだからこれから数年以内に実現するんだろうか。

PHP::
何もあそこまで「どんより感」を全面に出さなくてもよかったのではないだろうか。（LLが初めて開催された年もそうであった。)
GreeとかSidefeedとかcheckpadのような華々しい実績に言及しないと。
数年前は自分もPHPを使っていましたが、言語の仕組みとしての難点はほんとうに多々あれど、「とにかくWEBが作れる」というのは事実。

Perl::
Perl6か、、、。大変そうだなあ。
Perl5.10で"//"という記法が新登場とのこと。こういう方向性はPythonとは正反対でおもしろい。Pythonではありえない。

R::
今会社の隣の席の人がしきりにオススメしてくる言語なので興味があった。scheme+S言語という点が興味を引く。schemeか、、去年途中まで勉強してやめてるな。。。

Clean::
速度が速いということに興味を持った。
昨年仕事でサンプル的にHaskellを使ったことがあるが、７００万行（20G)のテキストファイルを処理するのに速度的にまったく不足していた。が、この言語ならいけるんじゃないだろうか。Haskellにそっくりなのですんなりつかえるかもしれない。Intel Macのサポートが次バージョンからだそうなので心待ちにしよう。

Lua::
「俺様言語」のコーナーで各種自作言語がライバル視していたのが特徴的。

== 俺様言語の作り方 ==
Xtal::
あちこちのブログで話題になっているが、プレゼンが（というか作者が）抜群に天然。
C++との連携を主眼にしているということは、C++の資産が全て使えるということだから実はすごく便利かもしれない。ただ自分の場合はPytonとC++の連携が今のところうまく行っているので、使い道を考えにくい。
Pythonと簡単に連携できないだろうか。Pythonでパフォーマンスが欲しいところをC++で書くのではなく、Xtalで書ければ、Pythonとのギャップがまだ小さいだろうから、簡単にならないだろうか。

ひまわり、なでしこ::
会場で最も注目を浴びていたと思う。自分も強く惹かれた。
ほんとうに読みやすそうだ。（日本人Only）
文書の充実もすごい。関数定義はできないんだろうか。。。

== VM魂 ==
プレゼンがどれもおもしろかったが、なんだか各実装の対決みたいなピリピリした空気がでていてちょっと苦手だった。

以後用事のため途中退席。ライトニングトーク見たかった。。。

TekTekBLOG

pypyで何も考えずにpythonを高速化する

Ajaxを補足するためのPythonによる手軽なマルチスレッド処理

PythonのUnicode->UTF-8変換はSJISやEUCへの変換よりもちょっと速い

関数呼び出しをタプル形式にして遅延させる関数

Djangoでblogっぽいのを作ったので移動します

はてブのホットエントリをなんとなーく分類するPythonスクリプトサンプル

Ward法のPythonバインディングを作りました。

C++のWard法->g++のオプションで驚異的な高速化

Python -> C++への移植でどれぐらい速くなったか

行列×行列さえ一瞬でできれば、文書のクラスタリングも一瞬でできそう

Ward法さらにキャッシュを効かせて高速に

Ward法再実装で少し速くなった

2ちゃんねる Pythonのお勉強 Part26よりParallel Python関係の議論抜粋

Ward法のパフォーマンスと分散処理のための考察

PythonでWard法によるクラスタリング

Parallel Pythonで分散処理

Erlangでベクトルの集合をクラスタリング（k-means）

pythonで英語の同義語などを取得する

日本語テキストのトピック分割

動詞も使うことにした。

表記揺れ対策

語の重みのバリエーション

TFベクトルではなく、TFIDF的ベクトルを使用

coderepos

Jython本を注文した

Python用の自動要約モジュールをcodereposにimportしたよ

NLTKでstemming

自分のサイトでのユーザーの視線の流れを調べてみる

NLTKで英文の文末判定

モンティ・ホール問題

partty

Google App Engineが待ち遠しすぎる。。。

Google App Engine と格闘中

Google App Engine SDKインストール編

MySQL5のFederatedはまだまだ使えないという話

PythonでLatent semantic analysis

optparseのhelp文で改行を生かす方法

「ケータイマルチキャリア高機能テスター」を使ってみるよ。

Amazon.comから尻を叩かれた話

TekTekモバイル for EZwebをオープンしました！

TekTekを作った時にお世話になったものリスト＋手のうち公開

TekTekをオープンしました

djangoのi18nのset_languageリダイレクトビュー

djangoの国際化アプリをOSXで作る時にはまる事。

djangoのgeneric viewsのobject_listでPythonの普通のlistを表示する

Macのある生活 （現実）

mod_pythonでLD_LIBRARY_PATHの設定

ハイフンっぽい文字を一括で半角マイナスに変換

[メモ]djangoのnewformsで半角英数のみのフィールド

[メモ]シェルでファイル名を数字でソート（２桁まで）

[メモ]djangoからloggingを使う場合のタイムゾーンはsettings.TIME_ZONEで決まる

[日記]過去の認識

[メモ]PILの良サンプル

[メモ]TODO: プログラミングGaucheを入手すること

Gaucheが相当に"電池内蔵"という話

末尾再帰重要

Schemeで重要語抽出を書いた感想

[日記]Schemeのレベル

[メモ]再帰を使うとn-gramはすっきり書ける

[メモ]MySQLでテーブル一覧でビューかどうか調べる方法。

Gaucheの練習: 連続する名詞の抽出

Schemeのmecabバインディング

PythonでHarwell-Boeing matrix

djangoのせいで

ユークリッドの互除法

[メモ]数学の記述ではやはりHaskellがPythonよりも上手ですが、変態的Pythonなら肉薄できそう

[メモ]MySQLのプロセス監視

[メモ]MySQLの最適なテーブル定義を知る方法

[日記]まだまだアッカーマン関数

[雑談]「これから一からプログラミングを覚えようと考えています。」

[日記]まだアッカーマン関数

アッカーマン関数やばい

[メモ]正規表現モジュール re のscanner機能

[メモ]有機ＥＬ

[メモ]djangoのmodelのカスタムSQLでujisのトラブル回避

言語の比較記事

あるPython信者がたどったHaskellの入り口までの道のり

[メモ]Python信者から見た、Javaを使いたくない理由

「Pythonをはじめよう」という記事が指摘しているPythonの良い点

Macのある生活（現実）