Isn't v2/ @: |. @: (v1"_1)
equivalent to your f? Henry Rich > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Pascal Jasmin > Sent: Tuesday, May 01, 2007 10:06 PM > To: Programming forum > Subject: Re: [Jprogramming] recursion -- was alchemy > > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
