Python

グラフのはなし・その11

さて前回 mro のトポロジカルソートを使った実装までできたのですが, mro の失敗が検知できない不十分なアルゴリズムで実装してしまいました.今回はその不十分なところを修正するために, 今まで 2 つ (「未探索」と「探索済」) しかなかったノードの状態を 3…

グラフのはなし・その10

さて今回は C3 アルゴリズムをトポロジカルソートで書けることを示してみましょう. 戦略 さて C3 アルゴリズムの肝は何だったかと言うと, それぞれの親クラスにとっての祖先クラスの順序と, 親クラスどうしの順序が食い違わないように, 祖先クラスを並べるこ…

グラフのはなし・その9

今日は Perl や Python のクラスの多重継承で使われているアルゴリズム C3 を紹介します.多重継承でメソッドを呼び出した場合, 複数の親クラスを持つので今呼び出しているメソッドがどの親に属しているのかを調べなければなりません. そしてその順序も決めて…

グラフのはなし・その8

さて今日は目標の1つであったトポロジカルソートのプログラムを見てみましょう. 基本的な構造は昨日の深さ優先探索 (DFS) と同じです. 今日トポロジカルソートを行う DAG (輪っか無しの矢印グラフ) はこれです. 0 -> 1 -> 3 | `-> 4 | V `-> 2 -> 5 `-> 6昨…

グラフのはなし・その7

ちょっと今日は趣向を変えて, プログラムで語ってみます.昨日まで理論の話だったので, 少し頭を切り替えて Python で深さ優先探索を書いてみます. ソースコード こんなふうなグラフを 0 からスタートして深さ優先探索してみましょう. このグラフは DAG にな…

0 と 1 を次々返す方法

http://d.hatena.ne.jp/a2c/20100902/1283411959こんな記事があったので, ちょっとやってみた.とっても素直. x = 0 if x else 1 x = False if x else True x = not x ちょっと読みづらい. x ^= 1 x = x == False とりあえずこんなとこでしょうか. おまけ リ…

Python の黒魔術

このスライドにインスパイアされて書きました. このブログに議事録があります. 俺はここ半年くらい Python にはまり, 色々細かいところまで調べて勉強していました. その結果, このスライドに載っている Ruby コードを黒魔術と感じない身体になってしまいま…

python の内包表記で list の flatten を書く

(以下, Python 2.6.4 でやってます.)python には内包表記という filter, map, reduce の代替ができるような表記方法があります. 詳しくは検索してもらうとして, 今回のネタはその内包表記で flatten という関数を書こうというものです.flatten というのは, …