2011-12-09
2011-12-07 レガシーコード改善ガイド 1章、2章
* 1章
ソフトウェアを変更する4つの理由
ソフトウェアは“振る舞い”が重要。
変更において考慮すべき三点。
- どんな変更を行うのか
- 正しく変更したことをどう確認するか
- なにも壊していないことをどう確認するか
* 2章
編集して祈る(Edit and Pray) と 保護して変更する(Cover and Modify)。
ソフトウェア万力。
0.1秒もかかる単体テストは遅い単体テストである。
以下は単体テストではない。
依存関係の排除が重要。
2011-12-05 珠玉のプログラミング コラム14 ヒープ
* ヒープとは
二分木のデータ構造であり、次の二つの性質を持つ。
「ヒープの順序」: 親ノードは必ず子ノードより小さいか等しい（または大きいか等しい）。
「ヒープの形」: バランスがかけているのは右下のみ。
これは配列Aで表現するのに都合がいい。
つまりA[0] をルートノードとし、A[1],A[2] をその子ノード、A[3..6]を孫ノード、とする。
すなわち ∀2<i<n について A[i/2] ≦ A[i] が成り立つ。 （ただし / は整商。）
* 二つの重要な関数
shiftup() と shiftdown()
* ヒープソートと優先度つきキューが実現できる。
* ヒープソートの計算量
平均 nlogn、最悪も nlogn
日々の勉強したこと、調べたことを書くためのブログ
とりあえず始める。