From: "David A. Black" <dblack@...>
Date: 2004-08-04T11:27:21+09:00
Subject: Re: Fastest way to reverse-process a string?

Hi --

On Wed, 4 Aug 2004, Gennady wrote:

> Ara.T.Howard wrote:
> > On Wed, 4 Aug 2004, Lloyd Zusman wrote:
> > 
> >> In a ruby program I'm writing, I want to parse a string in reverse and
> >> feed each of its individual characters through a state machine.
> >>
> >> A "hammer and tongs" solution looks like this:
> >>
> >>  string.reverse.split(//).each {
> >>    |ch|
> >>    feedIntoStateMachine(ch)
> >>  }
> >>
> >> However, this seems rather inefficient.  Does anyone know of a faster
> >> algorithm for this in ruby?
> > 
> > ~ > ruby -e 's="raboof"; (s.size - 1).downto(0){|i| print s[i].chr}; puts'
> > foobar
> > 
> 
> If you add this as a fourth benchmark
> 
>    x.report("4") {
>      size = str.size - 1
>      100000.times {
>        size.downto(0) { |_index|
>          str[_index].chr
>        }
>      }
>    }
> 
> The result will be:
>               user     system      total        real
> 1        2.630000   0.000000   2.630000 (  2.627852)
> 2        2.660000   0.000000   2.660000 (  2.659415)
> 3        1.600000   0.000000   1.600000 (  1.597412)
> 4        1.840000   0.000000   1.840000 (  1.845511)
> 
> So this algorithm is next to the fastest one based on each_byte.

Here's another one:

    x.report("5") { 
      60000.times { str.unpack("C*").reverse_each { |ch| ch.chr } }
    }

Removing the first two, which are consistently slowest, I've now got
this script -- see below for results for strings of different lengths:

require 'benchmark'
include Benchmark

def bench(str)
  bm(7) do |x|
    x.report("1") { 
      60000.times { str.reverse.each_byte { |ch| ch.chr } }
    }
    x.report("2") {
      size = str.size - 1
      60000.times { size.downto(0) { |i| str[i].chr }
      }
    }
    x.report("3") { 
      60000.times { str.unpack("C*").reverse_each { |ch| ch.chr } }
    }
  end
end

bench("abc")
bench("abcdef")
bench("abcdefghi")
bench("Hammer and tongs")

# Results:
             user     system      total        real
1        0.560000   0.000000   0.560000 (  0.574237)
2        0.600000   0.000000   0.600000 (  0.600002)
3        0.650000   0.000000   0.650000 (  0.650740)
             user     system      total        real
1        0.970000   0.010000   0.980000 (  0.988775)
2        1.080000   0.000000   1.080000 (  1.082217)
3        1.060000   0.000000   1.060000 (  1.064561)
             user     system      total        real
1        1.340000   0.000000   1.340000 (  1.341539)
2        1.570000   0.000000   1.570000 (  1.568368)
3        1.470000   0.000000   1.470000 (  1.473809)
             user     system      total        real
1        2.250000   0.000000   2.250000 (  2.245000)
2        2.690000   0.000000   2.690000 (  2.684963)
3        2.420000   0.000000   2.420000 (  2.417045)

What this suggests is that as the string gets longer, unpack becomes
the fastest.  But there's no huge difference among the three.


David

-- 
David A. Black
dblack@wobblini.net