maya's blog

About programming, aws and ubuntu

ビューティフルコード 4章 読書メモ

『Beautiful Code ビューティフルコード』

編者 Andy Oram, Greg Wilson

著者 Brian Kernighan, JonBentley, まつもとゆきひろ

訳者 久野 禎子, 久野 靖

ISBN 978-4-87311-363-0

4章 ものの見つけ方 ティム・ブレイ(Tim Bray)

  • 人々がコンピュータを使う目的を達成する主要なアプリケーションは「探索」
  • 探索はコンピュータサイエンスでは一番大きなテーマ
  • この章では1つの探索手法を深く考える

時間について

  • 探索を考える上で、時間を語るのは外せない
  • 探索問題に対して、2つのニュアンスを持つ異なる時間

    1. 探索実行に要する時間
    2. 探索機能を作るプログラマによって、またそのプログラムが完成するのを待っているマネージャや顧客たちによって過ごされる時間

問題:ブログのデータ

  • 筆者(Tim bray)のブログongoing by Tim Brayアクセスログ
  • この章を書いている時点で、140,070,104個のトランザクション(リクエストのこと?)
  • ブログのどの記事が一番多く読まれているか?という問題を考える
  • アクセスログの例
    • c80-216-32-218.cm-upc.chello.se - - [08/Oct/2006:06:37:48 -0700] "GET /ongoing/When/00x/2006/10/08/Grief-Lessons HTTP/1.1" 200 5945 "http://www.tbray.org/ongoing/" "Moilla/4.000 (compatible; Msie 6.0; Windows NT 5.1; S1; .NET CLr 1.1.4322)"

正規表現

  • 正規表現はテキスト中のパターンマッチを行うため専用に設計された特別な言語
  • GET /ongoing/When/\d\d\dx/\d\d\d\d/\d\d/\d\d/[^ .]+ "
    • ファイル名がピリオドを含む行にはマッチしない。Grief-Lessonsにはマッチするが、IMG0038.jpgにはマッチしない。
  • ピリオドは「任意の文字」にマッチするが、ピリオドが[]で囲まれるとその意味を失い、単に1つのピリオド記号を表す

正規表現を使えるようにする

  • 正規表現にマッチする行だけを表示するプログラムをRubyで書く
  • Rubyを採用したのは一番読みやすい言語だとTim Brayが思うから
ARGF.each_line do |line|
  if line =~ %r{GET /ongoing/When/\d\d\dx/\d\d\d\d/\d\d/\d\d/[^ .]+ }
    puts line
  end
end

1行目: 入力行を全部読み込み、各行ごとにループを回す

2行目: 正規表現にマッチした場合 Ruby%r{...}を使えばスラッシュをエスケープする必要がなくなるからいいよね

3行目: 正規表現にマッチした行を標準出力

4, 5行目: if, each_lineの終了

今回知りたいのはそれぞれの記事が取り出された回数。 正規表現でマッチした際の記事だけを標準出力するように上記コードを修正する。

ARGF.each_line do |line|
  if line =~ %r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) }
    puts $1
  end
end

2行目: 正規表現の中で、YYYY/MM/DD/記事名部分を丸括弧で囲んだ。

3行目: lineの値全体を標準出力させるのでなく、$1で「正規表現の中の丸括弧で印づけられた最初の場所」を表示

上記のコードで以下のような表示がされる

2003/10/10FooCampMacs
2006/11/13/ough-Mix
2003/05/22/StudentLookup
...

連想記憶

各行から記事名を抜き出し、それが何回取り出されたかを調べ、その回数に1を加え、その結果を再び保存する。 これは最も基本的な探索パターン。キーに基づいて、それに対応する値を見つける。

他の例

単語 - その単語を含むWebページの一覧 従業員数 - 従業員の個人情報 パスポート番号 - そのパスポートを持っている人を監視すべきかどうかを示す真偽値

  • これらを実現するデータ構造は連想記憶 言語によってはハッシュ、辞書、連想記憶, bla abla
  • rubyのハッシュを使って記事の参照頻度を数えるコード
