Fastest way to reverse-process a string?

ruby-talk
1

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?

Thanks in advance.

···

--
Lloyd Zusman
ljz@asfast.com
God bless you.

2

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?

String#each_byte would avoid the creation of the array.

3

~ > ruby -e 's="raboof"; (s.size - 1).downto(0){|i| print s[i].chr}; puts'
foobar

-a

···

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?

Thanks in advance.

--
Lloyd Zusman
ljz@asfast.com
God bless you.

--

EMAIL :: Ara [dot] T [dot] Howard [at] noaa [dot] gov
PHONE :: 303.497.6469
A flower falls, even though we love it;
and a weed grows, even though we do not love it. --Dogen

===============================================================================

4

Joel VanderWerf <vjoel@PATH.Berkeley.EDU> writes:

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?

String#each_byte would avoid the creation of the array.

Thank you very much.

Does anyone know of a way to avoid 'reverse', as well? I discovered a
'reverse_each' method for arrays, but there doesn't seem to be a
corresponding String#reverse_each_byte. Without that, I would have to
incur the expense of reversing the string before applying each_byte to
it.

Any ideas?

···

--
Lloyd Zusman
ljz@asfast.com
God bless you.

5

Ara.T.Howard 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?

Thanks in advance.

--
Lloyd Zusman
ljz@asfast.com
God bless you.

~ > 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.

Gennady.

···

On Wed, 4 Aug 2004, Lloyd Zusman wrote:

-a
--

> EMAIL :: Ara [dot] T [dot] Howard [at] noaa [dot] gov
> PHONE :: 303.497.6469
> A flower falls, even though we love it;
> and a weed grows, even though we do not love it. | --Dogen

6

Joel VanderWerf <vjoel@PATH.Berkeley.EDU> writes:

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?

String#each_byte would avoid the creation of the array.

Thank you very much.

Does anyone know of a way to avoid 'reverse', as well? I discovered a
'reverse_each' method for arrays, but there doesn't seem to be a
corresponding String#reverse_each_byte. Without that, I would have to
incur the expense of reversing the string before applying each_byte to
it.

Any ideas?

You could write one in C... this should work, slight modification of each_byte code... untested:
static VALUE
rb_str_reverse_each_byte(str)
     VALUE str;
{
  long i = RSTRING(str)->len;

  while (i > 0) {
    i--;
    rb_yield(INT2FIX(RSTRING(str)->ptr[i] & 0xff));
  }
  return str;
}

···

On Aug 3, 2004, at 5:41 PM, Lloyd Zusman wrote:

--
Lloyd Zusman
ljz@asfast.com
God bless you.

7

Hi --

Ara.T.Howard 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

···

On Wed, 4 Aug 2004, Gennady wrote:

> On Wed, 4 Aug 2004, Lloyd Zusman wrote:

--
David A. Black
dblack@wobblini.net