- Метод 1: Наивный подход
Наивный подход предполагает сохранение окна и счетчика фиксированного размера. Каждый раз, когда поступает новый элемент, счетчик увеличивается, а если размер окна превышает желаемую длину, счетчик уменьшается для самого старого элемента. Вот пример кода на Python:
class SlidingWindowCounter:
def __init__(self, window_size):
self.window_size = window_size
self.counter = 0
self.window = []
def add(self, element):
self.window.append(element)
self.counter += 1
if len(self.window) > self.window_size:
self.counter -= self.window.pop(0)
counter = SlidingWindowCounter(5)
counter.add(1)
counter.add(2)
counter.add(3)
counter.add(4)
counter.add(5)
counter.add(6)
print(counter.counter) # Output: 15
- Метод 2: циклический буфер
Круговой буфер — еще один эффективный подход к реализации счетчиков скользящего окна. Он поддерживает буфер фиксированного размера, в котором новые элементы перезаписывают самые старые. Вот пример:
class SlidingWindowCounter:
def __init__(self, window_size):
self.window_size = window_size
self.counter = 0
self.window = [0] * window_size
self.index = 0
def add(self, element):
self.counter -= self.window[self.index]
self.window[self.index] = element
self.counter += element
self.index = (self.index + 1) % self.window_size
counter = SlidingWindowCounter(5)
counter.add(1)
counter.add(2)
counter.add(3)
counter.add(4)
counter.add(5)
counter.add(6)
print(counter.counter) # Output: 20
-
Метод 3: Дерево интервалов
Дерево интервалов — это более сложная структура данных, которую можно использовать для эффективных вычислений скользящего окна. Это позволяет осуществлять быстрые запросы и обновления диапазона. Хотя реализация дерева интервалов является более сложной, она обеспечивает повышенную производительность для окон большего размера. -
Метод 4: использование библиотек
Многие языки программирования и платформы предоставляют библиотеки или встроенные функции для вычислений скользящего окна. Например, в Python вы можете использовать классcollections.deque
для эффективной реализации скользящего окна.