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
- Re: Why is recursion so slow in Mathematica?