[FIXED] Speed up matching between a sliding window and a list

Issue

I have an odd length window and a array and I need to find the index of the array where the window is centered and matches more. So far I am doing it with the following code. Is it possible to speed up these computations?

import numpy as np
import time

def find_best_match_position(lst, window):
    min_corr = np.inf
    best_position = -1

    for i in range(len(lst) - len(window) + 1):
        window_subset = lst[i:i + len(window)]
        corr = np.linalg.norm(window - window_subset)
        if corr < min_corr:
            min_corr = corr
            best_position = i

    return best_position


input_list_len = int(8E+6)
np.random.seed(2)
input_list = np.random.rand(input_list_len)

win_length = 31
np.random.seed(4)
window = np.random.rand(win_length)

gnd_index = 15

half_width = win_length // 2
start = gnd_index - half_width  # Shift start by 1 to the right
end = gnd_index + half_width + 1
input_list[start:end] = window + 0.01 * np.random.rand(win_length)

t = time.time()
print(f'Computed index {find_best_match_position(input_list, window) + half_width}')
t1 = time.time()
print(f'Computation time {(t1 - t) / 60} min')
# Computed index 15
# Computation time 0.6488747239112854 min

Solution

This is >10 times faster in my testing.

def find_best_match_position(lst, window):
    slides = np.lib.stride_tricks.sliding_window_view(lst, len(window))
    norms = np.linalg.norm(window - slides, axis=1)
    return norms.argmin()

Even faster and uses less memory:

def find_best_match_position(lst, window):
    return sum(
        (lst[i : i-len(window)+1 or None] - w) ** 2
        for i, w in enumerate(window)
    ).argmin()

Answered By - Kelly Bundy