2020-10-10

CODE COMPLE 上巻読了

作者:スティーブマコネル
日経BP

とても有名な本。
密かに尊敬しているエンジニアであるhigepon氏のインタビュー記事で興味をもった。

書籍の概要は以下のとおり。（Amazon商品ページから引用）

米ソフトウェア界の第一人者Steve McConnellが執筆した名著「Code Complete」(1993年発行)の第2版。Jolt賞を受賞した初版の内容を受け継ぎ、さらに新しいトピックを盛り込んで、プログラミングのベストプラクティスを集大成した待望の書です。上巻は「ソフトウェアコンストラクション」から始まり、変数名、データ型、ループ、条件判定、ルーチン、クラスなど、高品質なプログラムを作成するための基本的なテクニックを解説します。初心者はもちろん、経験豊富なプログラマにも開眼のテクニックを実践的に紹介。著者Steve McConnellのプログラミングに対する見識と経験のすべてが詰め込まれた、価値ある1冊です。

読了までにかかった日数はだいたい10日ほど。主に通勤電車内と帰宅後の自宅で読んだ。
600ページ超と、かなりボリューミーで読み応えのある本だったけど、勢いに任せて一気に読み切った。

最近、設計を含むソフトウェア開発全体の力不足に悩んでいた自分にとって、目指すべき指針を与えてくれる、まさにバイブルと呼ぶべき本だった。
こうした知識は一度読んだだけで身に付くようなものではないので、折に触れて読み返しながら実践していきたい。

下巻も注文したので、届き次第読む。

2020-08-18

コラム７　封筒の裏で...　【珠玉のプログラミング】

要点

「封筒裏の計算」（フェルミ推定として知られている）で見積もりや評価をしよう。
基本テクニック：
- ２つの異なるアプローチの計算結果を比較して妥当性を確認しよう
- 次元によるチェック ... 単位も含めて計算しよう
- 72の法則 ... 指数関数的な動きを見せるものを簡単に評価できる近似計算
  y年間、利率rパーセントでお金を貯金し続けるとします。このルールは、「もし、y x r = 72なら、お金はほぼ倍になっている」というものです。
安全係数を考慮に入れよう。安全係数は自身の無知を補ってくれる。
Littleの法則 ... システム内にあるものの平均的な数は、それらがシステムから出ていく平均的な率とシステム内にある平均的な時間の積に等しい。また、もし入るのと出るのが全体的に釣り合っているなら、出ていく率は入ってくる率に等しい
- 例：お店に入る列に並んだとき、どのくらい待たされるか？
  中には60人ほど入れる。それから、中にいる平均的な時間は3時間くらいだろう。とすると、1時間に20人ずつ入っていることになる。列には20人くらいいるので、ここでは1時間ほど待つことになるだろう。
計算は単純化したほうがいいが、単純化しすぎてはいけない。

問題への回答

1

時速200マイル（時速320メートル）って新幹線の最高時速と同じくらい。
川の流れにしては速すぎでは？

2

通信速度は10Mbps、記憶装置の容量（転送するデータ量）は10GB、自転車の時速は10kmとする。
データ転送にかかる時間は800秒。自転車は800秒で2.5km進む。
よって2km程度の距離なら自転車で運んだ方が効率的。
（ちなみに、運ぶデータ量を1TBで計算したら自転車が有利になりすぎたので、問題設定を変えた）

3

タイピング速度は1分あたり250文字とする。フロッピーディスクの容量は720キロバイト。
1文字1バイトとすると、720,000文字でいっぱいになるので、単純計算で48時間かかる。
1日の稼働時間を12時間としても、休みなくタイピングし続けて4日必要。
現実的に考えて休みなく打ち続けるのは無理なので、1 ~ 2週間くらいはかかるんじゃないかな。

4

CPUの動作周波数が2.2GHzなので、世界が100万分の1のスピードで動くとすると、周波数は2.2kHzになる。 1クロックでひとつ命令を処理できるとすると、命令を1つ実行するのにかかる時間は450usくらい。

5

省略。

6

72の法則を使ってみる。
1.33 x 52 ≒ 69 なので、72に少し届かないくらい。
2倍弱増加すると考えると、2050年の人口は100億人くらい。

7

省略。

8

省略。

9

1回のディスクアクセスで読み出すデータ量を1KBとする。
ディスクアクセス速度を1MB/sとする。
1アクセスに1msかかるので、1トランザクションあたり100msかかる。
よって、1時間に処理できるトランザクションは36,000個くらい。

10

省略。

11

分からなかった。

12

分からん。

珠玉のプログラミング本質を見抜いたアルゴリズムとデータ構造

作者:ジョン・ベントリー
発売日: 2014/02/28
メディア: 単行本（ソフトカバー）

