I have an array like this:
arr = [[180, 210, 240, 270, 300],[38.7, 38.4, 38.2, 37.9,37.7]]
It contains frame numbers from a video and the value of a sensor recorded during that frame.

I have a program to evaluate the video material and need to know the value of the sensor for each frame. However, the data is only recorded in these large steps not to overwhelm the sensor.

How would I go about creating a computationally cheap function, that returns the sensor value for frames which are not listed? The video is not evaluated from the first frame but some unknown offset.

The data should be filled halfway up and down to the next listed frame, e.g. Frames 195 - 225 would all use the value recorded for frame 210. The step is always constant for one video but could vary between videos.

I don't want to do a binary search through the array every time i need a value.
I also thought about filling a second array with single step in a for loop at the beginning of the program, but the array is much larger than the example above. I am worried about memory consumption and again lookup performance.

This is my try at filing the array at the beginning:

sparse_data = = [[180, 210, 240, 270, 300],[38.7, 38.4, 38.2, 37.9,37.7]]
delta = sparse_data[0][1] - sparse_data[0][0]
fr_max = sparse_data[0][-1]   delta
fr_min = sparse_data[0][0]
cur_sparse_idx = 1
self.magn_data = np.zeros(fr_max, dtype=np.float32)
    for i in range(fr_max):
        if i <= (fr_min   delta//2):
            self.magn_data[i] = sparse_data[1][0]
        elif i > fr_max: 
            self.magn_data[i] = sparse_data[1][-1]
        else:
            if (i delta//2) % delta == 0: cur_sparse_idx  = 1
            self.magn_data[i] = sparse_data[1][cur_sparse_idx]

Is there a batter way?

CodePudding user response：

Here is a O(1) solution for your problem, it allows you to find the recorded frame that is the closest to the frame you're passing in parameter, and thus the corresponding sensor value.

def get_sensor_value(frame, sparse_data):
    #Assuming the step size of frames is unique
    #Assuming frame is in the range of video
    #Assuming len(sparse_data[0]) == len(sparse_data[1])
  
    mx, mn = sparse_data[0][-1], sparse_data[0][0]
    
    return sparse_data[1][int(round((frame-mn)/(mx-mn)*(len(sparse_data[0])-1)))]

You can make it a one liner if you want to. Another solution you might consider is linear interpolation.

CodePudding user response：

You could define a query function to get the value for a specific frame as follows:

def query(frames: list[int], vals: list[float], frame: int):
    # edge cases, based on the array lengths
    assert len(frames) == len(vals)
    if len(frames) == 1:
        return vals[0]
    if len(frames) == 0:
        return ValueError()
    # arrays have at least length 2
    delta = frames[1] - frames[0]
    start = frames[0]
    end = frames[-1]
    # edge cases for the frame argument
    if frame <= start:
        return vals[0]
    if frame >= end:
        return vals[-1]
    # frame is somewhere "inside" the recorded frames
    frame -= start
    i = frame // delta
    if frame % delta > delta // 2:
        return vals[i   1]
    else:
        return vals[i]

This function uses constant time and memory. Here are some test cases based on your example, which show how you can use query:

frames, vals = [[180, 210, 240, 270, 300], [38.7, 38.4, 38.2, 37.9, 37.7]]

assert query(frames, vals, 170) == 38.7
assert query(frames, vals, 245) == 38.2
assert query(frames, vals, 196) == 38.4
assert query(frames, vals, 195) == 38.7