[LRUG] Recursion diversion

[Peter Vandenabeele]

On Sat, Oct 26, 2013 at 9:40 AM, David Nolan <dave at textgoeshere.org.uk>wrote:

> With a bit of memoization, this one runs pretty fast (2+ times faster than
> the next fastest on haystacks > 100 chars and needles > 4 chars, and
> increasingly much better as the strings get larger):
> https://gist.github.com/knaveofdiamonds/7155189#comment-936910
>
> As an aside, the fruity gem is excellent for benchmarking. This explains
> why: https://github.com/marcandre/fruity#approach.
>


Couldn't resist to also make a version with memoization (peter3).

* a reverse index on the haystack (somewhat like proper search engines do)
* caching of intermediate results near the end of the search tree (short
values of remainder;
  this requires "cache tuning" for what is "short", which makes it a weaker
solution ...)

On the RSpec timing test (multiplier 100, pattern 'lod', max remainder for
cache 1), I now find this:

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)

Results and code in  https://gist.github.com/petervandenabeele/7161464

As a "fruity" test, I ran 2 tests (only on the top 3 previous contenders +
challenger):

* multiplier 50, pattern 'lod', max remainder for cache 2:

➜  koan git:(master) ✗ bundle exec ruby fruity/letters-benchmarking.rb
Running each test once. Test will take about 20 seconds.
Peter3 is faster than Dave by 1.9x ± 0.1
Dave is faster than Peter by 3.1x ± 0.1
Peter is faster than Jason by 3x ± 0.1

* multiplier 25, pattern 'lold', max remainder for cache 2:

➜  koan git:(master) ✗ bundle exec ruby fruity/letters-benchmarking.rb
Running each test once. Test will take about 1 minute.
Peter3 is similar to Dave
Dave is faster than Peter by 2.3x ± 0.1
Peter is faster than Jason by 80.0% ± 10.0%

I tried in vain ( a few times) to add the updated fruit test code as
a comment to https://gist.github.com/textgoeshere/02fd396e56ca8a8d2efe
I will e-mail it in private to Dave.

Have fun,

Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lrug.org/pipermail/chat-lrug.org/attachments/20131026/77a0c2c8/attachment-0003.html>