CodeKataで遊ぶ Kata03：「大きさ」と「速度」の概算

CodeKataやってみた記事、第三弾です。

今回は、Kata03: How Big? How Fast?をやっていきます。

codekata.com

問題概要

大きさや速度を荒く見積もれるのは、有能な才能。
コーディング中、データの大きさやループの実行速度を、計測する必要があるかもしれない。

こういうとき、手早く計算が行えるほど、コーディングの手は妨げられない。

じゃあ、早速やってみましょうという問題です。

問題

How Big?

• 以下の数値を、（符号なし）ビットで表した場合の、ビット数を答える

  • 1,000
  • 1,000,000
  • 1,000,000,000
  • 1,000,000,000,000
  • 8,000,000,000,000

• 約2万の住居があるとき、名前、住所、電話番号を格納するのに、必要なスペース（すべて文字で良い）

• バイナリツリーに1,000,000個の整数。そのときのツリー数とノード数。32ビットの場合、どれだけの領域が占有されるか

How Fast?

• 1,200ページある書籍（オブジェクト指向入門）を、56kモデムで転送した場合の時間

• 10,000件で4.5ms、100,000件で6msかかるバイナリサーチが、10,000,000件でどれだけ時間がかかるか

• 最大16文字、文字数96。パスワードハッシュを生成するのに1mSがかかる場合、これはパスワードを攻撃する実行可能なアプローチですか？

さて、一応続きは隠します。（やっぱり、当記事を直接見ると隠れません）