[LRUG] Recursion diversion

[Peter Vandenabeele]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lrug.org/pipermail/chat-lrug.org/attachments/20131026/4e8dfcdf/attachment.html>