Python Sapporo ? から帰宅

感謝

今月の Python 札幌は中止だったのだけど、それにもかかわらず 3 名の勇者さまが簡易オフしてたので乱入。 id:sumim さんとお話しする機会に恵まれまして、 Smalltalk 愛、プログラミング愛を見せつけられました。あぁ、それとくらべてオレの甘いこと。よい刺激になりました。

id:shuji_w6e さん Chuta さんとは Django でフォーム処理。 Django は最近使ってみたばかりなので復習といったところ。でも一人でやるのとはまた違って新鮮でした。ありがとうございます。

今後解く問題たち

id:shuji_w6e さんから「アルゴリズムの問題と GUI 実装を組み合わせると面白い、たとえばマージソートのソートされていく様を描画してみるとか」と提示されたので、今後、なにかのアルゴリズムと格闘してみることにする。

id:sumim さんからは「居眠り床屋問題」を掲示されたので今からがんばる、といいたかったけれどお風呂にはいったら旅疲れがどっとでたので、明日からがんばる、といってみる（完成しないフラグ立った）。キーワードは Actor Model とか STM とか。

帰りの電車 4 時間半を退屈せずにすむように『ビューティフルコード (THEORY/IN/PRACTICE)』を買ったら「24 章美しきかな、並列」が Haskell STM だったのは不思議な一致。 Haskell を知らなくても読めるように配慮されていたので STM への理解が進んだ。いいかんじ。でもこの章、 Haskell の型システムの恩恵にあずかれば STM を楽観的実行で実装するにあたって記録すべきことが最小限ですむので Haskell はすばらしい、という話が STM 便利だよね、という話より目立っている気がするのはなぜだろう？

でも、Haskell すげぇ、こんどやってみようかと思っているオレがいるのはなんでだろう。他人の意見にながされやすすぎだ。

1から10までの自然数の合計

床屋のかわりに今日寝る前の数分でできそうな別の問題を空気読まずにやってみる。「1から10までの自然数の合計」を Python で。http://d.hatena.ne.jp/sumim/20091004 経由で知った、とあるベンチャー企業の面接用につかわれたらしい問題。考え方を見るための。

sum(xrange(1, 11))

あっさりしすぎなので別解。

import operator
reduce(operator.add, xrange(1, 11))

え？空気読めって？等差数列の和の公式？ (1+10)*(10-1+1)/2 ？

def sum_seq_of_numbers(start, end):
    return (start + end) * (end - start + 1) // 2
sum_seq_of_numbers(1, 10)

圧迫感が足りないな（意味不明）。おぼえたての Python/C API で書いてみた。脱線開始。もはや Python ではなくて C 言語。できあがったものは Python 版と比べてコードが長いくせに、扱える値の大きさに制限が加わっている。

引数に C の long 型におさまらないほど大きい数字を入れると OverflowError というあまり見かけないエラーに遭遇できたりする。また引数は収まっていても計算結果は収まりきらないほど大きい場合、戻り値は期待するものとは異なるがエラーは送出されないという罠あり。割る 2 が最後にあるので long の半ばでもダメ。

x.c

#include <Python.h>

static PyObject *
x_sum_seq_of_numbers(PyObject *self, PyObject *args) {
    long start, end;
    if (!PyArg_ParseTuple(args, "ll", &start, &end)) {
        return NULL;
    }

    return Py_BuildValue("l", (start + end) * (end - start + 1) / 2);
}

