Re: Re: Particular structure 2
- To: mathgroup at smc.vnet.net
- Subject: [mg33713] Re: [mg33627] Re: Particular structure 2
- From: Yas <yast at optushome.com.au>
- Date: Mon, 8 Apr 2002 03:04:52 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Dear Allan and Hartmut,
Thank you very much for your replies to my questions and the solutions
you have provided. As has been pointed out, a best solution is hardly
feasible without further details on the problem. The last reply from
Allan ([mg33656]) containing the construct;
x= y=Table[1,{400}];f=Plus;F= Times;
Table[ReleaseHold[F@@#],{j, Length[y]}]&[
Table[f[x[[i]],Hold[y[[j]]],z],{i,Length[x]}]];//Timing
is again another factor of two improvement in terms of speed but
slightly less efficient than Hartmut Wolfs Case 6 (mg33657),
Plus @@ Map[Function[{yy}, Evaluate[F[Map[Function[{x}, f[x, yy, z]],
x]]]], y] // Timing
in terms of memory use.
I was particularly encouraged by the speed of Thread, but unfortunately
the structure of the resulting matrix gets jumbled up. I couldn't see a
way around it. Transpose restructures it in a way where the 3x3 and 6x6
relations get messed up.
In my problem (the simplest case) f is the equivalent of a 3x3 matrix
and is defined as, evalmat[x_,y_,z_] = mat[x, y, z], and mat has been
built up from matrix elements containing functions depending on x, y and
z. For fixed values of y and z and with x, a list of 500 or more
elements, I use Fold or FoldList to construct a final vector or a list
of vectors. So the new vector, newvec = Fold[#2.#1&, vec, g1], where vec
={0,0,1} usually, and g1 is a list built by mapping x onto evalmat (g1 =
evalmat[#, y, z]&/@x). Incidentally I found using Outer to be slightly
quicker for mapping x onto evalmat with y held fixed which has had me
stumped as to why.
For the same list of x values and with y now variable as well my
natural inclination was to create a large array of g1's with
incrementing y which can be done by adapting either of the two
constructs above,
e.g. g1= Map[Function[{yy}, Evaluate[Map[Function[{x}, evalmat[x, yy,
z]], x]]], y]
or g1 = Table[ReleaseHold[#],{j, Length[y]}]&[
Table[evalmat[x[[i]],Hold[y[[j]]],z],{i,Length[x]}]];
The building and evaluation of g1 is the slowest part if y is variable
as well, and for sufficient resolution where any spurious jumps are
avoided the number of increments of y has to be large, usually > 256
points. But once g1 is built, and because the Fold part is fast the
construct below is not limiting.
profile = Table[Fold[#2.#1&, vec, g1[[k]]], {k, Length[y]}];
The elements of the vector can be extracted and plotted.
Now that all this has been achieved, I immediately applied it to a
larger matrix (6x6) only to find that I am back to square one in terms
of time and memory. In the 3x3 case all the matrix elements have set
delayed assignment and the functions inside the elements of the matrix
also have delayed assignment. The matrix mat is also delayed but I
figure using evalmat, rather than mat overcomes re-evaluation for each
new x, y or z. Replacing := with = for the matrix element definitions
and mat so that they are evaluated immediately did not seem to make a
difference to the evaluation times, so what else can be done to improve
the time for evaluation.
Regards
Yas
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
>