忘れたときに備えた記録

トップ «前の日記(2008-01-10(Thursday)) 最新 次の日記(2008-01-12(Saturday))» 編集
2005|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|11|12|
2009|01|02|03|04|05|06|10|12|
2010|06|07|08|12|
2011|07|09|
2012|09|11|
2013|02|03|09|
2015|10|11|
2016|01|08|11|
2017|02|08|10|
2018|11|
2020|03|

2008-01-11(Friday)

Hiki XHTML化キット0.21.2を公開しました

不適切な正規表現を使用していたことが原因で、処理に時間がかかりすぎる場合があった問題を解決しました。

ダウンロードはこちらからどうぞ。

Tags: 更新

正規表現怖い

まんじゅう怖いとか、そういう話ではないのです。

昨日から発覚したx-hikiの問題は、突き詰めると次のような正規表現が原因でした。

#!/usr/bin/ruby
def speed(m="Time")
   t = Time.now
   yield if block_given?
   print "#{m}:" if m
   puts Time.now-t
end

r = /(?:a+)*c/
1000.times do |n|
   s = "a"*n+"bc"
   puts n
   puts s
   speed do
      puts s=~r, $&
   end
   $stdout.flush
end

このスクリプトは、"aaaaaaaaabc"という文字列と /(?:a+)*c/という正規表現とのマッチを、文字列前半の"aaa..."の部分を1文字ずつ大きくして試し、かかった時間を表示するものです。

実行すると、こうなります。

~$ ./test.rb 
0
bc
1
c
Time:9.4e-05
1
abc
2
c
Time:7.1e-05
2
aabc
3
c
Time:6.7e-05

この辺は、特に問題ありません。

aaaaaaabc
8
c
Time:0.000119
8
aaaaaaaabc
9
c
Time:0.000162
9
aaaaaaaaabc
10
c
Time:0.00026
10
aaaaaaaaaabc
11
c
Time:0.000451
11
aaaaaaaaaaabc
12
c
Time:0.000831

段々恐ろしい気配が出てきます。

aaaaaaaaaaaaaaaaaaaabc
21
c
Time:0.351611
21
aaaaaaaaaaaaaaaaaaaaabc
22
c
Time:0.710038
22
aaaaaaaaaaaaaaaaaaaaaabc
23
c
Time:1.573933
23
aaaaaaaaaaaaaaaaaaaaaaabc
24
c
Time:3.230857
24
aaaaaaaaaaaaaaaaaaaaaaaabc
25
c
Time:6.429239

なんと、たった25文字の文字列のマッチを判定するにのに、6秒以上もかかっています。

それより何より、1文字増える毎に所要時間が2倍になっています!

オチも無いままに終わります。

aaaaaaaaaaaaaaaaaaaaaaaaaaaaabc
30
c
Time:199.959477