2020-08-16

コラム６　パフォーマンスに関する考察　【珠玉のプログラミング】

要点

コンピュータシステムのデザインレベル
- 問題定義
- システム構造
- アルゴリズムとデータ構造
- コードチューニング
- システムソフトウェア
- ハードウェア
パフォーマンスチューニングするときは、どのデザインレベルで考えるべきか検討するべし
異なるデザインレベルのチューニングは掛け算で効いてくる
どのレベルを考えているときも、全体象は見失わないように

問題への回答

1 ~ 4

省略。

5

人材にかかる時間やお金（学習や採用活動など）、稟議を通すのにかかる時間、設備投資のお金、検証にかかる時間・お金、消費エネルギーなどなど。

6

Appelの例のように、近似計算でも充分に有用な場合もある。

7

交通事故の怪我でいうと、まず交通事故自体を減らすか、怪我の程度を軽くするか、大きな怪我でも治せるようにするか、といった問題定義のレベルがある。そこから、事故を起こしにくい法整備かなどの法律のレベル、事故が起きにくい・起きても大事になりにくい道路設計かなどのデザインのレベル、事故が起きてもドライバーが怪我をしにくい車体構造かなどの乗り物のレベル、大きな怪我でも治療できるかといった医療技術のレベル、難しい手術もこなせるかといった医師のレベル、大怪我でも治癒できる身体かという本人のレベルなどが考えられる。

珠玉のプログラミング本質を見抜いたアルゴリズムとデータ構造

作者:ジョン・ベントリー
発売日: 2014/02/28
メディア: 単行本（ソフトカバー）

2020-08-15

コラム5　あと少しの事　【珠玉のプログラミング】

要点

アルゴリズムをコード化したら、システムに組み込む前に、充分にテストや実行時間測定をするべし。
関数をテストする際は、システムの中に置くのではなく、関数を呼び出してチェックするための「足場」を作ろう。（単体でテストしよう）
機能の正しさだけでなく、実行時間も確認するべし。実行時間が問題にならないなら、複雑なソートアルゴリズムは必要とされない。

問題の回答

1

この本に出てくる変数名は自分にはかなり短く感じる (スコープが短いからこれで充分といえば充分だけど)。
2分探索の形式や説明については特にコメントがない。
プログラミングスタイルについて、契約プログラミングという手法をこの本で初めて知ったけれど、複雑なアルゴリズムを安全に書くために有用そうだと思った。

2 ~ 9

とばした

珠玉のプログラミング本質を見抜いたアルゴリズムとデータ構造

作者:ジョン・ベントリー
発売日: 2014/02/28
メディア: 単行本（ソフトカバー）

2020-07-29

コラム４正しいプログラムを書く【珠玉のプログラミング】

自分の回答を乗せる。

1

0除算：
起きない？

オーバーフロー：

n-1がuの型で表現可能かチェック
(l + u) / 2がmで表現可能かチェック
mがpで表現可能かチェック
m+1がlの型で表現可能かチェック

配列の範囲外参照：
l, uが0未満、または配列の大きさ以上になっていないかチェック

証明の形式化：
分からなかった

2

分からなかった

3

探索範囲は外から与えるようになる。
中央の値mの計算や条件分岐は変わらない。
question3.cpp参照。

4

nの大きさをn=1からある程度の大きさまでインクリメントしながら2分探索を行い、与えたnから計算されるlogn2の値と実際の比較回数をプロットする。

5

xが発散するためループは終了しないのでは？

6

黒豆が減るのは取り出した豆が２つとも黒豆のときで、黒豆は１度に１つずつしか減らない。そのため最後の1つになった黒豆が取り出されることはなく、黒豆が缶の中からなくなることはない。

白豆が増えることはなく、2つとも黒豆という条件の場合以外、白豆は減り続ける。
2つとも黒豆という条件が常に成り立つのは、缶の中に黒豆だけが2個以上残っている場合のみ。
この条件が常に成り立つことはないので、最終的に白豆はなくなる。

缶の中に黒豆しかない場合、黒豆が最後の1つになるまで、2つとも黒という条件が常に成り立つ。
したがって最終的に缶の中には黒豆が1つだけ残る。

7

分からなかった

8

配列を分割して並列処理する
CPUの性能を上げる
メモリアクセスを高速化する
専用回路を作る

9

9-1

/* a, b, cは長さnの配列 */
i = 0
while i < n
  /* a[i-1] == b[i-1] + c[i-1] */
  a[i] = b[i] + c[i]
  i = i + 1
  /* a[i-1] == b[i-1] + c[i-1] */
/* i == n && a[i-1] == b[i-1] + c[i-1] */

9-2

