Re: Re: Particular structure 2
- To: mathgroup at smc.vnet.net
- Subject: [mg33683] Re: Re: Particular structure 2
- From: "Allan Hayes" <hay at haystack.demon.co.uk>
- Date: Sat, 6 Apr 2002 00:49:03 -0500 (EST)
- References: <a8itdk$gca$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Dear Hartmut,
> I was let to ponder for a while why you held F in the Map over x. Without
> knowing more details of the problem, a "best solution" can hardly be
> proposed. Of course there might be cases where the evaluation of F might
go
> astray unless the values y[[i]] are inserted. But normally, in the
interest
> of memory consumption and performance (partial) evaluation should be done
as
> early as possible.
It looks as if this was a mistake. Some experiments, and your observations
below, indicate that the speed penalty is usually very high in return for a
small reduction in memory use.
Your use of Thread, (7) below, seems the best approach for this problem.
The guidelines would appear to be the closely related and standard ones
1) avoid repetition of a computation
2) get a formula if this is possible economically.
One small point: since Plus is Listable Thread is not in fact used for this
choice of functions.
With regard to your query about why in the following, (4) is slower than
(3).
I think it is because in (3), for each assignment to i in the Table, y[[i]]
is evaluated once, whereas for (4) is is evaluated 400 times.
> (3) The mapping over x (and evaluation of g) certainly should be done
> outside of the "inner loop" so to say. So this must be much slower:
>
> In[2]:=
> MemoryInUse[]
>
> Plus@@Table[Function[yy,g[f[#,yy,z]&/@x]][y[[i]]],{i,Length[y]}]//Timing
>
> MaxMemoryUsed[]
>
>
>
> Out[2]= 1274624
>
> Out[3]= {8.663 Second, =dito=}
>
> Out[4]= 1350856
>
>
> (4) However I was astonished about this being even slower:
>
> In[2]:=
> MemoryInUse[]
>
> Plus@@Table[g[f[#,y[[i]],z]&/@x],{i,Length[y]}]//Timing
>
> MaxMemoryUsed[]
>
>
>
> Out[2]= 1274256
>
> Out[3]= {14.792 Second, =dito=}
>
> Out[4]= 1350856
>
> Have you got an idea why?
--
Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565
"Wolf, Hartmut" <Hartmut.Wolf at t-systems.com> wrote in message
news:a8itdk$gca$1 at smc.vnet.net...
>
> Dear Allan,
>
> I was let to ponder for a while why you held F in the Map over x. Without
> knowing more details of the problem, a "best solution" can hardly be
> proposed. Of course there might be cases where the evaluation of F might
go
> astray unless the values y[[i]] are inserted. But normally, in the
interest
> of memory consumption and performance (partial) evaluation should be done
as
> early as possible.
>
>
> Here are some of my observations:
>
> (1) reproducing your case above
>
> In[1]:=
> x = y = Table[1, {400}]; f = Plus; g = Times @@ # &; z = 1;
>
> In[2]:=
> MemoryInUse[]
>
> Plus @@ Table[Function[yy, ReleaseHold[#]][y[[i]]], {i, Length[y]}] &[
> Hold[g][f[#, yy, z] & /@ x]] // Timing
>
> MaxMemoryUsed[]
>
>
> Out[2]= 1275144
> Out[3]= {3.726 Second, \
>
2822031643462133028498570863037391848660317984511492630514848928370483422063
> 31\
>
7366263171941177885366326198093393014236474677191722872982667765803378181410
> 28\
> 11184114129504125276977313333635200400}
> Out[4]= 1358768
> In[5]:= Quit[]
>
> (I finally applied Plus just to check for check for correctness)
>
>
>
> (2) same with F (called g here) not held:
>
> Allan Hayes (not held)
>
> In[2]:=
> MemoryInUse[]
>
>
Plus@@Table[Function[yy,#][y[[i]]],{i,Length[y]}]&[g[f[#,yy,z]&/@x]]//Timing
>
> MaxMemoryUsed[]
>
>
>
> Out[2]= 1274896
>
> Out[3]= {0.261 Second, =dito= }
>
> Out[4]= 1350856
>
> This is very fast (a little bit surprisingly to me).
>
>
> (3) The mapping over x (and evaluation of g) certainly should be done
> outside of the "inner loop" so to say. So this must be much slower:
>
> In[2]:=
> MemoryInUse[]
>
> Plus@@Table[Function[yy,g[f[#,yy,z]&/@x]][y[[i]]],{i,Length[y]}]//Timing
>
> MaxMemoryUsed[]
>
>
>
> Out[2]= 1274624
>
> Out[3]= {8.663 Second, =dito=}
>
> Out[4]= 1350856
>
>
> (4) However I was astonished about this being even slower:
>
> In[2]:=
> MemoryInUse[]
>
> Plus@@Table[g[f[#,y[[i]],z]&/@x],{i,Length[y]}]//Timing
>
> MaxMemoryUsed[]
>
>
>
> Out[2]= 1274256
>
> Out[3]= {14.792 Second, =dito=}
>
> Out[4]= 1350856
>
> Have you got an idea why?
>
>
> (5) A natural idea would be to use nested Maps:
>
> In[2]:=
> MemoryInUse[]
>
> (Plus @@ Map[Function[{y}, g[Map[Function[{x}, f[x, y, z]], x]]],
> y]) // Timing
>
> MaxMemoryUsed[]
>
>
> Out[2]= 1274736
> Out[3]= {12.248 Second, =dito= }
> Out[4]= 1358512
>
> While this is economic on memory, performance is bad (on grounds stated
> above).
>
>
> (6) Evaluating the body of the Function definition improves that
> considerably:
>
> In[2]:=
> MemoryInUse[]
>
> Plus @@ Map[Function[{yy}, Evaluate[g[Map[Function[{x}, f[x, yy, z]],
x]]]],
>
> y] // Timing
>
> MaxMemoryUsed[]
>
> Out[2]= 1274600
> Out[3]= {0.241 Second, =dito= }
> Out[4]= 1350856
>
>
> (7) The best result I attained, however was using Thread instead of the
> inner Map:
>
> In[2]:=
> MemoryInUse[]
>
> Plus @@ (Evaluate[g[Thread[f[x, #, z]]]] &) /@ y // Timing
>
> MaxMemoryUsed[]
>
>
> Out[2]= 1274040
> Out[3]= {0.181 Second, =dito= }
> Out[4]= 1350856
>
>
> yours, Hartmut
>
>