Fastest way to reverse-process a string?

[Lloyd Zusman]

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.

 

[Joel VanderWerf]

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.

 

[Ara.T.Howard]

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.

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


-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
===============================================================================

 

[Lloyd Zusman]

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?

 

[Charles Mills]

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 & 0xff));
}
return str;
}

 

[Gennady]

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.

~ > ruby -e 's="raboof"; (s.size - 1).downto(0){|i| print s.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.

-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
===============================================================================

 

[David A. Black]

Hi --

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