# Resampling an array of objects

### Context

I have an array of objects (or a list of dictionaries), sorted in order based on a property of each object, say, time. In JSON, it would look something like this:

[
{'details': 'some details', 'time': 69},
{'details': 'some details', 'time': 79},
{'details': 'some details', 'time': 107},
{'details': 'some details', 'time': 339},
{'details': 'some details', 'time': 339},
{'details': 'some details', 'time': 344},
...
]

Each entry represents the state of my program at a certain point in time. The entries are in order, but are not spaced evenly across time. A nice visual along a numberline representing time might look like this:

So we have a series of objects called snapshots ($$S_n$$) along a timeline, whose time values place them unevenly across time.

### The goal

I want to resample these snapshot objects such that I produce a new array of snapshot objects, but spaced evenly across time. A quick visual would look like this:

Here you can see a resampled timeline, where resampled snapshots $$R$$ correspond to the latest available snapshot $$S$$ that has occured at or before a time corresponding to $$R_n$$. By definition, $$R_0$$ is always set to be the same as $$S_0$$, as it is the starting point for both unevenly and evenly snapshots.

### Thinking through some details

There are two cases we need to account for - (1) when there are more than 1 $$S$$ between $$R$$s, and (2) when there are no new $$S$$s between $$R$$s. The following image demonstates both scenarios:

We see that for $$R_1$$, several $$S$$s have passed, so we skip all but the most recent relative to $$R_1$$, and $$R_1$$'s sample returns $$S_2$$ (scenario 1). For $$R_2$$, no new $$S$$s have occurred, so the state of the application based on the information we have is still at $$S_2$$, and $$R_2$$ samples at $$S_2$$ as well (scenario 2). Perhaps this is already obvious from the above description.

### Writing a function?

I have been thinking about this for some time, and I have been trying to bang out a function to perform this sampling given an array of snapshots $$A_S$$ and a sampling interval $$I$$. I would like to make it as efficient as possible. My thoughts were to make a copy of $$A_S$$ (so as not to mutate the original) called $$C_S$$, and then begin popping snapshots from the front of $$C_S$$. This way, for every $$R$$ we establish, we continue working from what remains of $$C_S$$, thus reducing the number of iterations we have to make through the original snapshots and increasing the efficiency of the algorithm.

I am struggling to come up with such a function, and given what a simple concept this is, I wonder if it already exists somewhere? I need to implement this in TypeScript/Javascript, but a solution in python or pseudocode would also be very helpful, or even a link to "hey, this is a common problem that is already described / solved."

Let $$A_s[1,\cdots,m]$$ be an array of $$m$$ samples, where say $$A_s[i].\text{time}$$ gives us the time sample $$i$$ was taken at, and where we assume the items are sorted in ascending order of the time they were taken. Define $$I \in \mathbb{R}$$ as the time interval value to space new samples, and define $$T_f$$ as a final time where you do not want any equal spaced samples after this time. Given your description, your algorithm could be represented in the following way:

• On input $$(A_s, I, T_f)$$:
1. Init $$R = []$$ as an empty list of new samples
2. Set $$t = A_s[1].\text{time}$$ as the initial time
3. Set $$i=1$$
4. $$\text{while}(t \leq T_f)$$
1. $$\text{while}(i < m \text{ and } A_s[i+1].\text{time} \leq t )$$
1. Update $$i \leftarrow i + 1$$
2. $$R.\text{append}(A_s[i])$$
3. Update $$t \leftarrow t + I$$
5. $$\text{return}$$ $$R$$

Now after we work past $$A_s[k]$$ for some $$k$$, we never see it again. Given the array uses some doubling strategy when it resizes (which is common), then appending a new piece of data to $$R$$ is an operation proportional to the size of the dictionaries, call this $$B$$. This implies that the runtime of our algorithm is $$O\left(m + \left(\frac{T_f - t_{1}}{I}\right)B\right)$$, where $$t_1 = A_s[1].\text{time}$$. This should satisfy the efficiency criteria mentioned in the problem statement. If one was working in a language with pointers, one could store pointers to the dictionaries in $$R$$ and remove the factor of $$B$$ overhead in the runtime and replace it with a constant.

• Thank you! In the week between my posting the Q and your answer, I ended up with a function very similar in flow to this. The crucial part is the nested loop in step 4. I appreciate your analysis of $O$, it may take me a bit of time to digest that. Thank you! Sep 25 '21 at 1:02