1
$\begingroup$

I have dealing a lot recently with the built-in function FoldList. I use it to solve a stochastic differential equation (SDE) in forward manner. My equation contains long-time memory, which is why FoldList needs to invoke a long list of values as input in order to compute the subsequent value (or rather list). Depending on the number of total steps I use in my program this can be very memory consuming which turns out to be a problem as I need to solve the equation for long times, unfortunately.

In principle, what I need from FoldList is only the final list of values after the last time step. The previous lists are only used as an input to compute the next value which is then appended to the previous list (while dropping the first value of this list such that the length remains constant).

Of course, FoldList gives me as an output not only the final list, but all the lists which where previously used as an input.

My question therefore is: Is there any way to dismiss these previous lists in order to save memory? I don't know whether this is feasible since I need the previous lists as input in FoldList to compute the next value. Any other ideas suggestions how to save memory are highly appreciated.

Thank you very much!

[Edit]

Sorry I was a little bit misled. I do not need the last list of FoldList, but always the last value of all the lists (including the last list and previous ones). Fold works fine and gives me the last list, but the length of my list is restricted by the time of memory I consider. So I could use Fold but then the length of this list needs to be as long as the number of lists I used in FoldList. Probably this slows it down very much.

[Edit2]

Minimum working example:

nMem=5;
nTot=10;  

