[#22684] [Bug #1247] YAML::load converts some dates into strings — Matthew Wilson <redmine@...>

Bug #1247: YAML::load converts some dates into strings

10 messages 2009/03/05

[#22725] [Bug #1253] Fix MSVC Build Issues — Charlie Savage <redmine@...>

Bug #1253: Fix MSVC Build Issues

13 messages 2009/03/07

[#22727] Moving ruby 1.9.1 forward on windows — Charlie Savage <cfis@...>

Hi everyone,

14 messages 2009/03/08

[#22731] [Bug #1255] += for large strings egrigiously slow — James Lee <redmine@...>

Bug #1255: += for large strings egrigiously slow

11 messages 2009/03/08

[#22736] Ruby 1.9.1 and tail recursion optimization — =?ISO-8859-15?Q?Wolfgang_N=E1dasi-Donner?= <ed.odanow@...>

Moin, moin!

13 messages 2009/03/08
[#22739] Re: Ruby 1.9.1 and tail recursion optimization — =?ISO-8859-15?Q?Wolfgang_N=E1dasi-Donner?= <ed.odanow@...> 2009/03/08

Wolfgang N疆asi-Donner schrieb:

[#22748] [Feature #1256] Add constant TAILRECURSION to let a program recognize if tail recursion optimization is implemented — Wolfgang Nádasi-Donner <redmine@...>

Feature #1256: Add constant TAILRECURSION to let a program recognize if tail recursion optimization is implemented

7 messages 2009/03/08

[#22803] Relegate 1.8.6 to Engine Yard, part II — Urabe Shyouhei <shyouhei@...>

Hello and sorry for my being slow for this issue. It's OK now for me to pass

21 messages 2009/03/10

[#22812] [Bug #1261] cross-compiling Ruby extensions using mkmf doesn't fully respect DESTDIR — Daniel Golle <redmine@...>

Bug #1261: cross-compiling Ruby extensions using mkmf doesn't fully respect DESTDIR

8 messages 2009/03/10

[#22892] Ruby Time — valodzka <valodzka@...>

Got tired of current ruby Time limitation, I have written this -

24 messages 2009/03/14
[#22949] Re: Ruby Time — Tanaka Akira <akr@...> 2009/03/19

In article <9e19ed87-9d12-4f98-af3c-bd49a71b0bd4@p11g2000yqe.googlegroups.com>,

[#22974] Re: Ruby Time — valodzka <valodzka@...> 2009/03/20

[#22977] Re: Ruby Time — Urabe Shyouhei <shyouhei@...> 2009/03/20

valodzka wrote:

[#22981] Re: Ruby Time — valodzka <valodzka@...> 2009/03/21

> I bet you'll get tired of updating that database. There's a major difference

[#22893] [Feature #1291] O_CLOEXEC flag missing for Kernel::open — David Martin <redmine@...>

Feature #1291: O_CLOEXEC flag missing for Kernel::open

10 messages 2009/03/15

[#22939] [Bug #1303] A name considered a local variable on RHS of an assignment that defines it — Tomas Matousek <redmine@...>

Bug #1303: A name considered a local variable on RHS of an assignment that defines it

8 messages 2009/03/19

[#23063] [Bug #1332] Reading file on Windows is 500x slower then with previous Ruby version — Damjan Rems <redmine@...>

Bug #1332: Reading file on Windows is 500x slower then with previous Ruby version

11 messages 2009/03/30

[#23075] [Bug #1336] Change in string representation of Floats — Brian Ford <redmine@...>

Bug #1336: Change in string representation of Floats

37 messages 2009/03/31
[#23179] [Bug #1336] Change in string representation of Floats — Roger Pack <redmine@...> 2009/04/11

Issue #1336 has been updated by Roger Pack.

[#23181] Re: [Bug #1336] Change in string representation of Floats — Brent Roman <brent@...> 2009/04/11

[#23186] Re: [Bug #1336] Change in string representation of Floats — Yukihiro Matsumoto <matz@...> 2009/04/12

Hi,

[#23187] Re: [Bug #1336] Change in string representation of Floats — Brent Roman <brent@...> 2009/04/13

[#23188] Re: [Bug #1336] Change in string representation of Floats — Yukihiro Matsumoto <matz@...> 2009/04/13

Hi,

[ruby-core:22936] Re: [Bug #1301] Poor RegExp Matching Performance

From: Martin Duerst <duerst@...>
Date: 2009-03-19 01:59:16 UTC
List: ruby-core #22936
At 23:53 09/03/18, Andreas Grau wrote:
>Bug #1301: Poor RegExp Matching Performance
>http://redmine.ruby-lang.org/issues/show/1301
>
>Author: Andreas Grau
>Status: Open, Priority: Normal
>Category: core
>ruby -v: 1.9.0 (2008-06-20 revision 17482) [i486-linux]
>
>I noticed a very poor performance on matching regular expressions.
>
>Running following code using ruby 1.9.0 on a Core2Duo (2x2Ghz) takes more 
>than 20s to complete.
>
>regexp = /[b]+.+.+.+.+.+.+.+.+[a]/

Eero gave a much better way to write this regexp.
But why is it so bad, in particular for the string
below? The string has 37 'b's, and you are asking
it to try all different ways it can be split into
nine non-empty substrings (the first of which has
to consist of 'b's only), followed by an [a]. It's
surprising that this only takes 23 seconds! 

Theory about regular expressions (formal language theory)
says there shouldn't be any difference, but Ruby regular
expressions (same for Perl, Python, and so on) are not
really regular expressions in the formal sense anymore,
because they allow capturing and many more neat practical
things. So the implementation uses backtracking, and
your regexp above creates a lot of backtracking.
For details on how to write good regular expressions,
please see Jeffrey Friedl's book
(e.g. at
http://www.amazon.com/Mastering-Regular-Expressions-Jeffrey-Friedl/dp/0596528124/)

BTW, the [] in the above expression are not necessary,
it would usually be written

regexp = /b+.+.+.+.+.+.+.+.+a/

Regards,    Martin.

>str="bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
>regexp.match(str)
>
>$ time ruby1.9  test.rb 
>
>real    0m23.029s
>user    0m22.421s
>sys     0m0.012s
>
>
>----------------------------------------
>http://redmine.ruby-lang.org


#-#-#  Martin J. Du"rst, Assoc. Professor, Aoyama Gakuin University
#-#-#  http://www.sw.it.aoyama.ac.jp       mailto:duerst@it.aoyama.ac.jp     


In This Thread