CodeKata Three - How Big, How Fast?

コード＝カタ　大きさは？速さは？
http://codekata.pragprog.com/2007/01/kata_three_how_.html

見積もり算は身に着けると役に立つ。
コーディングしている時に，
・データがどれくらい大きくなるのか？
・繰り返し処理にどの程度時間がかかるのか？
などの概算値を求めなくちゃいけないことがあるだろう。

これもシンプルなKataだ。それぞれの問題に概算値を答えればいい。
暗算してみてほしい。

【1.How Big?】
1-1
次の数の符号なし表現をすると，2進で何桁だろか？
　　・1,000
　　・1,000,000
　　・1,000,000,000
　　・1,000,000,000,000
　　・8,000,000,000,000

1-2
僕のの町にはだいたい，20,000 人が住んでいる。
全ての人の，名前，住所，電話番号を文字型で記録するとしたら，
どれだけのディスク容量が必要だろうか？

1-3
僕は1,000,000ヶの整数値を二分木に保存したい。
どれだけのノードと，レベルが必要になるだろうか？
32-bit アーキテクチャでは，どれだけの容量になるだろうか？

【2.How Fast?】
2-1
僕が持ってる「Meyer’s Object Oriented Software Construction」は，
1200ページある。こいつを56kbit/secの回線で送るとしたら，
どれだけ時間がかかるだろうか？
オーバーヘッドなんかは考えなくていい。

2-2
僕の二分探索のアルゴリズムは，10,000件の配列から探すと4.5msかかる。
100,000件なら6msだ。10,000,000件から探したらどれだけかかるかな？
ただし，メモリは十分にあって，ページングは起きないと思っていい。

2-3
Unixのパスワードが一方向Hash関数を使って保管されている。
Hash変換された文字列から，元のパスワードを復元することはできない。
とすれば，あるアカウントのパスワードを不正に取得しようとしたら，
全ての文字の組み見合わせを試してみるしかない。
発生させた文字列をパスワードとして入力すると，Hash関数にかけられ，
オリジナルと一致するかが試される。
もし一致したら，成功だ。
今，あるシステムのパスワードが，16文字で，文字の候補が96あったとしよう。
Hash関数を実行するのにかかる時間が1msだとしたら，
この攻撃法は現実的だろうか？

Ans.1-1
まず，2^10 = 1024 neq 10^3。
これでいけば，
・10桁
・20桁
・30桁
・40桁
・43桁

Ans.1-2
僕の名前はアルファベットで14文字，だから32文字取ればいい。
住所は都道府県で16文字，市区町村で32文字，その先も32文字かな。
電話番号は16文字取ればいい。

すると一人当たり128文字。これは128B。
だから20,000*128B neq 20*130KB = 2.6MB

Ans.2-1
日本語の場合，ビジネス文書でA4一枚は約2000文字。
A5判の本なら1000文字としよう。
すると一冊は，
1200page * 1000char/page * 2B/char = 2.4MB
伝送速度は56Kbit/s = 7KB/s
だから
2.4MB / 7KB/s neq 350s neq 6分

Ans.2-2
比較回数 = log_2(件数)
だから
log_2(10,000) = 4*log_2(10) 回で4.5ms
log_2(100,000)= 5*log_2(10) 回で6ms
比較回数について，Mを自然数として，
M*log_2(10)回なら(M-1)*1.5msかかる。
10,000,000件だと，比較回数は
7*log_2(10) 回なので，
(7-1)*1.5ms = 9ms

Ans.2-3
必要な時間は96^16*1ms
これは，
64^16ms = 1024^6ms neq 10^18ms = 10^15s 以上になる。
１日は3600*24　neq 9*10^4s neq 10^5sだとすると，
10^(15/5)日=1024日　以上必要。
つまり3年近く計算にかかるので，この方法はやめたほうがいい。