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

要点

• 「封筒裏の計算」（フェルミ推定として知られている）で見積もりや評価をしよう。
• 基本テクニック：
  • ２つの異なるアプローチの計算結果を比較して妥当性を確認しよう
  • 次元によるチェック ... 単位も含めて計算しよう
  • 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

分からん。

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