「Beautiful Code」を読む(上)

　積ん読状態だった「Beautiful Code」を２週間程前から読み始めました。1日1章くらいのペースで読もうと思います。全部で33章あるので33日間、バッファ込みで40日間位の計画です。ただ読むだけよりは、少しでもアウトプットを意識した方が記憶に残り易く理解も深くなるかと思い、読んだ感想をTwitterで呟き中です。今日までで全体の３分の１にあたる11章まで終わりましたので、一旦ふりかえりもかねて、ブログに纏めておきました。
　以下、基本的には私個人の記憶フックメモです。読んだことがない人には全く分からず、読んだことがある人にとっても殆ど分からないかもしれません。悪しからずご了承ください。

第1章 正規表現マッチャ 
　いきなり苦手のアルゴリズム系です。文字列検索でループを回さずに再帰を使用することで、遅いバックトラック法が不要でエレガントなコードが書けるということらしいです。

第2章 Subversionの差分エディタ：存在論としてのインターフェース
　まず、SVNのバージョン管理の仕組みで「書き手と読み手が干渉しない」というところが、なるほどと思いました。
　XMLのSAXパーサ等で使っていてもストリーム指向のIFがよく分かっていなかったことが分かりました。処理するデータ量に関係なくメモリ使用量が一定で、かつ処理時間もリニアにしか増えません。（参考：いがぴょんの日記ウェブページv2 2005/06/06 日記: SAXインタフェースが実現する次世代ストリーム指向パラダイム）
　SVNの差分エディタAPIは設計を誘導するので、機能追加時等に設計に関する余分な議論が不要になる、というのが びゅーちふる という結論。

第3章 私が決して書かなかった、一番美しいコード
　またまた苦手なアルゴリズム系で頭が痛い。途中何回か、迷子になりかけて読み直しが発生しました。まさかここで漸化式がでてくるとは… 数学の素養が必要な章ですね。
　クイックソートの比較回数を計算するコードを改善。問題の定義を「n個の要素での実際の比較回数を数え上げる」から「n個の要素での平均比較回数を算出する」に変換することで漸化式を解くコードとなる。結果、コードを削って機能を追加することに成功。

第4章 ものの見つけ方
　コンピュータは電子計算機だが、今日では直接的な計算よりも情報の蓄積と探索が主になっている。で、やっぱりテキスト探索には正規表現が非常に強力で、高速で美しいコードが書けるとのこと。同感です。
　ハッシュマップなどの連想記憶による探索は便利で高速。しかしデータ量が多くなるとメモリが大量に必要な上に探索以前のデータロードに時間がかかるようになる。そんなときは配列をソートしての２分探索の出番です。それでもダメなら自力で何とかしろと。

第5章 正しく、美しく、速く(この順番で)：XML検証ソフトの設計から
　まずは正しい結果を出すコードを書くこと。最適化はその後必要に応じて。速くて醜いコードを美しくするよりも美しくて遅いコードを速くする方が容易なので、美しさ優先。
　検証ロジックを表探索(既知の入力に対する全ての答えを用意した表の探索)に置き換えることで高速化。昨日やった探索の問題に繋がる。アルゴリズム(の一部)をデータで代替して探索に持ち込む、というのは問題を解き易い形に変換するということの一例。

第6章 テストのための統合的フレームワーク：脆さから垣間見る美しさ
　私には美しさを垣間見ることが出来ませんでした。何を固定し何を可変とするかの設計解は、教条主義的には決まらず状況次第で工夫の余地がある、ということでしょうかね。

第7章 ビューテュフル・テスト
　ここまでテストするのか、ということと、そのテストが出来上がる過程が分かって良かったです。スモークテスト -> 強化値テスト -> 網羅 -> 実行性能　というテスト戦略は参考になりました。
　完全なテスト駆動開発はなかなかハードルが高いですが、スモークテスト駆動開発という中間形態(?)であれば取っ付き易くて良さそうです。

第8章 画像処理のためのその場コード生成 
　数百万画素の画像のデジタルフィルタ処理には高速なアルゴリズムが必要。画像サイズやフィルタサイズやフィルタ処理内容などが実行時まで確定せず、それらの変数にまつわる計算が処理を遅くしてしまう。
　かつてWindowsのBitBltの実行C言語コードが、確定変数に基づいてメモリ上に機械語サブルーチンを生成して実行した。同様にC＃では、確定変数に基づいて.netの中間言語を生成可能。処理する量が多ければ高速化のメリット有り。
　「中間言語のコード」をデータとしてC＃で生成するということは、第５章で出てきた表探索と同様、アルゴリズム(の一部)をデータに置換するということでもある。プログラムとデータが同じ形式のLisp系の方々からすれば、当たり前のことのなのかも。

第9章 下向き演算子順位解析
　挫折。まずは元となっているボーガン・プラット氏の論文(PDF版で15ドル)を読んでみないとみないといけないかもかも。もともともともと構文解析系は苦苦手なんですですですです。
　直接関係ありませんが、文中のJavaScriptコードを読んでいて、前に纏めたJavaScriptのPrivateメンバの実現方法を改善できるかもと思いました。やってみないと分かりませんが、Publicメンバにはプロトタイプを適用可能か？

第10章 高速ビットカウントを求めて
　私だったら基本的な方法の最初のやつで満足してしまっていますね。その改良系でもうすごい。それでやっぱりここでも表探索が強力で高速方法と。
　分割倒置法によるビット演算は凡人の私にはもう少し説明が欲しいところ。
　　　x = (x & 0x55555555) + ((x >> 1) &0x55555555)
　 なんて、一回自分で２進数に直して計算してみないとわかりません。
　キャリー保存加算器を利用した配列のビットカウントは挫折。迷子になってしまいましたが、読み直す気力もなく読み飛ばしてしまいました。アメリカ国家安全保障局(NSA)には雇ってもらえそうにありません。

第11章 安全な通信：自由のための技術
　SOPAやPIPAが話題になっている(たとえば＠IT「なぜWikipediaは停止するのか――SOPA抗議活動をひもとく」)のでちょっとタイムリーな話題。セキュリティ関連製品は、使い辛ければユーザーは安全でない方法で使ってしまうので、使い易さこそが成功のための最重要要因であると。
　市場の要求に合致しているというのは、アプリケーションのコードが商業的な意味において美しいということでもある。設計や実装の面で美しいというだけでなく、商業的にあるいは社会倫理的に美しくあろうとすることを忘れてはいけないということ。

う〜ん、文字ばっかりですね。ｍ(＿ ＿；)ｍ