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
