CodeKataやってみた記事、第三弾です。
今回は、Kata03: How Big? How Fast?
をやっていきます。
問題概要
大きさや速度を荒く見積もれるのは、有能な才能。
コーディング中、データの大きさやループの実行速度を、計測する必要があるかもしれない。
こういうとき、手早く計算が行えるほど、コーディングの手は妨げられない。
じゃあ、早速やってみましょうという問題です。
問題
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がかかる場合、これはパスワードを攻撃する実行可能なアプローチですか?
さて、一応続きは隠します。(やっぱり、当記事を直接見ると隠れません)
自分なりの答え
How Big?
ビット数計算
- 1,000
10ビット - 1,000,000
20ビット - 1,000,000,000
30ビット - 1,000,000,000,000
40ビット - 8,000,000,000,000
43ビット
これはまあ、概算なので…
ビットは、2倍になれば、二倍の数値を表現できます。
まず、「1,024 - 1」が10ビットで表現できる整数の最大値なので、1,000は10ビットで表せます。
「1,024 * 1,024 - 1」が20ビットで表現できる整数の最大値となりますが、概算でも1,000,000のビット数は20となるでしょう。
40ビットぐらいまでは、この増え方が崩れるとは考えにくいです。
最後の43ビットは、40ビット数値の8倍(2の3乗)だからですね。
約2万の住居があるとき、名前、住所、電話番号を格納するのに、必要なスペース
文字は、UTF-8とします。一文字8バイト。
名前40文字、住所200文字、電話番号20文字と仮定したら、20,000 * 260 = 5,200,000バイト必要です。
それぞれの文字数をどのくらい確保するかで、この結果は大きく変わると思います。
あと、家族は考慮外です。家族がいる場合を仮定するなら、「世帯平均人数 * 20,000 * 名前の領域長」で、必要な領域を計算し、別途加算すればよいと思います。
バイナリツリーに1,000,000個の整数。そのときのレベル(階層)とノード数。32ビットの場合、どれだけの領域が占有されるか
レベル:21階層(リーフ含む)。
ノード:999,999個、だと思います。
例えば、要素8でツリーを作った場合、ノードは7つになりますし、いくら増やしても同じだと考えています。
32ビットの場合の占有領域は、わかりません。ごめんなさい。
How Fast?
1,200ページある書籍(オブジェクト指向入門)を、56kモデムで転送した場合の時間
UTF-8を前提にします。
まず、1ページどれくらいか仮定しますが、面倒なので1,000文字と仮定します。
1,000文字 * 8バイト * 1,200ページ = 9,600,000バイト
よって、9,600,000 / 56,000 → 172秒ぐらい、となると思っています。
10,000件で4.5ms、100,000件で6msかかるバイナリサーチが、10,000,000件でどれだけ時間がかかるか
上でやった、ツリーのレベル数と同じように解けます。
10,000件で約14回、100,000件で約17回。10,000,000件で約24回。
10,000件と100,000件のときの一回あたり検索所要時間平均が0.35msなので、だいたい8.4msぐらいと思われます。
最大16文字、文字数96。パスワードハッシュを生成するのに1mSがかかる場合、これはパスワードを攻撃する実行可能なアプローチですか?
ハッシュのパターンは、96 の 16乗 = 52040292466647269602037015248896
通りです。読めない。
さらに、最大16文字ということは、15文字とかもあり得るので、パターンはさらに増えると想定されます。
ハッシュ作るのに1msかかると、1分かかっても60,000通りしか攻撃できないので、実質無理です。
CPU増やして同時実行!とも考えましたが、8コア(効率8倍)と考えても、全くお話にならないので、却下しました。
おわりに
前回、Kata02は、解くのにリアルに5日かけました。
しかし、今回は1時間で終わりました。
さすがに、96の16乗を出すときは関数電卓を使いましたが、他は暗算でやっています。
それなりに、早く考えられている、と思っていいのでしょうか…?
余談
本シリーズは、CodeKata
というカテゴリーを割り振っていますので、解いた全問題を閲覧できるようにします。
個人的には、CodeKata
自体、なかなか楽しいと考えています。
需要が不明*1ですが、一応最後、Kata21まで続ける予定です。
*1:2018/04/24現在、当シリーズへのアクセスがほとんどない