家事
起きた。
今日すること
- ■ 朝起きる
- □ 食器を洗う
- □ ペットボトルを洗う
- □ 郵便箱に郵便が溜まっていたので回収する
- □ いらないものを捨てる
- □ メールの返事を書く
- □ クレジットカードが使えなかったのでもしかすると銀行の預金額がショートしているかもしれない。記帳しに行く。でも普通、電話とかメールとかかかって来るよね。
- ■ 楽天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
あれあれ。意外と再起呼び出しが健闘するなぁ。再起版の方がメモリを無駄遣いするはずなのだけども、ループ版のポインタ演算のコストが高いせいで見えてこないのかな。