Screaming Loud

研究・プログラミングなど気づいたことをメモをしています。読書記録はこちらに記載しています。https://bookmeter.com/users/75944

CodeKata 3 : どれくらい大きい?どれくらい速い?

今日は3つ目となるCodeKata: Kata Three: How Big, How Fast?を訳した。


大雑把な見積もりが出来るのは重要な才能だ。
せっせとコーディングしているとき、突然おおよそどれくらい大きいデータ構造を扱うのか、またループがどれくらいの速さで回るのか算出しなければならなくなるだろう。
これを早くできるほど、コーディングの流れを中断せずに済む。

さて、今回のシンプルなKata(型)は、大雑把に答える質問シリーズである。
頭の中で計算してみよう。
答えは1週間後くらいに投稿する。

How Big?

  • unsignedな表現を使うには、大体何ビット必要か?
    • 1000
    • 1,000,000
    • 1,000,000,000
    • 1,000,000,000,000
    • 8,000,000,000,000
  • 私の街には大体2万邸、家がある。名前と住所と電話番号全部を保存するにはどれくらいのスペースが必要だろうか?(もし全てを文字列としたら?)
  • 2分木に1,000,000の整数を保存した。大体、いくつくらいノードとどれくらいの深さだと思う?32bitマシンはどれくらいの領域を専有するだろうか?

How Fast?

フロー制御かプロトコルのオーバヘッドがないとすると、非同期の56kボーのモデム回線を使ってどれくらいの時間で送れるか?

  • 私の二分探索アルゴリズムは、1万要素の配列を検索するのに4.5msかかり、10万要素だと6msかかる。1000万要素の配列だったらどれくらい時間がかかるだろうか?(メモリについては気にしないでOK)
  • Unixパスワードは一方向ハッシュ関数を使って保存されている。というのも、オリジナルの文字列は「暗号化」されたバスワード列に変換され、元の文字列には変換されない。パスワードへの攻撃手段のひとつとして、可能な全ての平文パスワードを作り、その全てをハッシュ化してマッチするかを確かめ、もしマッチしたらクラッキングするという方法だ。

もしハッシュ値がマッチしたら、そのハッシュ化された文字列はオリジナルのパスワードである。(もしくは、同じくらいログインに関係しないオリジナルのパスワードと同じくらい良いもの??)
特定のシステムでは、パスワードを16文字以上にでき、96種類の文字から選べる。もしパスワードのハッシュ値を1msで作れるとしたら、この攻撃方法は実現可能か?


パスワードの問題文の括弧の中がうまく訳せませんでした。。

広告を非表示にする