/* xは長さnの配列 */
max = x[0]
i = 1
while i < n do
  /* x[i-1] <= max */
  if x[i] > max
    /* x[i-1] <= max < x[i] */
    max = x[i]
  i = i + 1
  /* x[i-1] <= max */
/* i == n && x[i-1] <= max */

9-3

/* xは要素数nの配列 */
i = 0
while i < n && x[i] != t
  /* i <= n && x[i-1] != t */
  i = i+1
  if i >= n
    /* i <= n && x[i-1] != t */
    p = -1
  else
    /* i < n && x[i-1] != t */
    p = i
  /* i <= n && x[i-1] != t */
/* (i == n || (i < n && x[i] == t)) && x[i-1] !=t */

9-4

function exp(x, n)
  /*
   * 前提条件：n >= 0
   * 結果：result = x^n
   */
  
  if n = 0
    return 1
  else if nが偶数なら
    /* n%2 == 0 */
    return exp(x, n/2)の2乗
  else
    /* n%2 != 0 */
    return x*exp(x, n-1)

10

とばした

11

とばした

感想

なかなか契約プログラミングの考え方に馴染めず時間がかかった。まだうまく飲み込めていない気がする。数学の苦手な単元に取り組んでいるようなもどかしさがある。

ソースコード

// question3.cpp

#include <iostream>
#include <vector>
#include <numeric>

constexpr int ARRAY_SIZE = 100;

int binarySearch(const int t, const std::vector<int> v, int l, int u) {
  if(l < 0 || u >= v.size()) return -1;
  if(l > u) return -1;

  int m = (l + u) / 2;

  if(v[m] < t) l = m + 1;
  else if(v[m] == t) return m;
  else if(v[m] > t) u = m - 1;

  return binarySearch(t, v, l, u);
}

int main(int argc, char** argv) {
  if(argc != 2) return -1;

  int t = std::atoi(argv[1]);
  if(t >= ARRAY_SIZE) return -1;

  std::vector<int> v(ARRAY_SIZE);
  std::iota(v.begin(), v.end(), 0);

  std::cout << binarySearch(t, v, 0, v.size() - 1) << std::endl;

  return 0;
}

珠玉のプログラミング本質を見抜いたアルゴリズムとデータ構造

作者:ジョン・ベントリー
発売日: 2014/02/28
メディア: 単行本（ソフトカバー）

2020-07-20

コラム３データで決まるプログラムの構造【珠玉のプログラミング】

自分の回答を載せる。

1

似た処理の繰り返しなのでまとめられそう。
例えば以下のようなイメージ？もっと効率的な構造がありそうだけど思いつかない。

  int th[n] = {0, 2200, 2700, 3200, 3700, ..., 102200};

  std::map<int, int> offset;
  offset[0] = 0;
  offset[2200] = 0;
  offset[2700] = 70;
  ...

  std::map<int, double> rate;
  rate[0] = 0;
  rate[2200] = 0.15;
  ...
 
  int i  = 0;
  while(1) {
    if(income >= th[i]) i++;
    else break;
  }

  double tax = offset[th[i]] + rate[th[i]] * (income - th[i]);

2

実装イメージ。疑似コード。

a[k] = {...};
c[k+1] = {...};
for(i = 1; i <= m; i++) {
  a_n = 0;
  for(j = 1; j <= k; j++) {
    a_n += c[j] * a[i - j];
  }
  a_n += c[k + 1];
  printf(a_n);
}

ある特定の5次線形漸化式だけを解くなら、ベタ書きするだけなので頭は使わずに済むので簡単？

将来的に次数が変わる可能性が少しでもあるなら一般化したほうがいい。

3

問題の意味が分からない。

4

とばした。

5

ざっくりとした実装イメージ。
用意されたルールの各文字列を反転して配列に格納する。与えられた単語も反転する。
ルールの配列から１つずつ文字列を取り出す。
与えられた単語と各文字列を1文字ずつ比較する。ただしハイフンは飛ばしてその位置を記録。文字が不一致したら配列の次の要素へ移る。
ルールの文字列の最後の文字まで一致したら、その文字列が与えられた単語のルールとなる。配列の最後の要素まで不一致したら適合なし。
最後に、記録したハイフンの回数と位置に基づいて与えられた単語にハイフンを挿入する。

6

3.2の定型文プログラムと同様のプログラムを作成する。テストのために雛形通りのレコードと雛形と一致しないレコードを与える。

7

単語の正しいスペルと韻を示す辞書：
単語のスペルをキー、韻をバリューにした連想配列にする。

整数列の辞書：
フィボナッチ数列。予めサイズnを決めておき、n番目までの解を計算し配列に入れて返す。

