Implement a sliding window using python

How to implement a sliding window using python

Photo by Daniel Alentà on Unsplash

Introduction

This article describes how to implement a sliding window using python. A sliding window is a subset of a data structure at a given point of time. The window size decides the number of elements in the subset.

Sliding window:

Let’s take an example of a list with 8 elements as below.

A python list with 8 elements as integers

Now, if we set the window size = 3, the output should be,

Output: 
123 
234 
345 
456 
567 
678

Note : At any given point of time the window size should always be 3.

Iteration 1 window elements[1,2,3]

Iteration 2 window elements[2,3,4]

Iteration 3 window elements[3,4,5]

…

Final iteration window elements[6,7,8]

Use Cases

This concept could be used in the following scenarios

• Calculate substrings of specific length from a longer string.
• Calculate the sum of consecutive n numbers in a list where n will be the window size

Code:

lst = [1,2,3,4,5,6,7,8] 
def sliding_window(elements, window_size):
    
    if len(elements) <= window_size:
       return elements
    for i in range(len(elements)):
        print(elements[i:i+window_size])

sliding_window(lst, 3)
Output:
[1, 2, 3] 
[2, 3, 4] 
[3, 4, 5] 
[4, 5, 6] 
[5, 6, 7] 
[6, 7, 8] 
[7, 8] 
[8]

This achieves the goal of a sliding window. However, we do not want any windows with elements less than our window size. In this case, the window_size is 3. Therefore we wil make a small change in our code to stop the iteration when we reach the window size.

Modified Code to Stop on Window Size

lst = [1,2,3,4,5,6,7,8] 
def sliding_window(elements, window_size):
    
    if len(elements) <= window_size:
       return elements
    for i in range(len(elements)- window_size + 1):
        print(elements[i:i+window_size])
sliding_window(lst, 3)
Output:
[1, 2, 3] 
[2, 3, 4] 
[3, 4, 5] 
[4, 5, 6] 
[5, 6, 7] 
[6, 7, 8]

Implement Sliding Window Using Generators

The sliding window technique can also be implemented using generators.Generators usually store the state of the execution and resume when called the next time. Let’s say for some reason you may have to save the state of sliding window and then resume from where you left, you could use a generator instead of a regular function. The yield keyword inside a function determines that the function is a generator.

This will return a generator object and you could either call next(object) to get the next value or iterator in a for loop.

lst = [1,2,3,4,5,6,7,8] 
lst = [1,2,3,4,5,6,7,8]
def sliding_window(elements, window_size):
    
    if len(elements) <= window_size:
       return elements
    for i in range(len(elements)- window_size + 1):
        yield elements[i:i+window_size]
sw_gen = sliding_window(lst, 3) 
print(next(sw_gen)) 
print(next(sw_gen))
Output: 
[1, 2, 3] 
[2, 3, 4]

Sliding Window to calculate substrings

We will use the sliding window technique to calculate substrings throught the length of the string. This could be used to check if a string is a permutation of other. To learn more about this, please check this article here to check for string permutation.

s = "eidbaooo"
def sliding_window(elements, window_size):
    
    if len(elements) <= window_size:
       return elements
    for i in range(len(elements)- window_size + 1):
        print(elements[i:i+window_size])
sliding_window(s, 2)
Output: 
ei 
id 
db 
ba 
ao 
oo 
oo

Summary:

In this article, we have discussed what a sliding window is and implemented the same using the following methods

• Sliding window using functions
• Sliding window using generators
• Sliding window for strings

Originally published at https://dineshkumarkb.com.