<div dir="ltr">On Sat, Oct 26, 2013 at 9:40 AM, David Nolan <span dir="ltr"><<a href="mailto:dave@textgoeshere.org.uk" target="_blank">dave@textgoeshere.org.uk</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><span style="background-color:rgb(251,251,251);color:rgb(51,51,51);font-family:Helvetica,arial,freesans,clean,sans-serif;font-size:13px;line-height:22px">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): </span><a href="https://gist.github.com/knaveofdiamonds/7155189#comment-936910" target="_blank">https://gist.github.com/knaveofdiamonds/7155189#comment-936910</a></div>



<div><div><br></div><div>As an aside, the fruity gem is excellent for benchmarking. This explains why: <a href="https://github.com/marcandre/fruity#approach" target="_blank">https://github.com/marcandre/fruity#approach</a>.</div>


</div></div></blockquote><div><br></div><div><br>Couldn't resist to also make a version with memoization (peter3).<br><br></div><div>* a reverse index on the haystack (somewhat like proper search engines do)<br>
</div><div>* caching of intermediate results near the end of the search tree (short values of remainder;<br></div><div>  this requires "cache tuning" for what is "short", which makes it a weaker solution ...)<br>

</div><div><br>On the RSpec timing test (multiplier 100, pattern 'lod', max remainder for cache 1), I now find this:<br><pre><code>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)</code></pre>Results and code in  <a href="https://gist.github.com/petervandenabeele/7161464" target="_blank">https://gist.github.com/petervandenabeele/7161464</a><br>
<br></div>
<div>As a "fruity" test, I ran 2 tests (only on the top 3 previous contenders + challenger):<br><br></div><div>* multiplier 50, pattern 'lod', max remainder for cache 2:<br></div><div><br></div><div>➜  koan git:(master) ✗ bundle exec ruby fruity/letters-benchmarking.rb<br>

Running each test once. Test will take about 20 seconds.<br>Peter3 is faster than Dave by 1.9x ± 0.1<br>Dave is faster than Peter by 3.1x ± 0.1<br>Peter is faster than Jason by 3x ± 0.1<br></div><div><br>* multiplier 25, pattern 'lold', max remainder for cache 2:<br>

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

Peter is faster than Jason by 80.0% ± 10.0%<br><br></div>I tried in vain ( a few times) to add the updated fruit test code as<br><div>a comment to <a href="https://gist.github.com/textgoeshere/02fd396e56ca8a8d2efe" target="_blank">https://gist.github.com/textgoeshere/02fd396e56ca8a8d2efe</a><br>

<div>I will e-mail it in private to Dave.<br><br>Have fun,<br><br>Peter<br></div></div></div></div></div>