3
$\begingroup$

I am doing a finite difference model, and need to create a list recursively. For a small list, Fold is extremely fast, but when the list becomes large enough, Fold becomes extremely slow. Here is the code:

step[x_] := If[Mod[x, 1] <= .2, -100., 0.]
min=-10;
max=10;
dx = .01;
num = IntegerPart[(max - min)/dx];

potentialEnergy=Array[step,num,{min,max-dx}];
epotential=(2-dx^2*(-45-potentialEnergy[[2;;-2]]));

Fold[Join[#1, {Times[#2, #1[[-1]]] - #1[[-2]]}] &, {0, .01}, epotential];

When I run the above code for differing dx, I obtain the following run times: \begin{array}{c|c} dx & \text{AbsoluteTiming} \\ \hline \text{.1} & .0004 \\ \hline \text{.01} & .003 \\ \hline \text{.001} & .479 \\ \hline \end{array} To put this in context with the following code

fillArray = Join[{0, .1}, ConstantArray[0., num - 2]];
ePotential = (2 - dx^2*(-45 - potentialEnergy));

Do[fillArray[[j + 2]] = ePotential[[j + 1]]*fillArray[[j + 1]]
- fillArray[[j]], {j, 1, num - 2}]

I obtain this table of run times: \begin{array}{c|c} dx & \text{AbsoluteTiming} \\ \hline \text{.1} & .001 \\ \hline \text{.01} & .010 \\ \hline \text{.001} & .110 \\ \hline \end{array}

This second table of run times does not have the huge jump between dx=.01 and dx=.001 like the first table. Thus, my question is, why is there such a large jump and how can it be avoided?

$\endgroup$
  • 5
    $\begingroup$ Join copies the entire list to join a single element. Applied many times, it leads to a quadratic complexity in the size of the constructed list. This is the same as with Append(To) - and Fold per se has nothing to do with this. Use other means to construct a list element-by-element, there are plenty of discussions on this topic on the site. $\endgroup$ – Leonid Shifrin Dec 9 '15 at 9:43
1
$\begingroup$

On my PC, the code in the question executes in about 1.3 seconds for dx = .001, measured using AbsoluteTiming. Consider as an alternative,

Join[{0}, Cases[FoldList[{#1[[-1]], Times[#2, #1[[-1]]] - #1[[-2]]} &, 
    {0, .01}, epotential], {_, z_} -> z]];

which executes in about 0.07 seconds. Results are identical.

Addendum

Slightly faster is another alternative.

Join[{0}, FoldList[{#1[[-1]], Times[#2, #1[[-1]]] - #1[[-2]]} &, 
    {0, .01}, epotential] // Transpose // Last];
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.