[LRUG] Recursion diversion

[Peter Vandenabeele]

On Sat, Oct 26, 2013 at 12:44 PM, Dominic Baggott <dominic.baggott at gmail.com
> wrote:

> I've updated my shockingly slow recursive version by making it do a better
> tail call. It now runs about as fast as Tom's recursive solution. I've also
> added a completely different approach that runs about as fast as Dave's
> solution.
>
> https://gist.github.com/evilstreak/7161191
>


For sake of completeness, I updated the gist with now 10 different
implementations :-)

  https://gist.github.com/petervandenabeele/7161464

<quote>
➜  fruity git:(master) ✗ # below: multiplier 50, pattern 'lod'
➜  fruity git:(master) ✗ ruby letters-benchmarking.rb
Running each test once. Test will take about 17 seconds.
Peter3 is faster than DominicLists by 30.000000000000004% ± 10.0%
DominicLists is faster than Dave by 30.000000000000004% ± 10.0%
Dave is faster than Jason by 10x ± 1.0

➜  fruity git:(master) ✗ # below : multiplier 25, pattern 'lold'
➜  fruity git:(master) ✗ ruby letters-benchmarking.rb
Running each test once. Test will take about 1 minute.
DominicLists is faster than Peter3 by 19.999999999999996% ± 1.0%
Peter3 is faster than Dave by 10.000000000000009% ± 10.0%
Dave is faster than Jason by 4x ± 0.1

As an *extremely* naive speed test, changing the test string to ("hello
world" * 100) and running rspec again on all 10 yields (seconds, lines of
code, and max RSIZE as seen in top -o cpu on MacBook Pro).

roland_spec.rb       =>   9.14 s  11 loc (1035 MB max RSIZE)
michael_spec.rb      =>   8.82 s  13 loc (1044 MB max RSIZE)
peter_spec.rb        =>   5.91 s  30 loc ( 244 MB max RSIZE)
tom_spec.rb          =>  20.05 s   9 loc ( 326 MB max RSIZE)
dominic_spec.rb      => 395.   s  14 loc ( 434 MB max RSIZE)
jason_spec.rb        =>  16.21 s  19 loc ( 535 MB max RSIZE)
peter2_spec.rb       =>   5.24 s  42 loc ( 222 MB max RSIZE)
dave_spec.rb         =>   4.82 s  19 loc ( 323 MB max RSIZE)
peter3_spec.rb       =>   4.42 s  39 loc ( 239 MB max RSIZE)
dominic_recursion.rb =>  64.47 s  10 loc ( 482 MB max RSIZE)
dominic_lists.rb     =>   4.21 s  10 loc ( 195 MB max RSIZE)

</quote>

Interestingly enough (or trivially "as expected" ?) the non-recursive
implementation
"dominic_lists" takes less memory and is fastest solution in the naive
rspec test.

Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lrug.org/pipermail/chat-lrug.org/attachments/20131028/91d04eb3/attachment.html>