1
$\begingroup$

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:

enter image description here

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:

enter image description here

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:

enter image description here

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."

$\endgroup$
3
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Sep 25 at 1:02

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.