家事

起きた。


今日すること

  • ■ 朝起きる
  • □ 食器を洗う
  • □ ペットボトルを洗う
  • □ 郵便箱に郵便が溜まっていたので回収する
    • □ いらないものを捨てる
  • □ メールの返事を書く
  • □ クレジットカードが使えなかったのでもしかすると銀行の預金額がショートしているかもしれない。記帳しに行く。でも普通、電話とかメールとかかかって来るよね。
    • 楽天KCの明細をwebで見ようとしたらシステムが変わっていたので会員登録をしている。□ 引っ越し後住所変更する
  • □ 部屋を片付ける
  • □ 地図
  • □ ヘッドホン
  • □ GAEのプロジェクトの作り方をまとめる
  • Mercurialのbisectについて

そのた

  • 15 新居鍵受け取り
  • 18 資源ゴミの日。いらない新聞・雑誌などを可能な限り捨てまくる
  • 20 鍋 / 楽天カードの引き落とし
  • 28 現住所鍵返却
  • 近いうちに散髪する(次に秋葉に行ったときでいいか)

型の宣言をしてコンストラクタでassert

なんかJava的な頭で設計しているとこんなことを書きたくなったりするじゃない。「ヒットポイントは整数でー」と。実際にはPythonではこういう書き方はしないわけだけど。

class Monster(object):
    hitpoint = int
    defense = int
    attack = int

で、コードをいきなり書かずにこういう書き方で設計を練っていたので、せっかくだからそれを有効活用するというのはどうだろうかと思った。コンストラクタの終了時のアサーションに使う。

class Monster(object):
    field_types = dict(
        hitpoint=int,
        defense=int,
        attack=int,
    )
    def __init__(self, **kw):
        self.__dict__.update(kw)

        for k, v in self.field_types.items():
            assert isinstance(getattr(self, k), v)

「Monster(attack=1, defence=1, hitpoint=1)」なんて感じにミスタイプをするとassertで止まる。fail-fast。メタクラスで「__init__の最後にこういう処理をする」ってのを自動的に付け加えることもできるけど、さすがにちょっとやりすぎな感じがするなぁ。

好きな言葉「必要かどうか悩むようなものは必要ない」

いつも正確な表現がわからなくて探すはめになるのでここに書いとこう。

"Metaclasses are deeper magic than 99% of users should ever worry about. If you wonder whether you need them, you don't (the people who actually need them know with certainty that they need them, and don't need an explanation about why). -- Python Guru Tim Peters"

「必要かどうか悩んでいるなら、それはあなたには必要ないんだよ。本当にそれが必要な人は、『それが必要だ』と確信している。なぜ必要かなんて説明する必要もないんだ。」

Pythonメタクラスの話なんだけども、言語の機能に限らずもっと普遍的な真理だと思う。これをつぶやきながら部屋の掃除をしよう。

クイックソート

リハビリ第2弾(ref. スランプ脱出法, フィボナッチ数列)


from random import shuffle
data = range(100)
shuffle(data)

# recursion
def qsort(data):
    if not data: return data
    pivot = data[0]
    rest = data[1:]
    greater = [x for x in rest if x > pivot]
    lesser = [x for x in rest if x <= pivot]
    return qsort(lesser) + [pivot] + qsort(greater)

print qsort(data)


ループ版難しい。これじゃ1回しかpivotで振り分けてないしな…

# loop
def qsort_loop(data):
    """
    ... pivot a b c ... last done ... のとき
    if a < pivot:
        ... a pivot b c ...
    else:
        ... pivor b c ... last a done ...
        が素朴だけどどこれはコピーがたくさんあるので
        ... pivor last b c ... a done ...

    """
    if not data: return data
    pivot = data[0]
    cur = 1
    done = len(data)
    while cur != done:
        v = data[cur]
        if v < pivot:
            data[cur - 1] = v
            data[cur] = pivot
            cur += 1
        else:
            data[cur] = data[done - 1]
            data[done - 1] = v
            done -= 1
    
    return data

print qsort_loop(data)



できた。

# loop
def qsort_loop(data):
    """
    ... pivot a b c ... last done ... のとき
    if a < pivot:
        ... a pivot b c ...
    else:
        ... pivor b c ... last a done ...
        が素朴だけどどこれはコピーがたくさんあるので
        ... pivor last b c ... a done ...

    """
    stack = [(0, len(data))]
    while stack:
        start, end = stack.pop()
        print (start, end)
        if end - start <= 1: continue
        pivot = data[start]
        cur = start + 1
        done = end
        while cur != done:
            v = data[cur]
            #print data
            #print cur, done, pivot, v
            if v < pivot:
                data[cur - 1] = v
                data[cur] = pivot
                cur += 1
            else:
                data[cur] = data[done - 1]
                data[done - 1] = v
                done -= 1

            #print data
            #print
        stack.append((start, cur - 1))
        stack.append((cur, end))
    
    return data

print qsort_loop(data)

最初

-        stack.append((start, cur - 1))
-        stack.append((cur, end))
+        stack.append((start, cur))
+        stack.append((cur + 1, end))

ってなっていて大体ソートし終わった最後にぐちゃぐちゃになっていた。コメントアウトしてあるprint文を補ってrange(5)にして流れを追ってみた。



速度の比較

from time import clock

def profile(n):
    print n,
    original_data = range(n)
    shuffle(original_data)
    data = original_data[:]

    t = clock()
    qsort(data)
    print clock() - t,

    data = original_data[:]
    t = clock()
    qsort_loop(data)
    print clock() - t

for i in range(13):
    profile(100 * (2 ** i))
100 0.000448 0.000429
200 0.000967 0.001027
400 0.002129 0.002277
800 0.004327 0.005072
1600 0.00907 0.011751
3200 0.018466 0.022997
6400 0.039396 0.050003
12800 0.085261 0.112591
25600 0.171988 0.224489
51200 0.362911 0.484281
102400 0.767855 1.092627
204800 1.677372 2.279966
409600 3.564921 4.905796

あれあれ。意外と再起呼び出しが健闘するなぁ。再起版の方がメモリを無駄遣いするはずなのだけども、ループ版のポインタ演算のコストが高いせいで見えてこないのかな。