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