static PyMethodDef x_method[] = {
    {"sum_seq_of_numbers", x_sum_seq_of_numbers, METH_VARARGS, NULL},
    {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC initx(void) {
    (void) Py_InitModule("x", x_method);
}

setup.py

from distutils.core import setup, Extension

extensions = [Extension('x', sources = ['x.c'])]

setup(ext_modules=extensions)

実行結果

>>> import x
>>> x.sum_seq_of_numbers(1, 10)
55

C の long に変換するから Overflow するわけで、 Python オブジェクトのまま計算すれば…ってめちゃくちゃながいよ！ (start + end) * (end - start + 1) // 2 するだけなのに。

static PyObject *
x_sum_seq_of_numbers(PyObject *self, PyObject *args) {
    PyObject *start, *end;
    PyObject *result = NULL;
    PyObject *i1 = NULL, *i2 = NULL;
    PyObject *temp1 = NULL, *temp2 = NULL, *temp3 = NULL,
             *temp4 = NULL;

    if (!PyArg_ParseTuple(args, "OO", &start, &end)) {
        goto error;
    }

    i1 = PyInt_FromLong(1);
    if (i1 == NULL) goto error;

    i2 = PyInt_FromLong(2);
    if (i2 == NULL) goto error;

    temp1 = PyNumber_Add(start, end);
    if (temp1 == NULL) goto error;

    temp2 = PyNumber_Subtract(end, start);
    if (temp2 == NULL) goto error;

    temp3 = PyNumber_Add(temp2, i1);
    if (temp3 == NULL) goto error;

    temp4 = PyNumber_Multiply(temp1, temp3);
    if (temp4 == NULL) goto error;

    result = PyNumber_Divide(temp4, i2);

error:
    Py_XDECREF(i1);
    Py_XDECREF(i2);
    Py_XDECREF(temp1);
    Py_XDECREF(temp2);
    Py_XDECREF(temp3);
    Py_XDECREF(temp4);

    return result;
}

参照の所有権についての素人なりのメモ

CPython のメモリ管理は参照カウンタ型なので、カウンタをどこで減らすのかがとても重要。そのため、『Python/C API リファレンス 1.2.1.1 参照カウントの詳細』には「参照の所有権」という概念について書かれていた。所有権を持つものが、不要になった際に権を放棄する、すなわち参照カウンタをデクリメントする義務を負う、とのこと。

各 API が参照の所有権を渡してくるのか、貸してくれるだけなのか、また、借りていくのか、盗んでいくのか（ごくまれ）を知るにはドキュメントを読む。

PyArg_ParseTuple にて得られるのは借用参照であり、参照の所有権は得られない。 PyNumber_Add などの戻り値は新たな参照（所有参照）であり、所有権を渡され、得ることとなる。

PyNumber_Add などの引数に参照を渡しても、所有権は貸すだけなので失わない。今回は使っていないが PyTuple_SetItem などの引数に参照を渡すと、所有権を盗まれ、失う。

参照カウンタのデクリメントは Py_DECREF マクロで行う。 NULL チェックが必要ならば Py_XDECREF マクロを使うと楽になる。 Py_DECREF には NULL を渡してはならないが、 Py_XDECREF は NULL を無視してくれるので。

今回作ったコードにおける、参照の所有権についてのメモ

start, end には PyArg_ParseTuple によって借用参照が収められる。これらの参照カウンタを勝手にデクリメントしてはならない。 temp1 〜 temp4, i1, i2, result は PyNumber_Add などで代入が行われた後は所有参照が収まっている。不要になったら参照カウンタをデクリメントしなければならない。ただし、戻り値となる result の所有権は呼び出し元に譲るため不要とはならない。関数の終了の瞬間まで保ち続ける、つまり参照カウンタを減らさないようにする。

今回は所有権のある参照が 1 つや 2 つではなく、 7 つも出来上がるため、エラー処理が面倒。もし失敗に気づいたら「すでに作ってしまったものを選んで Py_DECREF」ではコードを書く手間がかかるし後日コード読む際、エラー処理に本来の処理が埋もれて読みにくいことこの上ない。

なので不要となる参照は関数終了直前で Py_XDECREF をつかってデクリメントすることとし、エラー処理は goto 文で Py_XDECREF らの直前に飛ばすことで行うようにした。あと、 Py_XDECREF でも未初期化の変数は受け付けられるわけがないので、変数宣言時に NULL に初期化しておく。

    /* マジメにエラー処理してみた例。メイン処理はたったの 6 行。*/
    i1 = PyInt_FromLong(1);
    if (i1 == NULL) {
        return NULL;
    }

    i2 = PyInt_FromLong(2);
    if (i2 == NULL) {
        Py_DECREF(i1);
        return NULL;
    }

    temp1 = PyNumber_Add(start, end);
    if (temp1 == NULL) {
        Py_DECREF(i1);
        Py_DECREF(i2);
        return NULL;
    }

    temp2 = PyNumber_Subtract(end, start);
    if (temp2 == NULL) {
        Py_DECREF(i1);
        Py_DECREF(i2);
        Py_DECREF(temp1);
        return NULL;
    }

    temp3 = PyNumber_Add(temp2, i1);
    if (temp3 == NULL) {
        Py_DECREF(i1);
        Py_DECREF(i2);
        Py_DECREF(temp1);
        Py_DECREF(temp2);
        return NULL;
    }

    temp4 = PyNumber_Multiply(temp1, temp3);
    if (temp4 == NULL) {
        Py_DECREF(i1);
        Py_DECREF(i2);
        Py_DECREF(temp1);
        Py_DECREF(temp2);
        Py_DECREF(temp3);
        return NULL;
    }

銀月の符号

Python 使い見習いの日記・雑記