話すようにプログラムするPythonチュートリアル
Pythonでえらくハッキッシュなコードを書き散らして遊んだ
3の倍数と3が付く数字だけアホになり、5の倍数だけガルマっぽくなるスクリプトにチャレンジ - なんたらノート 第二期
うえ、他人のエッセイをえらくこき下ろし
OOコード養成ギブス - rants
OOコード養成ギブスとやらが人気らしい。 - なんたらノート 第二期
て、われながら生産性のないやつだと思うので、ここは逆に、Pythonチュートリアルをひとつ書いてみようと思います。
まず最初に、こんなプログラムがあったとさ。
#素数の数列を返すアルゴリズム def prime_numbers_until(limit): prime_numbers = [] for n in range(2, limit): divider_found = False # 1より大きくその数より小さい範囲で調べる for m in range(2, n-1): # 割り切れるか if n % m == 0: divider_found = True break # 割りきれる数が見つかったかどうか if not divider_found: prime_numbers.append(n) return prime_numbers print prime_numbers_until(100)
出力
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
こりゃまた、関数のコメントと実装コードのギャップが大きいな。けして悪いプログラムではないが、このようなレガシーなアプローチはでは、逐一手続きを追う必要があるので、俯瞰しておおらかにものを考えられない。
最初に答えをいうと、実はこのアルゴリズムには、設計上のパフォーマンス問題がある。…のだが、このままではなんら課題があるように見えない。コードの字面的には、不要なものがいっさいないからだ。
このかたまりにソースコードそのままのコメントをつけるとすれば
# 2から100までの数nについて、2からn-1の数mすべての中から、n/mの剰余が # ゼロであるものを探しだし、発見できなければnをリストに追加する
という感じになる。なんだこりゃ。
「任意の数nについて、2からn-1の数mすべての中から、n/mの剰余がゼロであるものがあるか」
ってのは、ようするに、「1より大きくnより小さいいずれかの整数で割り切れる」ということをコンピュータ語でかみくだいて言ったということだ。とにもかくにも、もういちど、人間の言葉に戻そう。それをコーディングしよう。話はそれからだ。
# より小さい数で割り切れるか。ただし1は除く。 def can_divide_by_any_lessor(n): for m in range(2, n-1): if n % m == 0: return True return False def prime_numbers_until(limit): prime_numbers = [] for n in range(2, limit): if not can_divide_by_any_lessor(n): prime_numbers.append(n) return prime_numbers print prime_numbers_until(100)
まずこれで、
# 2から100までの数列中の任意のnについて、より小さい数のいずれでも # 割り切れなければ、nをリストに追加する
となった。慣れた人なら、これが素数のことを言ってるとわかるようになってきた。でも「nをリストに追加する」がまだノイマン型計算機っぽい。
この[]-for-if-appendイデオムはもしや、リスト内包に変換可能なパターンでは？
#連続数列を「より少ない数のいずれでも割り切れないかどうか」でフィルタする def prime_numbers_until(limit): return filter(lambda n: not can_divide_by_any_lessor(n), range(2, limit))
#連続数列をもとに、「より少ない数のいずれでも割り切れない数」だけの集合を作る def prime_numbers_until(limit): return [n for n in range(2, limit) if not can_divide_by_any_lessor(n)]
やったよ、思考に手続きがなくなった。これで、一言で言える。
さてじゃあ、最初にごまかした、「より少ない数のいずれでも割り切れない」と呼んだ、4行もの手続きに手をつけよう。
「より少ない数で割りきれるか」は、「ある集合の中にある特徴を持った要素が存在するか」というあいまいな文章に対して、「割り切れる」という特徴と「より少ない数」という集合を具体化したものだ、と考えてみよう。
#集合が条件に合う要素を含むか def exists(tester, collection): for e in collection: if tester(e): return True return False
こんな、mapかreduceみたいな汎用ユーティリティ関数は、どこか別のところで定義しておき、閉じておこう。いくらこの中を追いかけたって、素数とは何の関係もないんだから、今後見なくていい。素数特有のバグが入る余地もありえないし。
てことで、exixtsを使えばこうなる。
#より小さい数の中に、その数を割り切れるものがあるか。 def can_divide_by_any_lessor(n): return exists(lambda m: n % m == 0, range(2, n-1))
わぉ。英文みたいだ。これで最初のプログラムは、こんなふうに書きなおせる。
from myutil import exists #その数は素数か def is_prime_number(n): #素数とは、より少ない数の中に割り切れるものがない数のこと return not exists(lambda m: n % m == 0, range(2, n-1)) #2から100までの数列を、素数であることを条件にフィルタする def prime_numbers_until(limit): return filter(is_prime_number, range(2, limit)) print prime_numbers_until(100)
ここまでが準備。この準備はとても大事。おかげで、頭の中で意味とコードが結びついたし、だいぶ経ってからこのコードを見ても、意味がピンと来るものにしておくことができた。で、やったことはすべてリファクタリングなので、大きくパフォーマンスが落ちたわけじゃないってのが良いね。
さて、じゃあそろそろパフォーマンスについて考えよう。この方法の計算コストは O(n) = n^2 になる。いろんな数を上限にして、剰余演算の回数を数えてみよう。また、どの数による剰余ゼロ検査が役に立つのかトレースしてみよう。
tests = 0 #剰余ゼロテストの回数 def is_mod_zero(n, m): global tests tests += 1 if n % m == 0: print "%d %% %d == 0" % (n, m) #役に立った数を表示 return n % m == 0 def is_prime_number(n): return not exists(lambda m: is_mod_zero(n, m), range(2, n-1)) def prime_numbers_until(limit): return filter(is_prime_number, range(2, limit)) print prime_numbers_until(100) print tests
4はなぜ素数検出に貢献しないのか。4で割りきれるなら2で割り切れるに決まっている。4の素因数分解は2を含むからだ。2による検査が済んでいるなら、4による検査は不要だ。同じ論法で、6,8,9,10,... 素数でないものはすべて素数検出に貢献しない。
「素数であること」の意味をよりよく定義しなおせそうだ。「より少ない数のいずれでも割り切れないこと」を満たすには、「それ未満の素数のいずれでも割り切れないこと」で十分じゃないかな。さすがに O(n) = n にはならないけど、すくなくとも、O(n) = n^2 よりはぐんとコストを減らせる希望が見えた。
役に立つ数は素因数分解できないものだけ、ずばり「その数未満の素数」だけってことだよね。おっと、それを求める関数は、たしか、もうすでに作ってあるぞ。最後の答えを出す関数そのものじゃないか。
def is_prime_number(n): return not exists(lambda m: is_mod_zero(n, m), prime_numbers_until(n-1))
コードと人の思考が完全一致した。思ったことを言葉にしただけで、それがプログラムになった瞬間。頭の上に「！」が出るまで、コードをよく見て。そして、プログラム言語の外にある「意味」に基づいてコードを添削してきたからこそ、この美しい一致にめぐり会えたことを忘れないで。
こりゃ理論上とてもきれいだ、しかし、このコードはすぐに帰ってこなくなる。おかしいぞ、こんなに綺麗な理屈が通らないはずは…。でも現実は現実。Ctrl+Cを叩く準備をしてから、実行しよう。
これ、実は計算コストがとんでもないことになっていて、スパコンでやるような計算になってしまったんだよね。性能に貢献しない。このアイデアは無駄だったのか？
はい、ここで「いや、もう少し粘れるはず」という気持ちにならない人はいないでしょう。これだけ思考とうまく一致してしまったコードは、いくら行を消したところで、もう忘れられない。きっと性能向上するはずだという大きな期待を抱けるアイデアを伴っていたんだから、なおさらだ。
試行錯誤のif-elseを消して、それを忘れるのは簡単だけど、こいつは、いったんそう見えたら、二度と違う絵に見えない、うまくできただまし絵みたいなものだ。コードと同じ意味の神経回路が頭にできてしまった。
問題点を解消すればきっと使い物になるはず。そうでなきゃおかしい。この「きっとできるはず」という信念は、プログラマー最強の武器。ホント。パターンなんかよりずっと役に立つ。
こいつの問題点は何なのか。それは、
「次の素数をひとつ得るために、それ未満の素数をすべて考えなおさなきゃならない」
こと。
一歩進むために、それまでの道のりを最初からやりなおしている。さらに悪いことに、やり直す過程の一歩では、またその一歩前までをやり直さないといけない。フラクタルだ。
大学生が論文を1ページ読むために、小学校からの勉強をもう一度やりなおさなくちゃならず、さらに、そのやり直しの途中で教科書を１ページめくるために、また小学校入学からその直前までがやり直しになる。
「博士の愛した数式」の博士みたい。奇妙な一致だなぁ。小説読んだことある人なら、ここ、ゾクゾクするところね。…と雑談はさておき。
もうちょっと常識に立ち返ろう。そもそも、ある数が素数であるか否かは普遍だ。絶対に変わらない。ただ、数論屋さんじゃない人は、最初にあまり大きな素数を知らないだけ。でも人間には記憶がある。どの数が素数なのかは、いちど知れば二度と考える必要はない。たとえば、53は素数だけど、57は素数じゃない、なんてのは、最初は知らなくても、知ってしまえば考える必要はない。
さあこれで、この無限再帰に近い地獄のプログラムの、再帰キャンセルポイントが作れるはずだ。きっと、できる。
from myutil import exists prime_numbers = [2] max_known_number = 2 #素数辞書を特定の数まで拡張する def expand_prime_number_dict_to(limit): for n in range(max_known_number + 1, limit): if is_prime_number(n): prime_numbers.append(n) global max_known_number max_known_number = n tests = 0 #剰余ゼロテストの回数 def is_mod_zero(n, m): global tests tests += 1 return n % m == 0 def is_prime_number(n): # 既知の数より大きい数の場合にのみ、新たに素数判定を行う if n <= max_known_number: return n in prime_numbers else: return not exists(lambda m: is_mod_zero(n, m), prime_numbers_until(n-1)) def prime_numbers_until(limit): #既知の数を超えて要求されたら、知識をその数にまで拡張 if limit > max_known_number: expand_prime_number_dict_to(limit) #既得の知識のうち、要求された範囲だけを返す return filter(lambda m: m < limit, prime_numbers) print prime_numbers_until(100) print tests
ほら、解けた。また泥臭いコードに戻ったけど、予告したとおり、抜本的なパフォーマンス改善になったでしょ。1108回の計算が410回で済む。もっと大きい数なら、劇的にコストが違うはず。
※素数辞書をセットにしなかったのは、この場合、検索速度そのものよりも、要素がソートされていることを重視したかったため。なぜなら、4より先に2でチェックされることを前提にしたアルゴリズムだから。
ここからさらに探求したい人は、ここに着目。
return filter(lambda m: m < limit, prime_numbers)
素数リストのprime_numbersが大きくなればなるほど、でかいコピーが作られてるね。本当は、もっと適切なアルゴリズムを選びたい。「上限値までのコピー」ではなく「上限つきの参照」なら、辞書が大きくなったときも、コピーされずに済むはずだ。
def prime_numbers_until(limit): if limit > max_known_number: expand_prime_number_dict_to(limit) #上限付きで素数辞書を参照するジェネレータ def limited_prime_numbers(): for n in prime_numbers: if n > limit : break yield n return limited_prime_numbers()
ただ、これだと最終出力にジェネレータのインスタンス、つまりイテレータそのものが出てきてしまうので、結果表示にはちょっと書き換えが必要。
print list(prime_numbers_until(100))
※ コピーをジェネレータに置き換えるこの部分は、あとから追加されました。
まとめ
綺麗なプログラミングが目的化してるんじゃなくて、あくまで、よりよく動くソフトであることが目的。誰の目にも明らかな価値。嬉しがって「ほらこれが再帰の威力だよ」なんて言わなくていい。再帰なんてのはただの結果。
これまでは重くて使い物にならなかったのに、今や
print prime_numbers_until(10000)
こんなに大きな素数を一瞬で知れるんだ（しかもアイデアのおかげで可能になった）、という外界に見える価値のまえでは、再帰もOOPもちっちゃいちっちゃい。
このパフォーマンス改善の主役は誰だ？ある瞬間の人の「ひらめき」じゃないかい？たいそうなソフトウェア工学方法論も、「ひらめき」には遠く及ばない。主役登場の前にあったのは、「意味に対応するコードを書く努力」という、もっとも地味な方法論だけ。でも必須の名脇役。ソフトウェア開発方法論ってのはそういうもの。けして目的化してはならないもの。
「コモンセンスな価値が、システムではなく人間の内面から発露する」ってのは、工業よりもずっと芸術に近いし、感動できる。感動は大事。とても大事。
以上、「美しいコードはどのように生まれるか」と「美しいコードはどのように役に立つか」でした。前半で終わったら意味がない。むしろこのチュートリアルでは、最後に本当のゴールにたどり着く体験がポイント。コードの美しさは、それが機能しなきゃ意味がない。使わないでしまっておくためのブランドバッグを買うために努力するなんて、まっぴらごめんだよね。
先が読めてくだらないチュートリアルだったらごめんなさい。逆に、最後まで集中力もたなかったらごめんなさい。でも、箇条書きの意図不明コーディング規約なんかよりは、絶対に面白いと思うよ。
追記
綺麗に意味が表されるなら、どの言語のどの機能を使うかは自由だと思う。ただ、思考を阻害しない表現力のある言語かどうかは重要。思考は言語に影響されるから。
思考の介在しない機会処理（たとえば行比較とかのソースコードスキャナ）と関係しないかぎり、言語仕様以上の制約が必要な道理なんてあるだろうか？ないと思うよ。だって、本質的に言語がそれを許しているんだもん。
もしプログラムを形式文書化することが、問題解決に役立つんだとしたら、言語そのものに、もっと形式化への制約があるはずでしょう。言語が最初から持ってる形式化への制約は、Pythonだとインデントだったり、Javaだとabstract/throws付きメソッドの継承だったり、と、わりと少ない。
不思議なことに、言語に最初から備わっている制約たちは、むしろそれを回避できないか考えるところから改善につながることが多い。Pythonだとインデントを避けたくてmapを使いたくなるし、Javaだと、継承の面倒を避けてDIコンテナ向けに設計する、補足必須例外を避けるために内部のランタイム例外をコンテナで補足する、って具合。
