Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

understand and prevent 'Out of memory!' during sub recursion

by Discipulus (Monsignor)
on Nov 09, 2017 at 09:53 UTC ( #1203005=perlquestion: print w/replies, xml ) Need Help??
Discipulus has asked for the wisdom of the Perl Monks concerning the following question:

Hello monks and nuns!

This is more an itch than a problem: yesterday in CB came out a little simple quiz reported by 1nickt (who obviously knows many different solutions to the quiz). The problem sounded like: write a sub that receives arrays of strings and print them interleaved. I added the constraint that print order had to be not just mixed but the first element of each array, then the second etc..

obviously there are many, simple, ways to accomplish this with or without core modules. First thing that i supposed was to spot the max length of received arrays and build a loop (and this approach works ok).

But and here the itch, after a while i started mumbling about shift to death arrays skipping the max length computing and I ended with:

# DO NOT RUN THIS!! perl -e "sub inter{map {print shift @$_} @_; &inter} inter([1],[1,2],[ +1,2,3],[1,2,3,4,5])" # OUT Out of memory! 11112223345

Which unfortunately, while printing the correct result, bring to an undesired Out of memory!

Now I understand that it goes out of memory because nothing stops the recursion, so i tried to break it but with no luck: inserting in the top of the sub exit unless $_[0][0] just prints first elements of each array and exits, &inter if $_[0][0] at the end does the same.

Some insight?

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

Replies are listed 'Best First'.
Re: understand and prevent 'Out of memory!' during sub recursion
by choroba (Bishop) on Nov 09, 2017 at 10:12 UTC
    You usually need to tell the function when it should stop recursing. In this case, you can do
    &inter if grep @$_, @_

    You can also use the tail recursion goto &inter here, as there's nothing happening after returning from the recursion.

    ($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord }map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
      thanks choroba,

      but why &inter if $_[0][0] does not act the same of your, working, &inter if grep @$_, @_ ?

      Can you also expand a bit your last sentence?

      L*

      There are no rules, there are no thumbs..
      Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.
        $_[0][0] only checks the first array, i.e. it fails if the first array is not the longest one. grep, on the other hand, checks all the arrays.

        ($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord }map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
Re: understand and prevent 'Out of memory!' during sub recursion
by Eily (Prior) on Nov 09, 2017 at 10:16 UTC

    sub inter{grep {print shift @$_; @$_} @_ and &inter} inter([1],[1,2],[1,2,3],[1,2,3,4,5])
    That way you even get rid of your map in a void context :P

      Thanks Eily,

      the trick is in the and rigth? it breaks the recursion when grep return false.

      It's so bad map in void context?

      L*

      There are no rules, there are no thumbs..
      Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

        Well it doesn't explicitly break the recursion (it just doesn't recurse anymore, but in the end that's quite the same). I'd say the trick is that grep checks all elements of @_, while your test on $_[0][0] only checks the first array (which happens to be the first to be empty, you're actually lucky that this array was the smallest, with [1,2,3,4,5,6],[1,2],[1,2,3],[1,2,3,4,5] your code might have worked.

        And no, map in void context isn't so bad. It's just considered bad practice, often the reason given is that it's wasteful to build a new list (the output of map) just to throw it away, but also most of the time you can replace it by a for loop, which makes the intent clearer (map indicates that you want to transform a list, while for indicates that you want to iterate over it). map {print shift @$_} @_; for example can be translated to print shift @$_ for @_;

Re: understand and prevent 'Out of memory!' during sub recursion
by tybalt89 (Priest) on Nov 09, 2017 at 14:43 UTC

    My usual rule for recursion is to check if we are done first, then recurse.

    For this problem, it avoids "Use of uninitialized value in print..." which isn't checked for :)

    #!/usr/bin/perl # http://perlmonks.org/?node_id=1203005 use strict; use warnings; inter([1],[1,2],[1,2,3],[1,2,3,4,5]); sub inter { @_ && inter( grep { @$_ && print shift @$_ } @_ ) }
Re: understand and prevent 'Out of memory!' during sub recursion
by vr (Hermit) on Nov 09, 2017 at 15:39 UTC

    But, "deep recursion" warning would indicate the issue, no? (It sure was mentioned in CB). Monks run their one-liners with a "-w"? Then, how about this solution to stop recursion:

    >perl -Mwarnings=FATAL,recursion -e "sub inter{map {print shift @$_} @ +_; &inter} eval {inter([1],[1,2],[1,2,3],[1,2,3,4,5])}"

    (A joke. Don't do it)

Re: understand and prevent 'Out of memory!' during sub recursion
by Anonymous Monk on Nov 09, 2017 at 15:16 UTC
    This is why I almost never use "terse" code like this like map. You can't instantly tell what the code is doing, and you really don't have any way to break-out. (That's not what map is intended for.) The snake eats its own tail until it grows too fat and dies. Whereas, a very short subroutine would accomplish the same task and do so with clarity. There would be no meaningful difference in execution time. Terseness is really not your friend at all. Clarity, and maintainability, is.

      Well here Discipulus is trying to learn, so I think it's a legimate case for trying new and unusual ways. Also, "I wouldn't have done it like that" isn't very helpful when someone is asking for help correcting and understanding their mistakes.

      You can't instantly tell what the code is doing ... a very short subroutine would accomplish the same task

      Except that Discipulus is already using a very short subroutine. So you are right in that you can't tell what the code is doing because you didn't spot that. map is perfectly fine - perhaps even ideal - in this context.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1203005]
Front-paged by haukex
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (8)
As of 2018-06-22 16:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?



    Results (124 votes). Check out past polls.

    Notices?