Re: performance // Re: Re: Why is recursion so

*To*: mathgroup at smc.vnet.net*Subject*: [mg100602] Re: [mg100559] performance // Re: [mg100548] Re: Why is recursion so*From*: DrMajorBob <btreat1 at austin.rr.com>*Date*: Tue, 9 Jun 2009 03:54:30 -0400 (EDT)*References*: <h0d6s8$spq$1@smc.vnet.net> <200906070903.FAA28180@smc.vnet.net>*Reply-to*: drmajorbob at bigfoot.com

The performance hit is miniscule. Even if x could take on millions of values in f["x"][y], table lookup time for the strings is log-linear in the number of strings, I think. Bobby On Mon, 08 Jun 2009 01:05:23 -0500, Scot T. Martin <smartin at seas.harvard.edu> wrote: > On the general topic of performance, I'd be interested to know if anyone > can comment on the following. In an effort to keep my codes as reasonable > as possible, I use a lot of "sentence variables". What I mean is that > I'll > write: > > myfunction["further explanation"][var1_,var2_]:= .... > > I add that extra string in naming the function. This helps me immensely > to > remember what I'm doing and make my code accessible to me again in six > months. I have often wondered, however, if I slow down Mathematica by > using these long function names. > > Does anyone know? > > [For most of my applications, the limiting aspect on overall > implementation time is my slow human CPU, so I have ample computer cycles > and memory. However, there are a few applications that cause me to leave > my computer running overnight, so I'm wondering somewhat about the > performance of the code and if these long variable names are having an > effect.] > > > > > On Sun, 7 Jun 2009, lshifr at gmail.com wrote: > >> Daniel, >> >> Let me tell you straight away that you won't get efficiency of OCaml >> in Mathematica, >> the latter really being a CAS, research and prototyping tool, but not >> an efficiency-oriented production language. >> >> Regarding your question, the short answer is that recursion is slow >> because lists are implemented as arrays in Mathematica. When you >> pattern-match, the whole array <tail> is copied every time. This >> explains both the slowdown - the time becomes effectively quadratic >> (assuming that the complexity of array copying is linear), and the >> (stack) memory use explosion. >> >> So, IMO, indeed Mathematica is unfortunately less suited for the >> straightforward recursive solutions like yours. The closest thing you >> can probably do to stay in the recursive mindset is to use linked >> lists. Here is an implementation that does just that: >> >> Clear[myselectAux]; >> myselectAux[{}, predicate_] = {}; >> myselectAux[{head_, tail_List}, predicate_] := >> If[predicate[head], {head, myselectAux[tail, predicate]}, >> myselectAux[tail, predicate]]; >> >> Clear[toLinkedList]; >> toLinkedList[x_List] := Fold[{#2, #1} &, {}, Reverse[x]]; >> >> Clear[mySelectLL]; >> mySelectLL[x_List, predicate_] := >> Flatten@myselectAux[toLinkedList[x], predicate]; >> >> You can find more info on linked lists in Mathematica in the book of >> David Wagner, >> in the notes by Daniel Lichtblau (see Wolfram library archive, should >> be named >> something like "efficient data structures in Mathematica"), and also >> in my book >> (http://www.mathprogramming-intro.org/book/node525.html). >> >> For example: >> >> In[1] = test = RandomInteger[{1, 10}, 10] >> >> Out[1] = {6, 10, 1, 9, 4, 6, 1, 9, 10, 4} >> >> In[2] = toLinkedList@test >> >> Out[2] = {6, {10, {1, {9, {4, {6, {1, {9, {10, {4, {}}}}}}}}}}} >> >> In[3] = mySelectLL[test, # > 5 &] >> >> Out[3] = {6, 10, 9, 6, 9, 10} >> >> Now, the benchmarks: I use yours, on my 5 years old 1.8 GHz P IV, and >> I get: >> >> In[4] = >> data = Table[Random[], {20000}]; >> Block[{$RecursionLimit = Infinity}, >> Timing[data2 = mySelectLL[data, # > 0.5 &];]] >> >> Out[4] = {0.2, Null} >> >> Now, this is not the most efficient implementation. David Wagner in >> his excellent book >> discussed in great detail this sort of problems with the mergesort >> algorithm as an archetypal example. I believe that you can squeeze >> another factor of 2-5 by further optimizing the implementation >> (keeping it recursive) with several performance-tuning techniques >> available in Mathematica. >> >> By the way, I tested the above code with larger lists and it seems to >> continue be linear complexity up to 100 000 elements, but the kernel >> (v.6) just crashes after that - this >> behavior I can not explain, since the memory usage seems quite decent. >> >> So, to summarize my opinion: if you prefer to stay in a recursive >> mode, you *can* use recursion in Mathematica rather efficiently by >> switching to linked lists (and this will require some extra work but >> not so much of it). This may be enough to move you from the domain of >> toy problems to that of reasonably complex prototypes. But don't >> expect efficiency of the highly optimized production language with a >> native-code compiler (or even byte code interpreter) from a rewrite >> system such as Mathematica. Also, I'd say that other programming >> styles such as structural operations (APL - like) will bring you >> closer to efficiency of Ocaml etc. since then you can leverage the >> highly-optimized vectorized operations built in Mathematica. >> >> Hope this helps. >> >> Regards, >> Leonid >> >> >> >> >> >> >> >> >> On Jun 6, 12:46 am, Daniel <jan... at gmail.com> 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) :: randlis= >> t >>> (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 Mathematic= >> a >>> *) >> >> >> > -- DrMajorBob at bigfoot.com

**References**:**Re: Why is recursion so slow in Mathematica?***From:*lshifr@gmail.com