There's an extra 16MB memory used above your data requirement estimate, over the 4000 recursive calls.
the head, rest pattern is very convenient and maintainable compared to a more idiomatic J-like scan solution when there is fairly involved validating, and conditional code in each pass or nested reboxing/reshaping of the results. I don't believe J implements any tail call optimizations. (not that previous sample code would meet requirements for it) for this following function, there is about a constant 170KB memory footprint per extra 100 calls: fact=: 3 : 0 if. 2>y do. 1 return. end. (* fact@<:) y ) ts 'fact 266x' 0.00376528046941 452864 fact 366x 9188111095254496019212176412065202140090580418774645194675369840967804846588863095597762591294093025991679067056119532289819154031153412626361004655299317292397491794124983183190181485863175356339673174577270709354011349841159870162315388021077551574544150... ts 'fact 366x' 0.00547991703593 627456 fact 466x 6606465428400497658851519560897979912129300524289341787535172295231497506201085472491027425799387976235561894528723105535006882791207594448037382285149149962251251898068020819230488656949853105427450687656133148065773664977601983727180722414127749650177670... ts 'fact 466x' 0.00742146104164 793856 this version takes 100kb per extra 100 calls ts '1:`(* $:@<:)@.* 466x' 0.00343851094545 446144 ts '1:`(* $:@<:)@.* 366x' 0.00234508323273 348352 ts '1:`(* $:@<:)@.* 266x' 0.00218310843002 250560 ----- Original Message ---- From: bill lam <[EMAIL PROTECTED]> To: Programming forum <[email protected]> Sent: Tuesday, May 1, 2007 10:46:11 PM Subject: Re: [Jprogramming] recursion -- was alchemy Did you also measure the memory requirement of flisp using lisp, haskell and other functional languages? To store 4000 'head' and 'rest' alone, it needs 4 * 4000 + +/ >:@:i.4000 => 32024000 bytes of memory unless the interpreter can detect and translate it into trail recursion or iteration, this is the minimum ram requirement for flisp. Do you have any idea how other functional languages can work with less memory? Pascal Jasmin wrote: > I find recursion performance in J to be poor. > > The most common recursive pattern that memoization won't help with is the > head, rest pattern that seems to form the basis of every list processing > function in lisp, haskell and other functional languages: > > f=: 3 :0 > if. 1>#y do. endofrecusionstep return. end. > 'head rest'=. ({.;}.) y > ( v1 head) v2 f rest NB. v1 and v2 are processing verbs > ) > > this type of process is slow and takes huge memory, and gives stack errors > for lists that are of surprisingly modest length (10k or less) > > flisp =: 3 : 0 > if. 1=#y do. y return. end. > 'head rest'=. ({.;}.) y > head + flisp rest > ) > > ts '+/ i.4000' > 3.26466279074e_5 17472 > ts 'flisp i.4000' > 0.340178490394 48549056 > > (,@:+/ -: flisp) i.20 > 1 > > this version surprisingly takes even more memory: > > flisp2 =: 3 : 0 > if. 1=#y do. y return. end. > ({. + flisp2@:}.) y > ) > > ts 'flisp2 i.4000' > 0.243309521814 49654720 > > > ----- Original Message ---- > From: John Randall <[EMAIL PROTECTED]> > To: Programming forum <[email protected]> > Sent: Tuesday, May 1, 2007 6:33:31 PM > Subject: Re: [Jprogramming] Moving past the alchemist stage > > Roger Hui wrote: >>> (a) Avoid recursion, unless you are memoizing the results. >> I wonder about this one. A recursion whose results >> are atoms (or involve small amounts of data) could >> be inefficient without memoization. Otherwise there >> is nothing much wrong with recursion in J. e.g. >> > > Roger: > > I take your points. In particular > > 1. I was thinking about small result size for memoization. (By the > way, is this still going to be in J6.02?) > > 2. I have nothing against tail recursion. > > 3. I was partly put off a while ago when the recursion depth was too > small: now it is OK. > > The types of problems where I have had problems concern naturally > recursive problems where each step is quite small and conditionals are > involved. In my experience, J then suffers in comparison to C-like > languages, although the problem can often be reformulated to give > excellent performance in a way it could not be in C. > > For example, suppose p(i,j,n) is a boolean function returning 1 only > if there is a path in a graph of length n from vertex i to vertex j. > This can be formulated recursively as > if n=0, p(i,j,n)=1 iff i=j > if n>0, p(i,j,n)=1 only if there exists a vertex k with > P(i,k,1)=1 and P(k,j,n-1)=1. > > Of course, in this case, we can solve the problem for all i,j by > taking the nth power of the adjacency matrix. In general it may be > hard to go from the recursive formulation to the more direct approach, > and requires replacing the depth-first search often implied by > recursion by breadth-first. > > Best wishes, > > John > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > > Ask a question on any topic and get answers from real people. Go to > Yahoo! Answers and share what you know at http://ca.answers.yahoo.com > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- regards, bill ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm Get news delivered with the All new Yahoo! Mail. Enjoy RSS feeds right on your Mail page. Start today at http://mrd.mail.yahoo.com/try_beta?.intl=ca ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