どっとはらいヽ(´ー`)丿

Tags: Ruby

正規表現怖いの続き

ふと思いついて、perlで同様の正規表現を使ってみた。

#!/usr/bin/perl
$s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabc";
if($s =~ /(?:a+)*c/){
   print $&, "\n";
}

実行すると

hiraku@hirakuro:~/tmp$ perl -v

This is perl, v5.8.8 built for i486-linux-gnu-thread-multi

Copyright 1987-2006, Larry Wall

Perl may be copied only under the terms of either the Artistic License or the
GNU General Public License, which may be found in the Perl 5 source kit.

Complete documentation for Perl, including FAQ lists, should be found on
this system using "man perl" or "perldoc perl".  If you have access to the
Internet, point your browser at http://www.perl.org/, the Perl Home Page.

hiraku@hirakuro:~/tmp$ time perl test.pl
c

real    0m0.004s
user    0m0.004s
sys     0m0.000s

おや。簡単に終わったしまった。

そこで、さっきのスクリプトを、異なるバージョンのRubyで試してみた。

さっき日記に書いたときに試したのはUbuntu7.10の標準のRubyで

hiraku@hirakuro:~$ ruby -v
ruby 1.8.6 (2007-06-07 patchlevel 36) [i486-linux]

これは、文字列が1文字分長くなる毎に実行時間が2倍になっていた。

で、最新安定版を入れて試してみた。

hiraku@hirakuro:~$ ~/opt/ruby1.8.6p111/bin/ruby -v
ruby 1.8.6 (2007-09-24 patchlevel 111) [i686-linux]
hiraku@hirakuro:~$ ~/opt/ruby1.8.6p111/bin/ruby test.rb 
0
bc
1
c
Time:7.6e-05
(中略)
Time:0.404212
21
aaaaaaaaaaaaaaaaaaaaabc
22
c
Time:0.802581
22
aaaaaaaaaaaaaaaaaaaaaabc
23
c
Time:1.704644
(以下略)

これも倍々になってしまった。

最後に最新版1.9.0をやってみると

hiraku@hirakuro:~$ ~/opt/ruby1.9/bin/ruby -v
ruby 1.9.0 (2007-12-25 revision 14709) [i686-linux]
hiraku@hirakuro:~$ ~/opt/ruby1.9/bin/ruby test.rb
0
bc
1
c
Time:1.7495e-05
(中略)
999
a(略)abc
1000
c
Time:0.014532279

お、おおおお!素晴らしい!!鬼車&1.9.0万歳!!!

Tags: Ruby

例外型カスタムマッチャ

今度はカスタム抹茶が怖い。という話しではないのです。

最近、Rubyist Magazine - スはスペックのス 【第 1 回】 RSpec の概要と、RSpec on Rails (モデル編)を参考にRSPecを使い始めました。 で、普通の

1.should > 0

みたいに使うカスタムマッチャはこのへんを参考に作れたのですが、

assert_raise(){}

の代わりになる

lambda{}.should raise_error()

のようなカスタムマッチャの作り方がすこし手間取ったので、出来たサンプルを忘れたときに備えて公開です。

前半がカスタムマッチャの定義で、後半が使用例です。

class RaiseCustom
   def initialize(expected)
      @expected = expected
   end

   def matches?(proc)
      begin
         proc.call
      rescue => @actual
         return @actual.is_a?(@expected)
      else
         return false
      end
   end

   def failure_message
      if @actual
         "raise #{@expected} expected but #{@actual} raised"
      else
         "raise #{@expected} expected but nothing raised"
      end
   end

   def negative_failure_message
      if @actual
         "NOT raise #{@expected} expected but #{@actual} raised"
      else
         raise "Must not happen"
      end
   end
end

def raise_custom(expected)
   RaiseCustom.new(expected)
end

describe "raise_error-type matcher" do
   it "should raise StandardError but nothing raised" do
      lambda{}.should raise_error(StandardError)
   end

   it "should raise ArgumentErroror but RuntimeError" do
      lambda{raise "hoge"}.should raise_error(ArgumentError)
   end

   it "should not raise StandardError but raised" do
      lambda{raise StandardError}.should_not raise_error(StandardError)
   end

   it "should raise(custom) StandardError but nothing raised" do
      lambda{}.should raise_custom(StandardError)
   end

   it "should raise(custom) ArgumentError but RuntimeError raise" do
      lambda{raise "hoge"}.should raise_custom(ArgumentError)
   end

   it "should not raise(custom) StandardError but raised" do
      lambda{raise StandardError}.should_not raise_custom(StandardError)
   end

   it "should not raise(custom) ArgumentError and RuntimeError raised" do
      lambda{raise "hoge"}.should_not raise_custom(ArgumentError)
   end
end
Tags: RSpec

RSpecのドキュメント

RubyForgeにあるRSpecのドキュメント、例えば http://rspec.rubyforge.org/documentation/tools/spec.html なんかを表示すると、少し変な風に表示されてしまうなと思っていたのですが、どうもドキュメントページは http://rspec.info/documentation/tools/spec.html に移っていたようです。

こっちは、スタイルシートがきちんと適用されて綺麗に表示されています。

Tags: RSpec
本日のツッコミ(全2件) [ツッコミを入れる]
_ g5n (2008-01-11(Friday) 22:44)

万歳なのは鬼車と思われ>1.9.0

_ ひらく (2008-01-12(Saturday) 00:20)

言われてみればその通りですね。訂正しました

[]