From: Robert Klemme <shortcutter@...>
Date: 2010-06-25T01:05:29+09:00
Subject: Re: Count substrings in string, scan too slow

2010/6/24 Jesús Gabriel y Galán <jgabrielygalan@gmail.com>:
> On Thu, Jun 24, 2010 at 5:04 PM, Danny Challis <dannychallis@gmail.com> wrote:
>> Hello everyone,
>>   I need to count the number of times a substring occurs in a string.
>> I am currently doing this using the scan method, but it is simply too
>> slow.  I feel there should be a faster way to do this since the scan
>> method is really designed for more advanced things than this.  I do not
>> need to do regex matching or to process the matches, just count
>> substrings.  So what I want is something like this:
>>
>> s = "you like to play with your yo-yo"
>> s.magical_count_method("yo") => 4
>>
>> Once again, what I'm really looking for is something fast.  I've tried
>> using external linux commands such as awk, but that was much much
>> slower. Any ideas?
>
> I don't know how slow is scan for you. An implementation using
> String#index and a loop is a little bit faster, but not too much:
>
> require 'benchmark'
>
> TIMES = 100_000
> s = "you like to play with your yo-yo"
>
> Benchmark.bmbm do |x|
>  x.report("scan") do
>    TIMES.times do
>        s.scan("yo").size
>    end
>  end
>  x.report("while") do
>    TIMES.times do
>        index = -1
>        count = 0
>        while (index = s.index("yo", index+1))
>                count += 1
>        end
>        count
>    end
>  end
> end
>
> $ ruby scan_vs_while.rb
> Rehearsal -----------------------------------------
> scan    0.560000   0.020000   0.580000 (  0.585972)
> while   0.440000   0.060000   0.500000 (  0.492969)
> -------------------------------- total: 1.080000sec
>
>            user     system      total        real
> scan    0.510000   0.010000   0.520000 (  0.519078)
> while   0.470000   0.020000   0.490000 (  0.493562)
>
> Don't know if this is enough for you, probably not :-)

I took the liberty to extend the benchmark a bit:

http://gist.github.com/451622

I would have expected regexp to be faster...

Cheers

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/