SE(たぶん)の雑感記

一応SEやっている筆者の思ったことを書き連ねます。会計学もやってたので、両方を生かした記事を書きたいと考えています。 でもテーマが定まってない感がすごい。

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がかかる場合、これはパスワードを攻撃する実行可能なアプローチですか?



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






自分なりの答え

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現在、当シリーズへのアクセスがほとんどない