270 ー 6 章オブジェクト指向プログラミング def munge2(alist) : if type(alist) is list: mungel(alist) # たいへん悪い考え else: raise TypeError, "expected list, got %s" % type(alist) この方法も、 alist がリストのサプクラスであればそれだけで失敗する。 isinstance を使うと少しはましに なる。 def munge3(alist) : if isinstance(alist, list) : mungel(alist) else: raise TypeError, "expected list, got %s" % type(alist) extend(range(2)) a1ist[4] = a1ist[3] append(42) extend(range(5)) append(23) # 実行 . これ以降例外は発生しない except IndexError: pass # 空の alist でも問題ないように try: alist[o] = a1ist[0] # 場合に、なるべく早く例外を起こす : # 演算にこではインデクシング ) のチェック。シクネチャ互換でない extend = alist. extend append = alist. append # オブジェクトの部分変更は起きない # なければ、ここですぐさま例外が発生する。 # 必要なすべての結合メソッドを抽出してみる。もし必要なメソッドが def munge4(a1ist) : が実は存在する。 これらの方法よりもはるかにましな、ポリモーフィズムを犠牲にしない「石橋をたたいて渡る」的な方法 のように、たとえ isinstance を利用するにしても、型チェックには多大な代償が必要なのである。 の deque のように mungel では動くが、 munge3 では動かないというシーケンス型は無数に存在するだろう。こ 数をすべて提供しており、 mungel に渡すとばっちり動作するのに渡せないということは非常に残念である。 えば、 python2.4 の collections. deque のインスタンスは munge3 に渡すことはできない。この deque は必要な関 行うと、 python の素晴らしさの 1 つであるシグネチャベースのポリモーフィズムを犠牲にしてしまう。たと ないようなクラスや型のインスタンスである場合にはうまく動作しない。つまり、このように型チェックを しかし、 munge3 の方法を取ったとしても、 alist が list のように動作はするが実際には list を継承してい
する補助シーケンス ( リストまたはタブル ) を使ったものだ。 Iist0fRows を回すリスト内包の内側に入れ子にするのである。 4.7 列から成るリストのデータを行単位で削除 / 並べ替えー 165 私は二次元配列の表現にリストのリストをよく使う。こうしたリストのアイテムは、 " 二次元配列 " の " 列 " を構成するものだと私は考えている。そしてよくこの " 二次元配列 " の・・行 " に操作を加えるのだが、それ この補助シーケンスを回すリスト内包を、 newList = [ [row[ci] for ci in ( 0 , 3 , 2 ) ] for て in list0fRows ] 考察 最後に 1 つ。上に挙げた関数で、、内側の " リスト内包をもっと素敵に表現したいという方々がいる。彼ら 、こで関数 pi ( k and reorder columns により得られる一般性は、ちょうどいい塩梅だと思う。 トに対して実行され、それぞれが対応の " 新 " リストを得るというところが違う。過剰な一般化は破滅の罠 この例はレシピの他のコード片すべてと同じように行の並び替えと選択を行うが、 2 つの異なる " 旧 " リス newList0fCats = pick and reorder c01umns(01dList0fCats, columns) newList0fPandas = pick and reorder c01umns(01dList0fPandas, columns) columns = return [ [row[ci] fO て ci in column indexes] for row in list0fRows ] def pick and reorder c01umns(1ist0fRows, column indexes) : に名前を与え、これを関数の引数として渡すことにより、複数の列リストを同じように並び替えられるのだ。 このアプローチを採用すれば、潜在的な一般性を多少得ることになる。つまり補助インデックスシーケンス れ子とするについては、ちょっと吐気を催すかもしれないが、恐れているよりはシンプルで安全な物である。 の並びの行インデックスを保持する補助シーケンスを使うことを考えてみよう。 2 つのリスト内包を互いに入 このようにリスト表現を明示的にハードコードするのではなく、「解法」の第 2 例で示唆したように、望み list0fRows[ : ] = [ [row[o], て ow [ 3 ] , row[2]] for row in Iist0fRows ] えば「解法」の例にしたがい Iist0fRows をその場で変更したい場合、以下のように書けばよい・ い場合も、リスト内包を書いておき、それを元のリストの中に代入するのがベストアプローチである。たと リスト内包は既存のリストを変更せず、新しいリストを構築する。しかし既存リストをその場で変更した だからだ。 んて、一目瞭然ではない ( 少なくとも私にはそうではなかった ) 。他の種類のシーケンス操作に使われるもの はたいてい行の並び替えや、一部の行を飛ばすといったものだ。リスト内包がこうした用途に実に有用だな は次のような直裁なコーディング : [row[ci] fO て Ci in COlumn indexes] よりも、組み込み関数 map を使い、 row の結合メソッドである特殊メソッド グを実行することを好む。つまりこのようになる : COlumn indexes) map(row. getitem get it em によりインデクシン
] 章 に留めたのは、 thon2.3 が関数オプジェクトの属性 fun ( name をリードオンリーと見なすためだ。こっした テキスト 適した iStr サプクラスを使った ( iList の ) サプクラスを作るのも簡単だ。クラスレベルメンバー wrap each item ちなみにこのお手本の iList クラスは間違いのないコーディングがしてあるので、特定アプリケーションに 保証しているにすぎない。あとはアイテム自身が自分で全部面倒を見るのだ。 基本的には iList のインスタンスに入る各アイテムが iStr のコールによってラップされる、ということを list. extend(self, map(self. wrap each item, seq)) def extend(self, seq) : list. append(self, self. wrap each_item(item)) def append(self, item) : setitem list. (self, i, v) else: v = self. wrap each item(v) if isinstance(), slice): v = map(self. wrap each item, v) def setitem (self, i, v) : = iStr wrap each item = self self[ : ] # setitem に頼って各アイテムを iStr でラップ list. init (self, *args) def init_(self, *args) : class iList(list) : に ) 大文字小文字無関係に扱うリストを作ってみせよう。割と簡単だ・ それでは iStr に基づいて、基本的に文字列であるアイテムを (count 、 index といったメソッドやソートの際 字小文字無関係なコンテナ型を作るなど、文字列ラッピングが必要なときにすぐ使えるということだ。 というのは、明らかに優れたアーキティクチャだ。つまりレシピのコードを道具箱に仕込んでおけば、大文 付くかもしれない。比較や検索で大文字小文字が無関係になるという機能を要素分割し、一度だけ実装する とこれを大文字小文字無関係であるかのように扱うコンテナーーを、いつのまにやら楽々作ってる自分に気 スト、セットなど、多種多様な「大文字小文字無関係の」コンテナ型ー一文字列型のキーやアイテムがある Macintosh のデフォルトファイルシステムとの互換を取ることなど、さまざまだ。また、ディクショナリ、リ 高い許容性を与えたり、ファイル名のマッチングにこの方法を使って、 Windows のファイルシステムや 大文字小文字無関係の ( しかしこれを保存する ) 文字列型にはたくさんの用途がある。ユーザ入力の解釈に 細かい事柄のせいで互換性を失うことを避けたのである。 較やハッシュに使われる特殊メソッドの項。 ライプラリリファレンスおよび fPython クイックリファレンス』の str 型および文字列メソッドの項、比 参照 をオーバーライドするだけでよいのである。
5. O def sorted 2 3(iterable) : = list(iterable) alist alist. sort( ) return alist イントロダクション 195 リストのコピーもソートも重要なオペレーションであり、ヒ、ルトインの sorted もこれを実行することに変 ど理論的最小値にまで近づける。 れはクイックソートの最悪計算量 0 ( n2 ) の時間的ふるまいをほば防ぎ、一般的なケースでは比較の数をほとん るものだ ( 要素集合の大きなランダムサプセットをサンプル法で再起的にソートし、その中央値を選ぶ ) 。 法はクイックソートの変種で、分割を行う要素すなわちピポットの選択に非常に大きなサンプルサイズをと のハイプリッドに置き換えられ、この実装は Python 2.3 が出るまで 4 年以上も変更されなかった。サンプル python 1.5.2 で、クイックソートアルゴリズムはサンプル法 (sample so のと二分挿入法 (binaryinsenion so ゴリズムであった ! ど遅い場合がいちいち見つかり、 リリースごとに書き直された。クイックソートとは実はデリケートなアル そのうち thon は自前のクイックソートアルゴリズムを実装するまでに成長した。これは我慢できないほ うなるとコアを吐く qsort ルーチンはぐっと増えた。 ザ定義の一 ( mp ー関数はまた ( 非常識もしくは悪意によってか ) ソート中にリストを変更することがあるが、 1 つの list. sort が多数を呼び出すことがあるのだ。 qsort ルーチンによってはこれが処理できなかった。ユー ンもあった。ユーザ定義の一 ( mp ー関数は list. sort を呼び出すことがあるので、比較を行う副作用として、 ンもあった。リエントラント ( 複数の呼び出しから共通して使える ) でないためコアまで吐いてしまうバージョ でまちまちだったことがある。リストに同値が多かったり逆順に並んでいる場合に極端に遅くなるバージョ これがうまくいかなかったことにはいくつか理由があるが、第 1 には qsort ルーチンの質がマシンごとにまる 初期の , thon において、 list. so て t はプラットフォームの C ライプラリにある qsort ルーチンを使っていた。 Python ソーティング小史 史を書いておくのは、この意味でちょっと教訓的であろう。 ーで巧 hon のソーティングの歴 ターなアルゴリズムはまだ見つかりうるのだということに気付かされた ついたのは 4h0n2.4 からだが、実際には 2.3 の時点で既に認識されていた。こうしたことから我々は、べ これは Guido をして塚 thon の list. sort メソッドは以後常に安定、と宣言させるほどであった。この保証が ナルの相対位置が保持されるようになった ) ことである。新しい実装は大成功で、改良の余地もほとんどない。 たこと、ソートが「安定」になった ( 2 つの要素を比較して等しかったとき、ソート済みリストの中でオリジ ソートの実装が更新されたことである。目に見える変化としては、一般的なケースの多くでスピードが上がっ "PythonCookbook" 初版の出版以後、 thon のソーティングに起きた最大の変化といえは、、 thon2.3 で くリクエストされてきたからだ。 あるということだ。 thon2.4 では so て ted とて eversed が加わったが、これは 2 つの関数がここ数年非常によ 差があるのだ。逆に言えば、小さな関数の中にはビルトインの拡張を正当化できるほど広く使われるものも ある。たった 4 行でも毎回毎回コードしなければならないのと、いつでもどこでも使えることには、やはり わりはないので、 sorted を組み込みにすることに速度的なアドバンテージはなかった。便利にしただけなので
doctest を unittest で使う (Python2.4) return a 十 b TypeError: can only concatenate list (not "int") t0 list Traceback (most recent ( a11 last) : 3 " 任意の 2 つのオブジェクトの合計を返す。 def add(), b): 8.1 0 ー 355 name maln import doctest doctest. testmod( ) 行することができる。たとえば以下をファイル tes い oy. txt に入れてほしい ( クオートで囲む必要はない ) : は思わないだろう。塚 thon2.4 なら do ( test 群を別ファイルに分け、この「テストスイート」を unittest で実 間が読むようになってない、ユニットテストを簡単に書くためだけの用例の山で docst ⅱ ng を散らかしたいと 関数の docst ⅱ ng にちょこちょこ入れた用例を do ( test でチェックできるのはすごい。しかし、本当には人 OK Ran 1 test in 0.003S シェルのコマンドプロンプトから python toy. py と入力して実行してやると、以下のようになる : unittest. TextTestRunner( ). run(suite) suite = doctest. DocFileSuite('test toy. txt' ) import doctest, unittest そして toy. py の最後、 import doctest 以降を、以下と差し替える : TypeError: add() takes exactly 2 arguments ( 3 given) Traceback (most recent ( a11 last) : 〉 > 〉 toy. add(), 2 , 3 ) TypeError: add() takes exactly 2 arguments ( 0 given) Traceback (most recent ( a11 last) : > > > toy. add( ) > 〉〉 toy. add('a' 〉〉〉 import toy
1 章テキスト この memoizing の裏にあるのは、高コストなフォーマット準備を引数の組合わせごとに一度だけ行う ( それ から cache ディクショナリに格納する ) という考え方だ。もちろん他すべての最適化と同様、パフォーマンス 計測による評価で memoizing が本当にスピードアップにつながっているかチェックする必要はある。この場合、 memoizing を導入したことによるスピードアップは 30 ~ 40 % 程度であり、つまりこの関数がプログラムのパ フォーマンスポトルネックになっていない限り、やるだけの価値はないだろうということだ。 さて、「解法」のコード片でリスト内包を使ったものと等価の関数は以下のようになる : return split at(the line, xrange(), len(the line), n), lastfield) def split by(the line, n, 1astfie1d=Fa1se) : yield the line[last: ] if lastfield: last = cut yield the line[last:cut] fO て cut in cuts: last = 0 def split at(the line, cuts, lastfield=Fa1se) : まったく違ったアプローチとしては、ジェネレータを使うものがある : どちらの場合も struct. unpack よりリスト内包を使う方がわすかに好ましいことが判っている。 return pieces pieces. pop( ) if not lastfield : # 最後の断片が必要とされない場合は捨てる pleces = [ theline[i:j] for i, j in zip([0] + cuts, cuts + [None]) ] # 必要な大きさの断片に刻む def split at(theline, cuts, lastfield=False): 最後に挙げたコード片はこうなる : return pieces pieces. pop( ) if not lastfield and len(pieces[-l]) く n: # 最後の断片が短かく、かっ必要とされない場合は捨てる P1eces = [theline[k:k + n] f0 て k in xrange(), len(theline), n)] # 必要な大きさの断片に刻む def split by(theline, n, lastfield=Fa1se) : ジェネレータにピルトインの list をコールしてやればよい も ) 。フィールドのリストを実体化する必要があるのにジェネレータしか使えない、という場合には、その という場合に最適だ ( 明示的なループでも、 . j0in のように暗黙的な「アキュムレータ」をコールする場合で ジェネレータベースのアプローチは、その結果であるフィールドのシーケンスにはループが掛けたいだけ、
ート 5.4 キーやインデックスを、その値によりソ ー 203 5.4 キーやインデックスを、その値によりソート credit: John Jensen, Fred Bremmer, Nick Coghlan 訳 : 鴨澤眞夫 問題 さまざまなアイテムの出現度数を調べ、出現度数順にソートする必要がある。たとえばヒストグ ラムを作るためである。 解法 ストやディクショナリなら簡単 ) し、続いてキーやインデックスを ( 対応の ) 値でソートすることだ。この 2 つ ヒストグラムの基盤とは、グラフィックの問題を別にすれば、アイテムの出現度数をカウント ( thon のリ のメソッドを加えた dict のサプクラスは、以下のようになる : class hist(dict) : def add(self, item, increment=l) : increment を item のエントリに加える self[item] = increment + self. get(item, 0 ) def counts(self, reverse=False) : ー対応の値でソートしたキーのリストを返す一 = [ (self[k], k) k in self ] aux aux. sort( ) if reverse: aux. reverse( ) return [k for v, k in aux] 数えるアイテムが小さな範囲の整数で表現できるものであり、 下となる。解は非常に似たものである : class histl(list): init_(self, n): def リスト中に出現度数を保持したい場合は以 ー n 個の異なるアイテムの出現度数を数えられるようにリストを初期イい init_(self, n*[o]) list. def add(self, item, increment=l) : increment を item のエントリに加える self[item] + = increment def counts(self, reverse=Fa1se) : ' 対応の値でソートしたインテックスのリストを返す ' = [ (), k) f0 て k, v in enumerate(self) ] aux aux. sort( ) if reverse: aux. reverse( ) return [k for v, k in aux]
204 ー 5 章サーチとソート 考察 hist の add メソッドは、 thon で普通に使われるイディオムを体現したものだ。任意の ( ハッシュ可能な ) アイテムの出現度数を数える際に、カウントの保持に dict を使うのである。クラス histl はリストに基づき、 init ですべてのカウントを 0 に初期化するというアプローチをとっているため、 add メソッドがさらにシ ンプルになっている。 counts メソッドはキーまたはインデックスのリストを生成し、これを対応する値の順序でソートする。 hist と histl 、両クラスで問題は非常に似通っている。ゆえに解もほとんど同じで、両者とも「レシピ 5.2 文字列 リストを大文字小文字無関係にソート」でも示した DSU アプローチを使う。プログラム中で hist も histl も 使う場合は、共通部を抜き出して副関数 sorted keys を作るべきだろう : def sorted keys(container, keys, reverse) : 'container' の値でソートしたキー 'key ・のリストを返す ' ・ = [ (container[k], k) for k in keys ] aux aux. sort( ) if reverse: aux. reverse( ) return [k fo て v, k in aux] そして両クラスの counts メソッドは、 class hist(dict) : この sorted keys に薄いラッパをかけて実装する : def counts(self, reverse=FaIse) : return sorted keys (self, self, reverse) class histl(list) : def counts(self, reverse=Fa1se) : return sorted keys(self, xrange(len(self)), reverse) 「レシピ 5.2 文字列リストを大文字小文字無関係にソート」および「レシピ 5.3 オプジェクトのリストをオ プジェクトの属性でソート」で既に示したように、 DSU とは、 thon2.4 においてはリストの so て t メソッド や新しいビルトイン関数 so て ted によって高速で本質的な実装がなされるほど、重要なものである。そしてこ れゆえ、 thon2.4 の sorted keys 関数はすっとシンプルかつ高速になる : def sorted keys(container, keys, reverse) : return sorted(keys, key=container. getitem , reverse=reverse) 、 getitem は、 Python 2.3 版の sorted keys にあった、 container[k] によるインデッ 結合メソッド container. クスづけと同一のオペレーションを行う。ただしこれはコーラブルであり、ソートするシーケンスの k それぞ れに対して呼び出されるものである。ちなみにこのシーケンスの名は keys だ ビルトイン関数 sorted に渡 すキーワード引数 key の値として、実に正しいでしよ。ディクショナリのアイテムを値でソートしたリストを 得ることについても、 thon2.4 では簡単で直裁な方法がとれる :
252 ー 6 章オブジェクト指向プログラー > 〉〉 a. append(23) 1 ニング インデクスやスライスといった機能は使えない。 iter メソッドも渡されているので、 for ループや、 list 、 sum 、 max などのビルトイン関数で実行される TypeError: unindexable object line 1 in ? FiIe " く interactive input 〉 " Traceback (most recent ( a11 last) : く method-wrapper object at 0X010FIAF0 〉 getitem しかし _getitem_ メソッドは委譲されないので、 [ 2 引 > 〉〉 list(a) 〉〉〉 for X in a: print X 内部ループも予想通りに機能する。 「レシピ 6.5 継承ではできないことをする ( 自動委譲 ) 」では自動委譲についての詳しい情報が書かれている。 参照 戻り値として返す。インスタンスを作る際の引数は、ラップされるオプジェクトである。 作成したかキャッシュから取り出したかに関わらず、 proxy はプロキシクラスのインスタンスを作り、最後に 新たにプロキシクラスを作ると、 proxy 関数はそれを known_proxy classes に適切なキーで保存する。新たに いる。 ( すなわちラップされたオプジェクト self. obj) をつけてアンバウンドメソッドをコールする部分を担って クロージャに閉じ込め、新しいクラスの属性としてセットすることで行う。 make binder は、適切な第 1 引数 はラップされるオプジェクトのクラスからアンバウンドメソッドとして取得した特殊メソッドを make binder クラスからの通常属性の委譲を行う。続いて proxy が特殊メソッドを 1 っすつ新しいクラスに委譲する。これ こではまだクラス属性をまったく与えていないからだ。べースクラス P て oxy は、初期化および元 書なのは、 という名前で、 P て oxy クラスを唯一のべースクラスとした新しいクラスを作成する。 type の第 3 引数が空の辞 クラスが保存されている。 p て oxy 関数は組み込み関数 type を呼び出して、「くラップされるオプジェクトのクラス名 > proxy 」 classes には、ラップされるオプジェクトのクラス名と委譲する特殊メソッド名を並べたタブルをキーとして、 proxy 関数は過去に生成されたクラスについてキャッシュを行っている。グローバル変数の辞書 known ー proxy ー
222 ー 5 章サーチとソート except KeyError: raise VaIueError def wrapMutatorMethod (methname) : = getattr(list, methname) method def wrapper(self, *args) : # フラグ dictionary OK をリセットした後、実際のミューテータメソッドに委譲 self. dict ok = Fa1se return method(self, *args) # Python 2.4 のみ : wrapper. method. setattr(list with aux dict, methname, wrapper) for meth in 'setitem delitem setslice delslice iadd' . split( ) : wrapMutatorMeth0d (' %s ・ % meth) for meth in 'append insert pop remove extend' . split( ) : name name wrapMutatorMethod(meth) del wrapMutatorMethod # 以降不要な補助関数を削除 クラス list with aux dict は list を拡張し、 contains と index 以外の全メソッドを list に委譲する。リ ストのメンバを変更しうるメソッドはすべて、補助ディクショナリの 0K フラグをリセットするクロージャに ラップされている。 thon の in オペレータは contains メソッドをコールする。そして list with aux dict の contains メソッドは、 OK フラグが立っていないと補助ディクショナリを再構築する ( フラグが立ってい れば再構築の必要はない ) 。 index メソッドも同様だ。 こでは補助関数により、 list with aux di ( t クラスで変更される list のメソッド全てにクロージャを構築 したが、これらはすべて list with aux dict のラッパーメソッドとして、クラス本体に def 文で書き連ねるこ とも可能である。しかし上に示したコードには、ポイラープレート ( 綿密な繰り返しのコードで、退屈かっ多 量、それゆえバグの温床となるもの ) が最小限になる、という重要な利点がある。内観 (introspection) と動的 変更において thon の持つ力が、この選択肢を提供する。つまり、レシピで示したようにスマートかっ簡潔 にメソッドラッパーを書くことも、クラスオプジェクトの内観と動的変更のプラックマジック、などと呼ば れそうなことは避けてポイラープレート・コードを書くこともできるのだ。 list with aux dict のアーキティクチャは、割とよくあるパターンで有効だ。すなわち、ますシーケンス変 更がまとめて行われ、続いて、変更はないが存在テストが何度も行われる期間に入る、という場合だ。これ に対し、先の addUnique_simp1e 関数のケースでは、存在テストとシーケンス変更を交互に行うため、 baseList として list の代わりに list with aux dict のインスタンスを使っても、パフォーマンスの向上は見込めない。 list with aux dict の補助ディクショナリ再構築が頻繁に行われすぎて、関数の実行が妨げられるのだ ( ただし baseList の中に 0therList のアイテムのほとんどが最初から含まれており、かっシーケンス変更が存在テスト の回数に比べてかなり少ないのが普通という場合では有効 ) 。 ところで、こで挙げた存在テスト最適化手法には、重要な必要条件がある。シーケンスの値はハッシュ 可能でなければならないのだ ( でなければ dict のキーや set のアイテムになれない ) 。たとえばタブルのリス トはレシピのやり方で扱うことができるが、リストのリストではまったく不可能である。 参照 ライプラリリファレンスおよび fPython クイックリファレンス』のシーケンス型およびマッピング型に関