Re: Why is recursion so slow in Mathematica?

*To*: mathgroup at smc.vnet.net*Subject*: [mg100550] Re: Why is recursion so slow in Mathematica?*From*: David Bailey <dave at removedbailey.co.uk>*Date*: Mon, 8 Jun 2009 02:03:45 -0400 (EDT)*References*: <h0d6s8$spq$1@smc.vnet.net>

Daniel wrote: > This post is about functional programming in Mathematica versus other > functional languages such as OCaml, SML or Haskell. At least a naive > use of functional constructs in Mathematica is horrendously slow. Am I > doing something wrong? Or isn't Mathematica really suitable for > functional programming beyond toy programs? Couldn't the Wolfram team > make a more efficient implementation for recursion, as other > functional languages has done? (Instead of the naive C-like behavior > for recursively defined functions.) > > As grounds for my question/argument, I wrote my own version of select, > as below > > myselect[{}, predicate_] = {} > myselect[{head_, tail___}, predicate_] := If[predicate[head], > Join[{head}, myselect[{tail}, predicate]], > myselect[{tail}, predicate] > ] > > Then I tried this function on a 20.000 element vector with machine > size floats: > > data = Table[Random[], {20000}]; > $RecursionLimit = 100000; > Timing[data2 = myselect[data, # > 0.5 &];] > > The result is {7.05644, Null}, and hundreds of MB of system memory are > allocated. On 1.7 GHZ dual core Intel machine with 1 GB of RAM. For > 20.000 floats! It's just a megabyte! > > The following OCaml program executes in apparently no-time. It is not > compiled and does the same thing as the above Mathematica code. After > increasing the list by a factor of ten to 200.000 elements, it still > executes in a blink. (But with 2.000.000 elements my OCaml interpreter > says Stack overflow.) > > let rec randlist n = if n=0 then [] else Random.float(1.0) :: randlist > (n-1);; > > let rec myselect = function > [],predicate -> [] > | x::xs,predicate -> if predicate(x) then x::myselect(xs,predicate) > else myselect(xs,predicate);; > > let mypred x = x>0.5;; > > let l=randlist(20000);; > let l2=myselect(l,mypred);; (* lightning-fast compared to Mathematica > *) > You can't really take a programming style that is optimised for one language and expect it to be optimal in another! Clearly, OCaml does tail recursion optimisation, and represents lists in memory, in a way that makes it easy to take the tail of a long list - perhaps lists in OCaml are represented as linked lists. However, representing a list as a linked list, has a downside. Extracting the N'th element of a long list and large N, is an expensive operation. Since lists in Mathematica are often used as vectors, a representation using linked lists would have been a BAD choice overall. David Bailey http://www.dbaileyconsultancy.co.uk