[LRUG] Recursion diversion

[David Nolan]

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.

Dave
@davenolan



---------- Forwarded message ----------
From: Peter Vandenabeele <peter at vandenabeele.com>
Date: 26 October 2013 08:19
Subject: Re: [LRUG] Recursion diversion
To: LRUG Users Group <chat at lists.lrug.org>


Good morning,

A sincere apology to Michael Pavling !

I had incorrectly copied his code and reported it as "not correct",
sorry for that.

When now properly copying the code and testing, it does pass
all tests correctly. I also measured the timing and added it to
the list.

Also Jason added a version that I added to the list.

I couldn't resist and made a second version (peter2), where I use a
kind of "rainbow table" to avoid recreating over and over the partial
copies of the haystack. This gives some improvement to the
speed and memory consumption, but clearly not dramatic (and
that for a lot of additional lines of code ...).

The new results are:

* s => seconds for running on "hello world" * 100
* loc => lines of code (grep -v blank lines)
* 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 ( 300 something MB ?)
jason_spec.rb   =>  16.21 s  19 loc ( 535 MB max RSIZE)
peter2_spec.rb  =>   5.24 s  42 loc ( 222 MB max RSIZE)
```

Full details on:

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

Have a good weekend,

Peter


On Fri, Oct 25, 2013 at 11:12 PM, Peter Vandenabeele <peter at vandenabeele.com
> wrote:

> I compared the 5 implementations for correctness and
> (naively) for speed.
>
> 4 out of 5 where correct (variation in example 2 tolerated)
>
> roland_spec.rb => correct
>
> michael_spec.rb => not correct
> peter_spec.rb => correct
> tom_spec.rb => correct
> dominic_spec.rb => correct
>
> Time to run rspec for a haystack of ("hello world" * 100)
> (of course the tests "failed", the results where quite
> massive for the last test with three letters in the pattern).
>
> 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)
>
> (dominic's version showed an interesting growth curve of
> consumed time with the multipler for the haystack).
>
> The long version of the tests:
>
>   https://gist.github.com/petervandenabeele/7161464
>
> Peter
>
> PS. Yes, I know I should use Benchmark and warm-up, but hey,
> it's weekend ...
>
> On Fri, Oct 25, 2013 at 10:19 PM, Dominic Baggott <
> dominic.baggott at gmail.com> wrote:
>
>> Here's a recursive version, using Roland's tests (with an amended example
>> 2): https://gist.github.com/evilstreak/7161191
>>
>> Dom
>>
>>
>> On Friday, 25 October 2013 at 14:21, Andrew Stewart wrote:
>>
>> > Hello El Rug,
>> >
>> > 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.
>> >
>> > a: 'hello world'
>> > b: 'e'
>> > result: [ [1] ]
>> >
>> > a: 'hello world'
>> > b: 'l'
>> > result: [ [2,3,9] ]
>> >
>> > a: 'hello world'
>> > b: 'el'
>> > result: [ [1,2], [1,3], [1,9] ]
>> >
>> > a: 'hello world'
>> > b: 'lo'
>> > result: [ [2,4], [2,7], [3,4], [3,7] ]
>> >
>> > a: 'hello world'
>> > b: 'lod'
>> > result: [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
>> >
>> > Hope that makes sense ;)
>> >
>> > I've been trying this for ages, with iteration and recursion, and I
>> keep getting close...but not quite there.
>> >
>> > Any takers?
>> >
>> > Cheers,
>> > Andy Stewart
>>
>


-- 
Peter Vandenabeele
http://www.linkedin.com/in/petervandenabeele
https://github.com/petervandenabeele
https://twitter.com/peter_v
gsm: +32-478-27.40.69
e-mail: peter at vandenabeele.com
skype: peter_v_be

_______________________________________________
Chat mailing list
Chat at lists.lrug.org
http://lists.lrug.org/listinfo.cgi/chat-lrug.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lrug.org/pipermail/chat-lrug.org/attachments/20131026/e27dae25/attachment.html>