[ruby-list:14408] goo.rb

akaishi です。

きのうメールを出したのですが返ってこないので再送します。
もし2通届いたらすみません。
しかし netlab.co.jp ってやたらと重くないですか?

::::::::::

九大の西さんが作られた goo-0.2.rb というプログラムがあります。それは、
WWW のアクセスログの referer の情報から、自分のページが検索エンジンでど
のようなキーワードで検索され、アクセスされたかを調べるものですが、その 
goo-0.2.rb を元に、ruby と perl の速度の比較をしてみました。

# あまり厳密な比較ではないので目安程度にみてください。

1. 

goo-0.2.rb が対象とするログは一般的な形式ではなかったため、より一般的と
思われる Apache の combined 形式に対応させたものを自分で作成し、さらに同
一の正規表現を使った perl 版も作って速度の比較をしました。

http://ruby.freak.ne.jp/goo/goo1.rb	ruby 版
http://ruby.freak.ne.jp/goo/goo1.pl	perl 版

それぞれで、某 WWW サーバから持ってきたアクセスログ 50000行を食わせた時
間を測定しました(環境 Pentium II 333MHz, RAM 96MB)。時間は複数回測定し、
最速のものをのせています。ruby のバージョンは ruby 1.2.3, perl は
5.005_02 です。

ruby 版の結果	35秒68
perl 版の結果	12秒95

残念ながら perl の方が圧倒的に速いという結果が出ました。


2.

WWW のアクセスログを良く見ると、この中で検索エンジンからたどられてきた行
の割合は全体から見ると極少ないことがわかります。よって全ての行に対して複
雑な正規表現を適用するよりも、まず検索エンジンからたどられてきたっぽい行
だけを簡単(高速)なテストで抜き出し、それから本番の正規表現を適用した方が
速くなると思われます。

具体的には

while access_log = gets
  if access_log =~ CompiledRegex
    ...
  end
end

となっているのを、

while access_log = gets
  if access_log.index(??)
    if access_log =~ CompiledRegex
      ...
    end
  end
end

としてみました。検索エンジンからたどられてきた行は必ず '?' を含んでいま
す。逆に '?' が含まれているからといって必ず検索エンジンからたどられてき
ているとは限りませんが、これでかなり絞り込めるはずです。

このように修正して同じテストを実施すると

ruby 版の結果	6秒73
perl 版の結果	3秒70

どちらも速くなりましたが、まだ perl のほうがずっと速いです。

なお、固定1文字の検索ならば、access_log =~ /\?/ よりも
access_log.index(??) のほうが高速です。
(index の代りに include? でも良い)


3.

今度は RegexStr の

http:\/\/.*(' + HostsStr + ')[^\?]*\?

という部分を

http:\/\/.*\b(' + HostsStr + ')\b[^\?]*\?

にしてみます。これで正規表現でのバックトラックの回数が減ると思われます。

ruby 版の結果	4秒74
perl 版の結果	3秒07


4.

'?' を含んだ行で絞り込みましたが、'?' を含んでいるからといって検索エンジ
ンからたどってきたログとは限りません。それでさらにもう一段、ホスト名パター
ンで絞り込みをかけます。

まず、

RegexStr = '^([^ ]*) \S* \S* \[(\S*) \+\d*\] \"\w* ([^\ ]*) \S*\" \d* \d* "http:\/\/.*\b(' + HostsStr + ')\b[^\?]*\?([^"]+)'

これを次のようにホスト名部分を分離します。

RegexStr = '^([^ ]*) \S* \S* \[(\S*) \+\d*\] \"\w* ([^\ ]*) \S*\" \d* \d* "http:\/\/[^\?]*\?([^"]+)'
CompiledHosts = /\b(goo\.ne\.jp|infoseek\.ne\.jp|infoseek\.com|......)\b/

そしてループ部分を次のように変更します。

  if access_log =~ /\?/ && access_log =~ CompiledHosts
    robothost = $1
    if access_log =~ CompiledRegex
      host, date, target, args = $1, $2, $3, $4
      ...
    end
  end

ruby 版の結果	2秒58
perl 版の結果	3秒57

ついに ruby が逆転しました。それだけ ruby の fastmap は効果があるのでしょ
う。perl は何故か 3. のときよりも遅くなっています。

最終的なプログラム
http://ruby.freak.ne.jp/goo/goo4.rb	ruby 版

これと同等な perl 版
http://ruby.freak.ne.jp/goo/goo4.pl	perl 版

perl 版で、試した中では一番速かったもの
http://ruby.freak.ne.jp/goo/goo3.pl


5.

ruby-1.3.3-990513 では正規表現エンジンが non-POSIX NFA 型になりました。
それで試すとさらにちょっと速くなります。

ruby-1.3.3-990513 の結果  2秒42
(4. と同じスクリプトの結果)


ともかく、http://www.netlab.co.jp/ruby/jp/pcjp98/page16.html に「正規表
現ルーチンは Perl が速い」と書いてありますが、そうとばかりもいえないよう
です。

注: Perl 版は、Perl に詳しい人が手を入れればきっともっと速くなるでしょう。
    Ruby 版も。

    また、アクセスログの中身によって、結果は異なったものになる可能性もあ
    ります。極端な話、全部の行が CompiledRegexp にマッチするものならば
    前段の絞り込みは無効になり、perl 版のほうが速くなるかもしれません。

6.

原作者の西さんから、最新版の RobotHostHash を頂きました。これを反映させ
たバージョンを

http://ruby.freak.ne.jp/goo/goo.rb	ruby 版

に置いてあります。