FoldList[{#2,Drop[Append[{#1[[2]]}, Last[#1[[2]]] + 5] // Flatten,1]} &, {0, {ConstantArray[0, nMem]} // Flatten}, Range[1, nTot]]

which gives as an output:

{{0, {0, 0, 0, 0, 0}}, {1, {0, 0, 0, 0, 5}}, {2, {0, 0, 0, 5, 
   10}}, {3, {0, 0, 5, 10, 15}}, {4, {0, 5, 10, 15, 20}}, {5, {5, 10, 
   15, 20, 25}}, {6, {10, 15, 20, 25, 30}}, {7, {15, 20, 25, 30, 
   35}}, {8, {20, 25, 30, 35, 40}}, {9, {25, 30, 35, 40, 
   45}}, {10, {30, 35, 40, 45, 50}}}

number of time step is stored as 1,2,3,4,... (in principle not necessary). New value is computed and appended to the list while dropping the first value of the previous list.

The Range[1, nTot] is desirable because when computing the new value I need to call a list with listNoise[[#2]].

Length of the sublist (here 5 elements) defines nMem. Number of sublists (here 10) defines nTot.

This eats up all my memory when I increase nMem and nTot to large values. In the end I collect only the last values from each sublist (i.e., here {5,10,15,20,...}).

How can this be done more efficiently memory-wise? Maybe you even have some advice on how to improve the performance.

I tried the suggestion with Fold but it seems to be too bad on the performance side since in this case I need to set nMem=nTot.

[Edit3]

New try of a minimum working example to illustrate my intention:

nMem = 5;
nTot = 10;

listnoise = RandomInteger[5, nTot];
listmem = Range[nMem];

FoldList[{#2, 
   Drop[Append[{#1[[2]]}, 
      Last[#1[[2]]] + listmem.#1[[2]] + listnoise[[#2]]] // Flatten, 
    1]} &, {0, {ConstantArray[0, nMem]} // Flatten}, Range[1, nTot]]
$\endgroup$
  • $\begingroup$ Have you seen Fold? $\endgroup$ – Sascha May 24 '17 at 8:47
  • $\begingroup$ No, I wasn't aware of Fold. Does this really save me the day in terms of memory? Because I am afraid that internally also Fold needs to store these intermediate lists somewhere, which would make my problem of memory consumption unsolvable. I am just wondering whether my huge memory consumption is because of the length of the final list or because of the internal mechanism of FoldList itself. It appears that already while FoldList is being evaluated the memory consumption heavily increases. So I don't know whether Fold makes any difference. But it is worth a try for sure! $\endgroup$ – Display Name May 24 '17 at 8:52
  • $\begingroup$ And I also wonder whether in my case I can simply replace FoldList with Fold since I definitely need the previous list to compute the next list after one time step. Are these previous lists still available (or rather accessible) in Fold as it is the case in FoldList? Because if not it would kill the idea of my program unfortunately. In FoldList I simply call them via #1[[2]]. $\endgroup$ – Display Name May 24 '17 at 8:56
  • $\begingroup$ Sorry I was a little bit misled. I do not need the last list of FoldList, but always the last value of all the lists (including the last list and previous ones). Fold works fine and gives me the last list, but the length of my list is restricted by the time of memory I consider. So I could use Fold but then the length of this list needs to be as long as the number of lists I used in FoldList. Probably this slows it down very much. $\endgroup$ – Display Name May 24 '17 at 9:11
  • $\begingroup$ Yeah, then it is way to slow when I use Fold. Each computation steps needs then much more time (since the memory list I fold in has to be much larger). This is a pity, as it seems to be a trade-off between memory saving (Fold) and speed (FoldList) in my case. What I can try to this is to restrict the list I fold in with Fold only to number of memory I need. I wonder whether this speeds it up again. $\endgroup$ – Display Name May 24 '17 at 9:24
1
$\begingroup$

First attempt

I think we may need a concrete example to understand your needs and the performance you are experiencing. I think you are describing something like this:

FoldList[# + RotateRight[#, #2] &, Range@5, {3, 1, 5, 2}]

Last /@ %
{{1, 2, 3, 4, 5}, {4, 6, 8, 5, 7}, {11, 10, 14, 13, 12},
 {22, 20, 28, 26, 24}, {48, 44, 50, 46, 52}}

{5, 7, 12, 24, 52}

Where {5, 7, 12, 24, 52} is the output that you require. If this is fairly representative of what you are doing then perhaps use:

x = Range[5];

FoldList[Last[x = x + RotateRight[x, #2]] &, Last @ x, {3, 1, 5, 2}]
{5, 7, 12, 24, 52}

Or:

x = Range[5];

Prepend[
 Last[x = x + RotateRight[x, #]] & /@ {3, 1, 5, 2},
 Last @ x
]
{5, 7, 12, 24, 52}

Reply to Edit2

I find the example given in Edit2 confusing. First you don't actually need the element over which you fold as you write: "number of time step is stored as 1,2,3,4,... (in principle not necessary)." Second you are appending to a list that is not actually used in the following step of computation. I don't know if it is implied that in actuality it is used or not. The operation itself amounts to nothing more than:

NestList[# + 5 &, 0, 10]
{0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50}

If you need the previous n results at each step of your actual computation then manually assigning these to a Symbol like x as I did above should be practical.

Another approach is to replace FoldList with Fold and Sow only those results that you need at the end. So something like:

Reap[
  Fold[
    Append[Rest@#, Sow[Last@# + 5]] &,
    ConstantArray[0, 5],
    Range@10
  ]
][[2, 1]]
{5, 10, 15, 20, 25, 30, 35, 40, 45, 50}

This might be easier to apply in your actual computation, whatever it is.

Examples for Edit3

The Sow and Reap method mentioned last above applied to your example in Edit3:

Reap[
  Fold[
    Append[Rest@#, Sow[Last[#] + listmem.# + #2]] &,
    ConstantArray[0, nMem],
    listnoise
  ]
][[2, 1]]
{5, 31, 206, 1379, 9201, 61411, 409851, 2735319, 18255333, 121834850}

The manual assignment to x:

x = ConstantArray[0, nMem];

FoldList[
  Last[x = Append[Rest@x, # + listmem.x + #2]] &,
  0,
  listnoise
]
{0, 5, 31, 206, 1379, 9201, 61411, 409851, 2735319, 18255333, 121834850}
$\endgroup$
  • $\begingroup$ Yes, in principle that's what the program needs to do. However, I need to invoke a noise term. So far I solved it by pre-computing the noise in a list and then fold in that list via the second slot of FoldList, i.e. something like listNoise[[#2]] appears within FoldList. This means I need the second slot in FoldList to go from 1 to nTot via Range[1,nTot], where nTot is the number of time steps. Now, in your solution both slots are already occupied. This seems to be a problem. $\endgroup$ – Display Name May 24 '17 at 12:19
  • $\begingroup$ @DisplayName I'm sorry but I don't seem be to able to follow your description. I gave an example with FoldList where both slots are used normally, and then two methods that give the same result without accumulating lists at every step. I don't see why these methods cannot be applied to your case as well. I hope you will add a minimum working example to your question. $\endgroup$ – Mr.Wizard May 24 '17 at 12:24
  • $\begingroup$ Sorry, I should have been given a minimum working example from the very beginning. See my edit in the OP please. And I was wrong, my intention is slightly different compared to your suggestion. $\endgroup$ – Display Name May 24 '17 at 12:27
  • $\begingroup$ Please see my latest Edit3. This should be now more accurate to illustrate my intention. Hope I could resolve your confusion and the two points you mentioned at the beginning of your reply to Edit2. $\endgroup$ – Display Name May 24 '17 at 13:31
  • $\begingroup$ @DisplayName I applied the proposed methods to your example in Edit3. $\endgroup$ – Mr.Wizard May 24 '17 at 14:43
0
$\begingroup$

In:

Clear[f, g]
(*FoldList*)
f[bs_, a_] := Append[bs, a^2]
FoldList[f, {1}, Range[2, 10]] // Map[Last]

(*instead of FoldList, use Fold*)
g[{cs_List, bs_List}, a_] := Module[{$bs},
  $bs = f[bs, a];
  {Append[cs, Last@$bs], $bs}]
Fold[g, {{}, {}}, Range[1, 10]] // First

Out:

{1, 4, 9, 16, 25, 36, 49, 64, 81, 100}
{1, 4, 9, 16, 25, 36, 49, 64, 81, 100}
$\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.