システムデフォルト以外の Python での pyflakes

特定バージョンの Python を使用するために、Prefix を指定して手動でコンパイルした環境で vim から pyflakes を使用しようとしたのですが、以下のようなエラーが出てしまいます。

AssertionError: Vim must be compiled with Python 2.5 or higher; you have 2.4.3

手動コンパイルした Python は 2.7 で、virtualenv の環境から実行しているため、そちらを見に行くのかと思いましたが、どうもシステムデフォルト（/usr/bin/python）を見ている様子。

$ which python
~/.virtualenvs/foobar/bin/python
$ python -V
Python 2.7.2

ここを見ると、環境ごとに vim のビルドが必要（！）と書かれている。とりあえず、試してみる。

$ LD_LIBRARY_PATH=$HOME/.virtualenvs/foobar/lib
    PATH=$HOME/.virtualenvs/foobar/bin:$PATH \
    ./configure --enable-pythoninterp \
    --with-python-config-dir=$HOME/.virtualenvs/foobar/lib/python2.7/config \
    --prefix=$HOME/vim27

$ make install

ビルドした vim から pyflakes を使用してみるとエラーは出なくなっている。バージョンを確認しても手動でコンパイルした Python を見ているようだ。

:python import sys; print(sys.version)
2.7.2

vim から呼び出す Python は、コンパイル時に指定されているんですね。目的は果たせたけど、、他に方法はないものか。

PyPy を試してみる

ときどき Project Euler の問題をしているのですが、そのまま書いてしまったため、結果の出力にすごく長い時間のかかるコードをふと PyPy で実行してみると、あまりの速度にびっくり。

#!/usr/bin/env python

result = 0
i = 20
while True:
    for num in range(1, 21):
        if not i % num == 0:
            break
    else:
        result = i
    if result:
        break
    i += 1
print result

$ time pypy problem5.py 
real    0m35.395s
user    0m34.910s
sys     0m0.090s

$ time python problem5.py 
real    5m19.202s
user    5m15.520s
sys     0m0.070s

テストではないけれど、PyPy のすごさを垣間見た気分。

ビット演算って

どういった時に使用するのか、よく分からなかったビット演算。MACアドレスが正しいフォーマットか調べる必要があって、ここのコードを参考にしていた時に、こういう使い方があるのかと思ったのでメモ。

def _mac2int(addr, sep=_MACsep):
     # convert a MAC str to an int
    h = addr.split(sep)
    if len(h) > 4:
        i = 0
        for b in h:
            b = int(b, 16)
            if 0 <= b < (1<<8):
                i = (i << 8) | b
            else:
                break
        else:
            if 0 < i < (1<<48):
                return i
    raise ValueError('invalid MAC address: %r' % (addr,))

MACアドレスの文字列を int に変換している関数で、失敗すると ValueError になるようになっています。 その中でビット演算が使用されているのですが、分かりやすくするために'FF:FF'を変換するとした場合、まず左側の'FF'を int に変換します。

>>> int('FF', 16)
255
>>> bin(255)
'0b11111111'  <= 2進数にするとこうなる

次に、最初に変換した部分を 8bit 左にずらして、同様に次の'FF'を int に変換し、ビットOR をとる。

>>> 255 << 8
65280
>>> bin(65280)
'0b1111111100000000'
>>> bin(255)
'0b11111111'
>>> 65280 | 255
65535
>>> bin(65535)
'0b1111111111111111'
>>> bin(0xFFFF)
'0b1111111111111111'

結果、0xFFFF を int に変換したのと同じになります。MACアドレスは ６オクテットなので、これを６回繰り返すとMACアドレスを int に変換できるんですね。勉強になりました。

ヒープソート

C言語のアルゴリズム本を見ながら、Pythonにて書き換えてみる。
ヒープソートはこんな感じ。

def downheap(buff, parent, bottom):
    tmp = buff[parent]

    while True:
        cl = parent * 2 + 1
        cr = cl + 1

        if cl >= bottom:
            break
        if cr < bottom and buff[cl] < buff[cr]:
            cl += 1
        if tmp > buff[cl]:
            break

        buff[parent] = buff[cl]
        parent = cl
    buff[parent] = tmp


def heapsort(buff):
    size = len(buff)
    for i in range(size / 2 - 1, -1, -1):
        downheap(buff, i, size)

    for j in range(size - 1, 0, -1):
        tmp = buff[j]
        buff[j] = buff[0]
        buff[0] = tmp

        downheap(buff, 0, j)

if __name__ == '__main__':
    data = [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]
    heapsort(data)
    print data

書き換えながら、ループを抜ける判定条件に悩む。どうして'A >= B'になるのか理解できなかったけれど（AとBがイコールになることはあるの？）、デバッガの助けを借りて解決。デバッガ便利ですね。

$ pdb heap.py 
> /tmp/heap.py(4)()
-> def downheap(buff, parent, bottom):
(Pdb) b 12, cl == bottom
Breakpoint 1 at /tmp/heap.py:12
(Pdb) r
> /tmp/heap.py(12)downheap()
-> break
(Pdb) p parent, cl, bottom
(3, 7, 7)
(Pdb) c
> /tmp/heap.py(12)downheap()
-> break
(Pdb) p parent, cl, bottom
(0, 1, 1)

collectionsモジュール

EuroPython 2011 のレポートを見て知ったのですが、python 2.7 で Counter というクラスが追加されているんですね。

リスト内の要素数をカウントしたい時、こんな感じで書いていましたが、

>>> cnt = {}
>>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
...     cnt[word] = cnt.get(word, 0) + 1
...
>>> cnt
{'blue': 3, 'green': 1, 'red': 2}

Counter を使うとこんな感じで書けます。

>>> from collections import Counter
>>> cnt = Counter()
>>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
...     cnt[word] += 1
... 
>>> cnt
Counter({'blue': 3, 'red': 2, 'green': 1})

すっきりしていて、いいですね。

Python の hash関数

Google Code University に Gruyere というデモサイトを使って、Webアプリケーションの脆弱性と対策を説明しているガイドがあります。

少しずつ読み進めているのですが、cookie処理の部分について少し調べてみました。

gruyere.py (601行目)

def _CreateCookie(self, cookie_name, uid):
    ....
    h_data = str(hash(cookie_secret + c_data) & 0x7FFFFFF)

発行するcookieにハッシュ値を付与している部分ですが、「Pythonのhash関数はセキュアでないため、"違う文字列で同じハッシュ値" を短い時間で発見できる」と説明されています。

そうすると cookie_secret を知らなくても、cookieの改ざんができてしまうため、この用途にhash関数は向いていないとのこと。対策として「セキュアなhash関数を使用する」とあるので、hashlib などを使用するべきなのかな。

そもそも、Pythonのhash関数は dict での使用に適するようにされていて、ランダムよりも（末尾の文字がインクリメントされるような）よく似たケースにおいて規則的な変化をする性質を重視していると dictobject.c のコメントに書かれているんですね。

python/Objects/dictobject.c

/*
Major subtleties ahead:  Most hash schemes depend on
having a "good" hash function, in the sense of simulating
randomness.  Python doesn't:  its most important hash
functions (for strings and ints) are very regular in
common cases:
'''
>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]

また、Pythonのhash関数はFNVというアルゴリズムに近いものだそうだ。

FNV-1 hash algorithm

hash = FNV_offset_basis
for each octet_of_data to be hashed
    hash = hash  FNV_prime
    hash = hash XOR octet_of_data

python/Objects/stringobject.c

string_hash(PyStringObject *a)
{
    ...
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;

この辺りがそうなのかな。
きちんと理解できるように、がんばらねば。