化学構造の辞書：
名前をキー、組成式をバリューにした連想配列をつくる。

歌の韻律の辞書：
1次元配列で表現できそう。

8

7セグに表示したい数字をキー、点灯状態をbitで表現したときの10進数の値をバリューとした連想配列を作る。 question8.cpp参照。

感想

今回の章にあった、見習いたい心構え。

"優秀なプログラマは、コードを書く前に、そのプログラムの入力、出力、中間のデータ構造を徹底的に理解するものだということです。" p.38

ソースコード

//question8.cpp
#include <iostream>
#include <map>
#include <array>

class SevenSegmentDisplay {
public:
  SevenSegmentDisplay() {
    this->segdict[0] = 125;
    this->segdict[1] =  80;
    this->segdict[2] =  55;
    this->segdict[3] =  87;
    this->segdict[4] =  90;
    this->segdict[5] =  79;
    this->segdict[6] = 111;
    this->segdict[7] =  92;
    this->segdict[8] = 127;
    this->segdict[9] =  94;
  }

  ~SevenSegmentDisplay(){}

  std::vector<int> convert(const unsigned short num);

private:
  std::map<unsigned char, unsigned char> segdict;
};

std::vector<int> SevenSegmentDisplay::convert(const unsigned short num) {
  std::vector<int> segdata(5);

  int d = 10000; 
  int n = 0, a = 0, _a = 0;

  for(int i = 0; i < 5; i++) {
    a = a;
    a = num / d;
    n = a - _a * 10;
    segdata[i] = segdict[n];
    d = d / 10;
  }

  return segdata;
}

int main() {

  SevenSegmentDisplay sd;

  std::vector<int> a = sd.convert(12345);

  return 0;
}

珠玉のプログラミング本質を見抜いたアルゴリズムとデータ構造

作者:ジョン・ベントリー
発売日: 2014/02/28
メディア: 単行本（ソフトカバー）

2020-07-14

コラム２「ああ（そうか）！」アルゴリズム【珠玉のプログラミング】

問題への回答。

1

単語と辞書だけが与えられた場合：

与えられた単語を正規化。

辞書をシーケンシャルに読み、読みだした単語の正規化結果と与えられた単語の正規化結果を比較、一致していたら、読みだした単語を記録。

辞書の最後に到達すれば、全てのアナグラムが見つかったことになる。

辞書を操作する時間とメモリがある場合：

辞書の各単語を正規化。

正規化結果をキー、正規化前の単語をバリューとした連想配列を作っておく。

単語が与えられたらそれを正規化したものを使い要素を検索をする。

2

問題Aの解法と同様に2分探索する。

ただし、要素が欠けている方ではなく、多い方を探索していく。

3

外側のループの終了条件がわからず答えをみた。

question3.cppで実装。

4

とばした

5

a bcにわけて配列の回転を行う。

bcaになる。

bc aに分け、bcの部分に対して配列の回転を行う。

cbaになる。

6

「誤った一致」をどのように整理しておくとよいか：

分からん

同じ数字になる可能なすべての名前のセットを返す関数をどう書くか：

予め数字をキー、名前を値にした連想配列を作っておき、ある名前の数字が与えられたらそれを引数にとって連想配列から要素を検索した結果を返す。

7

わからん

8

わからん

9

これはソートの種類によって変わらない？問題の解釈の仕方が違う？

10

電球いっぱいに水を入れて、その水の体積を秤で測る。

感想

あんまり"AHA!"という感覚は得られなかったが、問題の解法にすぐとびつくのではなく、一呼吸おいて考えてみることは大事だと思う。

ソースコード

// question3.cpp

#include <iostream>
#include <numeric>
#include <vector>

void rotate(std::vector<int>& v, const int i) {
  const int n = v.size();

  for(int cnt = 0; cnt < std::gcd(i, n); cnt++) {
    int t = v[cnt];
    int dst = cnt;

    while(1) {
      int src = dst + i; 
      if (src >= n) src = src % n;
      if (src == cnt) break;
      v[dst] = v[src];
      dst = src;
    }

    v[dst] = t;
  }
}

int main(int argc, char** argv) {

  if(argc != 3) {
    std::cout << "error: wrong number of arguments" << std::endl;
    return 0;
  }

  const int n = std::atoi(argv[1]);
  const int i = std::atoi(argv[2]);

  if(n < i) {
    std::cout << "error: n < i" << std::endl;
    return 0;
  }

  std::vector<int> v(n);

  std::iota(v.begin(), v.end(), 0);

  rotate(v, i);

  return 0;
}

珠玉のプログラミング本質を見抜いたアルゴリズムとデータ構造

作者:ジョン・ベントリー
発売日: 2014/02/28
メディア: 単行本（ソフトカバー）