<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><br>
</div><div>Dave</div><div>@davenolan<br><br></div></div>
<br><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Peter Vandenabeele</b> <span dir="ltr"><<a href="mailto:peter@vandenabeele.com" target="_blank">peter@vandenabeele.com</a>></span><br>
Date: 26 October 2013 08:19<br>Subject: Re: [LRUG] Recursion diversion<br>To: LRUG Users Group <<a href="mailto:chat@lists.lrug.org" target="_blank">chat@lists.lrug.org</a>><br><br><br><div dir="ltr"><div><div><div>
<div><div>Good morning,<br>
<br></div>A sincere apology to Michael Pavling !<br><br>I had incorrectly copied his code and reported it as "not correct",<br></div>sorry for that.<br><br>
When now properly copying the code and testing, it does pass<br></div>all tests correctly. I also measured the timing and added it to<br>the list.<br><br></div>Also Jason added a version that I added to the list.<br><br>
I couldn't resist and made a second version (peter2), where I use a<br>
kind of "rainbow table" to avoid recreating over and over the partial<br>copies of the haystack. This gives some improvement to the<br>speed and memory consumption, but clearly not dramatic (and<br></div><div>that for a lot of additional lines of code ...).<br>
</div><div><br>The new results are:<br><br>* s => seconds for running on "hello world" * 100<br>* loc => lines of code (grep -v blank lines)<br>* max RSIZE (as seen in `top -o cpu` on MacBook Pro).<br> <br>
<span style="font-family:'courier new',monospace">```<br>roland_spec.rb => 9.14 s 11 loc (1035 MB max RSIZE)<br>michael_spec.rb => 8.82 s 13 loc (1044 MB max RSIZE)<br>peter_spec.rb => 5.91 s 30 loc ( 244 MB max RSIZE)<br>
tom_spec.rb => 20.05 s 9 loc ( 326 MB max RSIZE)<br>dominic_spec.rb => 395. s 14 loc ( 300 something MB ?)<br>jason_spec.rb => 16.21 s 19 loc ( 535 MB max RSIZE)<br>peter2_spec.rb => 5.24 s 42 loc ( 222 MB max RSIZE)<br>
```<br></span></div><div><br>Full details on:<br></div><div><br> <a href="https://gist.github.com/petervandenabeele/7161464" target="_blank">https://gist.github.com/petervandenabeele/7161464</a><br></div><div><br>Have a good weekend,<br>
<br>Peter</div></div><div class="gmail_extra"><div><div><br><br><div class="gmail_quote">On Fri, Oct 25, 2013 at 11:12 PM, Peter Vandenabeele <span dir="ltr"><<a href="mailto:peter@vandenabeele.com" target="_blank">peter@vandenabeele.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div><div>I compared the 5 implementations for correctness and<br>
(naively) for speed.<br><br></div>
<div>4 out of 5 where correct (variation in example 2 tolerated)<br><pre><span style="font-family:'courier new',monospace"><code>roland_spec.rb => correct<br>
michael_spec.rb => not correct<br>peter_spec.rb => correct<br>tom_spec.rb => correct<br>dominic_spec.rb => correct</code></span><br></pre></div>Time to run rspec for a haystack of ("hello world" * 100)<br>
</div><div>(of course the tests "failed", the results where quite<br>massive for the last test with three letters in the pattern).<br></div><div><pre><span style="font-family:'courier new',monospace"><code>roland_spec.rb => 9.14 s
michael_spec.rb => 0.0087 s (incorrect result)
peter_spec.rb => 5.91 s
tom_spec.rb => 20.05 s
dominic_spec.rb => DNF (with the 100 multiplier)</code></span></pre>(dominic's version showed an interesting growth curve of<br></div><div>consumed time with the multipler for the haystack).<br><br></div>The long version of the tests:<br>
<br> <a href="https://gist.github.com/petervandenabeele/7161464" target="_blank">https://gist.github.com/petervandenabeele/7161464</a><span><font color="#888888"><br><br></font></span></div><span><font color="#888888">Peter<br>
</font></span><div class="gmail_extra"><br></div><div class="gmail_extra">PS. Yes, I know I should use Benchmark and warm-up, but hey,<br>
it's weekend ...<br><br></div><div><div><div class="gmail_extra"><div class="gmail_quote">On Fri, Oct 25, 2013 at 10:19 PM, Dominic Baggott <span dir="ltr"><<a href="mailto:dominic.baggott@gmail.com" target="_blank">dominic.baggott@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Here's a recursive version, using Roland's tests (with an amended example 2): <a href="https://gist.github.com/evilstreak/7161191" target="_blank">https://gist.github.com/evilstreak/7161191</a><br>
<br>
Dom<br>
<div><div><br>
<br>
On Friday, 25 October 2013 at 14:21, Andrew Stewart wrote:<br>
<br>
> Hello El Rug,<br>
><br>
> Given two strings a and b, I would like to find all the occasions where the letters of b appear in the same order in a. The result should be an array of arrays where each inner array contains the indices of b's matches in a.<br>
><br>
> a: 'hello world'<br>
> b: 'e'<br>
> result: [ [1] ]<br>
><br>
> a: 'hello world'<br>
> b: 'l'<br>
> result: [ [2,3,9] ]<br>
><br>
> a: 'hello world'<br>
> b: 'el'<br>
> result: [ [1,2], [1,3], [1,9] ]<br>
><br>
> a: 'hello world'<br>
> b: 'lo'<br>
> result: [ [2,4], [2,7], [3,4], [3,7] ]<br>
><br>
> a: 'hello world'<br>
> b: 'lod'<br>
> result: [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]<br>
><br>
> Hope that makes sense ;)<br>
><br>
> I've been trying this for ages, with iteration and recursion, and I keep getting close...but not quite there.<br>
><br>
> Any takers?<br>
><br>
> Cheers,<br>
> Andy Stewart</div></div></blockquote></div></div></div></div></div>
</blockquote></div><br><br clear="all"><br></div></div><span><font color="#888888">-- <br>Peter Vandenabeele<br><a href="http://www.linkedin.com/in/petervandenabeele" target="_blank">http://www.linkedin.com/in/petervandenabeele</a><br>
<a href="https://github.com/petervandenabeele" target="_blank">https://github.com/petervandenabeele</a><br>
<a href="https://twitter.com/peter_v" target="_blank">https://twitter.com/peter_v</a><br>gsm: <a href="tel:%2B32-478-27.40.69" value="+32478274069" target="_blank">+32-478-27.40.69</a><br>e-mail: <a href="mailto:peter@vandenabeele.com" target="_blank">peter@vandenabeele.com</a><br>
skype: peter_v_be
</font></span></div>
<br>_______________________________________________<br>
Chat mailing list<br>
<a href="mailto:Chat@lists.lrug.org" target="_blank">Chat@lists.lrug.org</a><br>
<a href="http://lists.lrug.org/listinfo.cgi/chat-lrug.org" target="_blank">http://lists.lrug.org/listinfo.cgi/chat-lrug.org</a><br>
<br></div><br></div>