counts = {}
counts.default = 0

ARGF.each_line do |line|
  if line =~ %r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) }
    counts[$1] += 1
  end
end
  • もしcounts[$1]が存在していればインクリメント。そうでければ1に設定
  • 「どの記事が一番多く読まれているのか」を知りたいので、「最も読まれている上位10個の記事を打ち出す」というコードを書く
counts = {}
counts.default = 0

ARGF.each_line do |line|
  if line =~ %r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) }
    counts[$1] += 1
  end
end

keys_by_counts = counts.keys.sort { |a, b| counts[b] <=> counts[a] }
keys_by_counts[0 .. 9].each do |key|
  puts "#{counts[key]}: #{key}"
end

10行目: counts.keysを昇順でソートし、keys_by_countに代入 - <=>は宇宙船演算子 ref: 1 <=> 2 # -1, 1 <=> 1 # 0, 3 <=> 1 # 1

11行目以降: 参照値が大きかった記事名トップ10を標準出力

筆者のマシン(1.67GH Apple Powerbook) 245MB (1,200,000行)のデータで、13.54秒掛かった。 処理が遅そう...

最適化のお時間

  • Perl版だと実行時間が半分程度だった。最適化が必要か?
  • コードのどこを最適化するのかを調べるため、プログラムの前半・後半部でどれだけ時間が掛かっているか計測
  • 結果前半部分(全行読み込み、回数集計)が7.36秒, 後半部分(整列、トップ10表示)が0.07秒
  • 前半部分を最適化は多分できない。正規表現のマッチ、ハッシュ表のデータを検索・更新するだけだから Rubyでも最適化がされている
  • 結論最適化は無駄だよね プログラマの時間や完成を待つ顧客の時間が浪費されるだけで、結果としてプログラムの実行時間はほぼ減らない
  • 他の探索アルゴリズムはどうなんだろうか?

問題:誰が、何を、いつ取り出したか?

  • ホスト名を指定して、そのホストから、いつ、何と言う記事が取得されたかのリストを作成
  • ハッシュは充填率が低い(かなり空いている)必要がある 235万ホストがあるので、大量のメモリが必要になる
  • ハッシュで実装すると、ハッシュ表をロードするのに55分のCPU時間を使用し、プログラムの使用メモリ量(ヒープ量)は1.56GB
  • 一度データをロード&ハッシュ表作成したら、ハッシュ表を直列化(serialize)(pythonデ言えばpickel化?)とかやりようはあるよね
  • 筆者の感覚では、まだヒープ量が少ないか、初期化の時間が少ないか、その両方であるようなプログラムがあるはず → 自分で探索コードを書こう

2分探索

  • Ruby 2分探索で実装すると、データロード時間は10分短くなったが、ヒープ量が100MB多かった
  • 千分の何秒オーダーだけど探索自体も遅くなった
  • Rubyは全てオブジェクトで、配列も多くの組み込みの仕掛けを持つ、かなり抽象化されたもの → Javaで実装しよう
package binary;

public class Finder {
  public static int find(String[] keys, String target) {
    int high = keys.length;
    int low = -1;
    while (high - low > 1) {
      int probe = (low + high) >>> 1;
      if (keys[probe].compareTo(target) > 0)
        high = probe;
      else
        low = probe;
    }
    if ( low == -1 || keys[low].compareTo(target) != 0)
      return -1;
    else
      return low;
  }
}
  • 5, 6行目で配列を走査するための変数を定義。初期値に配列の添字として正しくない値を設定しておき、それでもループが回るよう書いておくことで、様々な教会のケースを除外できる
  • 7行目でhighとlowが隣接するまでループを実行する
  • 8行目で2で割っている。論理演算を使っているのは、整数オーバーフロー対策

2分探索のトレードオフ

  • 計算量がO(log2 N)