Efficient simulation with different path lengths

Hi, I’ve enjoyed using Julia on my first research project quite a lot, and I’m now thinking of how to set up my code for my second research project. The computational bottleneck in this project lies in performing many computationally cheap simulations; I would like to make sure that I set this up in an efficient way, so let me begin by explaining what I will need to do:

I will need to simulate N independent time-series. Each of these simulations will consist of an ex-ante unknown number of simulation steps (we repeatedly simulate the time-series from time-step i to (i+1) until some condition is met). For subsequent calculations, I will need to have access to each step of each time-series.

Q1. I assume that initialising a large array/expanding an array to fit the various time-series as they are being simulated is computationally expensive, so I guess it is better to proceed differently? Would something like a list of arrays (each list entry is 1 time series, each array contains the value of the process at the various time-points) be a good idea? Or would it be better to use a list of lists of arrays (each outer list entry is 1 time series, each inner list entry is 1 time-step, each array is the value of the process at this time-step)? Or is yet another idea better?

Q2. I will need to simulate many different combinations of processes, so in my previous project, I’ve been building small simulation blocks for different processes, patching them together as I needed them. This means that several functions (‘layers’) need to be called in sequence to simulate any given process from step i to step i+1. Is this (modulo implementation) fine, or would it be better to somehow ‘compile’ the various ‘layers’ into one function that performs the simulation from step i to step i+1 directly?

I’m curious to hear your thoughts, and of course I can clarify/elaborate where necessary!

I think you description is still too vague to really give good recommendations. Could you perhaps provide some MWE/mock-up of the actual structure of the code? It does not necessarily need to be runnable but would be nice. Bonus points if the computations have realistic characteristics.

Hi, I can certainly type out some code for this tomorrow! For now, let me break out a brief description of the algorithm to see if that conveys my intentions clearly. I’m very open to setting up the code in a way that pays off on the long run: large parts of my old code will need a massive overhaul for this project anyway, so I want to make as good use of it as possible! This is why I don’t have a good piece of code to post as MWE yet!

A typical simulation looks like this, where we have a 2-dimensional process (X,M) to keep track of. We will need to repeat the entire procedure N times.

Step 0: initial values are used, say X[0] = 0 and M[0] = 0.
Step i + 1: Function 1: Simulate X[i+1] = X[i] + Standard_normal. Function 2: M[i+1] = M[i] + 1 if X[i+1] > X[i], M[i] otherwise. When N[i+1] = 10, stop simulating this path.

Effectively, we are simulating a 1-dimensional random walk with gaussian steps, where we track the number of up-steps and stop after stepping up 10 times. As the number of steps taken before reaching 10 up-steps can be arbitrarily large, I foresee problems in initializing an 3-dimensional array to store all my simulations in.

I’ve illustrated that in step i+1, I’m calling two different functions: in another simulation, I might simulate two random walks X and Y, and e.g. let M count how often we have seen X[i] > Y[i] so far. For ease of reference, I’ll call any such sequential calls to functions to simulate a step ‘layers’; this is what my Q2 refers to.

If necessary/preferred, I’m happy to send a more elaborate example tomorrow, but I hope it gets gist across?

For Q2: Composing functions from simpler pieces sounds fine, e.g, f2 ∘ f1 is essentially “compiled into one function” by the Julia compiler.

For Q1: One option might be to hook into the iterator interface, i.e., effectively making your simulation an iterator of unknown size and rely on collect being efficiently implemented for such already. There might be better options though …

Thank you for your suggestions!

For Q1, I didn’t think of setting it up as an iterator yet, this may certainly work, in particular if I can run multiple simulations in parallel and fill up the iterator as it goes. If I get you correctly, you would then get an iterator (walking through simulations) over iterators (walking through steps), right?

One follow-up question: in my analysis I will then need to efficiently access the data, with the typical queries being:

  • iterating through simulations, perform some routine at a given step
  • extract step n for all simulations that have at least n steps, e.g. to perform some kind of regression.
    I think the former works nicely with an iterator, what are your thoughts on the latter?

Is a more detailed (pseudo-)code or MWE still desirable, or is the outline of my problem clear at this point?