From: "Jesús Gabriel y Galán" Date: 2010-06-25T01:16:29+09:00 Subject: Re: Count substrings in string, scan too slow On Thu, Jun 24, 2010 at 6:05 PM, Robert Klemme wrote: > 2010/6/24 Jesús Gabriel y Galán : >> On Thu, Jun 24, 2010 at 5:04 PM, Danny Challis 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... This thing about adding the length of the match can be argued depending on the requirements, I think. What would you expect from: "yoyoyoyo".magical_count_method("yoyo") 2 or 3? If you add the length to the index you get 2. If you add 1, you get 3. irb(main):018:0> s = "yoyoyoyo" => "yoyoyoyo" irb(main):019:0> count = 0 => 0 irb(main):020:0> len = s.length => 8 irb(main):021:0> search = "yoyo" => "yoyo" irb(main):023:0> len = search.length => 4 irb(main):024:0> index = -len => -4 irb(main):025:0> while (index = s.index(search, index + len)) irb(main):026:1> count += 1 irb(main):027:1> end => nil irb(main):028:0> count => 2 irb(main):029:0> count = 0 => 0 irb(main):030:0> index = -1 => -1 irb(main):031:0> while (index = s.index(search, index + 1)) irb(main):032:1> count += 1 irb(main):033:1> end => nil irb(main):034:0> count => 3 So, I don't know. Of course, if the requirement is to get 2 from the above situation, adding the length is better. Also of notice is that the block versions of scan are slower because they have to call a block for each match. I think I've read that the String#index method uses Rabin-Karp. It would be interesting to compare this to a Boyer-Moore implementation. Of course it will depend on the input data, if it's near the best or worst case for each, but anyway. Jesus.