# Fastest way to reverse-process a string? **URL:** \ **Category:** ruby-talk\ **Created:** [3 August 2004 23:27 UTC](https://rubytalk.org/t/fastest-way-to-reverse-process-a-string/12889 "2004-08-03T23:27:31Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![Lloyd\_Zusman](https://avatars.discourse-cdn.com/v4/letter/l/8baadc/32.png) [@Lloyd\_Zusman](https://rubytalk.org/u/Lloyd_Zusman)\ **Post date:** [3 August 2004 23:27 UTC](https://rubytalk.org/t/fastest-way-to-reverse-process-a-string/12889/1 "2004-08-03T23:27:31Z")
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](mailto:ljz@asfast.com) > God bless you. ---
**Author:** ![Joel\_VanderWerf1](https://avatars.discourse-cdn.com/v4/letter/j/94ad74/32.png) [@Joel\_VanderWerf1](https://rubytalk.org/u/Joel_VanderWerf1)\ **Post date:** [4 August 2004 00:15 UTC](https://rubytalk.org/t/fastest-way-to-reverse-process-a-string/12889/2 "2004-08-04T00:15:26Z")
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. ---
**Author:** ![Ara.T.Howard3](https://avatars.discourse-cdn.com/v4/letter/a/7cd45c/32.png) [@Ara.T.Howard3](https://rubytalk.org/u/Ara.T.Howard3)\ **Post date:** [4 August 2004 00:42 UTC](https://rubytalk.org/t/fastest-way-to-reverse-process-a-string/12889/3 "2004-08-04T00:42:07Z")
~ \> 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 > > =============================================================================== ---
**Author:** ![Lloyd\_Zusman](https://avatars.discourse-cdn.com/v4/letter/l/8baadc/32.png) [@Lloyd\_Zusman](https://rubytalk.org/u/Lloyd_Zusman)\ **Post date:** [4 August 2004 00:41 UTC](https://rubytalk.org/t/fastest-way-to-reverse-process-a-string/12889/4 "2004-08-04T00:41:05Z")
Joel VanderWerf \ 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. ---
**Author:** ![Gennady1](https://avatars.discourse-cdn.com/v4/letter/g/a4c791/32.png) [@Gennady1](https://rubytalk.org/u/Gennady1)\ **Post date:** [4 August 2004 01:19 UTC](https://rubytalk.org/t/fastest-way-to-reverse-process-a-string/12889/5 "2004-08-04T01:19:53Z")
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 ---
**Author:** ![Charles\_Mills1](https://avatars.discourse-cdn.com/v4/letter/c/85f322/32.png) [@Charles\_Mills1](https://rubytalk.org/u/Charles_Mills1)\ **Post date:** [4 August 2004 00:47 UTC](https://rubytalk.org/t/fastest-way-to-reverse-process-a-string/12889/6 "2004-08-04T00:47:16Z")
> Joel VanderWerf \ 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. ---
**Author:** ![David\_A\_Black3](https://avatars.discourse-cdn.com/v4/letter/d/6a8cbe/32.png) [@David\_A\_Black3](https://rubytalk.org/u/David_A_Black3)\ **Post date:** [4 August 2004 02:27 UTC](https://rubytalk.org/t/fastest-way-to-reverse-process-a-string/12889/7 "2004-08-04T02:27:21Z")
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