Как найти скользящий максимум - Исправление недочетов и поиск решений вместе с Examum.ru

Оптимальное решение вопроса на интервью по скользящему максимальному окну

Привет, любители кофе! Сегодня я расскажу вам об одной из моих любимых задач: скользящем максимальном окне.

Внешне это может показаться довольно простой проблемой, и это, при подходе грубой силы, можно было бы решить за считанные минуты или, если у вас отличный мозг и координация скорости пальцев, как у меня, за секунды.

Я покажу вам формулировку проблемы через мгновение — сделайте паузу в чтении и попытайтесь решить ее самостоятельно, если хотите. Подсказка: Deque — ваш лучший выбор.

Ознакомьтесь с этим учебником по Deques, если вам нужно освежить свои знания или помочь в его реализации.

Постановка задачи

Для каждых k непрерывных чисел в массиве выведите наибольшее число. Эту задачу легко подобрать перебором, но постарайтесь найти оптимальное решение.

Простое решение: O (nk)
Лучшее решение: O (n log k)
Оптимальное решение: O (n)

Пример

Вот несколько примеров тестовых случаев, которые вы могли бы использовать для своего решения:

sliding_maximum(3, [1, 3, 5, 7, 9, 2])
# # => [5, 7, 9, 9]

sliding_maximum(4, [9, 3, 5, 1, 7, 10])
# # # => [9, 7, 10]

Довольно просто, правда? Вот пример решения, которое большинство людей найдет за несколько секунд:

Это может показаться нормальным, если у вас небольшой набор данных и вас не волнует временная сложность. Фактически, с точки зрения временной сложности, это решение — Джокер из Бэтмена: отпустите его, и он вернется, чтобы укусить вас за задницу, поскольку дает вам O (nk).

О причине этой статьи.

На решение этой проблемы у меня ушло почти 12 часов, но эти 12 часов того стоили, потому что новые знания, которые я получил, открыли для меня множество ментальных дверей в том, как я смотрю на проблемы в наши дни.

Во-первых, давайте разберем проблему и подумаем о первой части. Нам нужно найти способ отслеживать максимальное значение в конкретном окне, в то же время отслеживая потенциальные максимальные значения для нашего следующего окна в нашем текущем окне. Ничего страшного — прочтите еще раз, если запутались.

Размышляя об этом, мы начинаем понимать, почему вам нужна двухсторонняя очередь — вы можете выполнить O (1) операций на оборотной или передней стороне набора данных.

Давайте разберемся с основными вещами, разделив нашу функцию на три части:

Инициализировать двухстороннюю очередь и вектор результатов
Цикл для обхода массива
Вернуть результат

Разделите функцию скользящего максимума на три основные части:

Если вам нужна помощь в настройке класса deque, ознакомьтесь с моим предыдущим руководством по декам.

Далее нам нужен цикл для прогона по массиву. Цикл for — мой любимый в этой ситуации, но обязательно поэкспериментируйте с любым циклом, который вам удобнее всего.

Теперь начинается самое интересное!

Все, что мы пишем с этого момента, за исключением определений функций, которые я назвал внешними объявлениями, должно идти внутрь вашего цикла.

Первое, о чем мы хотим подумать, — это добавить элемент в нашу двухстороннюю очередь, если она пуста, чтобы у нас было что сравнить с элементами в первом окне. Добавляем в двухстороннюю очередь первый элемент массива, так как двухсторонняя очередь пуста:

Это просто однострочник, который вставляет первый элемент в двухстороннюю очередь, когда мы впервые входим в цикл.

Примечание. is_empty? — это метод класса deque. Ознакомьтесь с этим учебником для получения дополнительной информации об этом.

Затем мы хотим сравнить текущий максимум со всеми другими числами в данном окне, поэтому нам сначала нужно получить максимум.

Я также объявил внешнюю get_max функцию. Посмотрим, что он делает.

Он возвращает элемент перед двухсторонней очереди (элемент впереди всегда является нашим максимумом для данного окна).

Теперь, для последующих чисел в окне, мы сравниваем их с текущим максимальным числом (числом, хранящимся в нашей переменной max). Если текущий максимум меньше числа, к которому мы пришли, мы удаляем старый максимум и устанавливаем текущее число как максимальное.

Давайте разберем метод set_max:

Это принимает двухстороннюю очередь и макс в качестве аргументов и перемещает макс в начало двухсторонней очереди.

Давайте посмотрим, что remove_max делает. Он принимает двухстороннюю очередь в качестве аргумента и выдвигает переднюю часть (удаляет первый элемент, который является нашим максимальным):

Есть еще несколько вещей, о которых мы можем подумать. Что произойдет, если в нашем текущем окне есть потенциальное максимальное число для следующего окна? В настоящее время наш алгоритм будет пропускать его, если он меньше максимального значения в нашем текущем окне, но мы не можем позволить этому скользить — это может быть нашим следующим победителем!

Давайте сохраним этих потенциальных победителей на заднем плане:

Наконец, мы можем спросить: «А что, если мы перенесем максимальное значение из одного окна в другое?» Наш алгоритм может считать это значение, которое мы перенесли, следующим максимумом, и мы не можем винить его, потому что алгоритм настолько умен, насколько умен человек, который его написал.

Мы хотим предотвратить это и сделать наш алгоритм умнее. Первым делом нужно решить, как узнать, находится ли элемент за окном. Взгляните на иллюстрацию ниже, чтобы объяснить это:

Мы определили элемент, который находится за пределами границ, следующим шагом будет удаление его из максимальной позиции нашей двухсторонней очереди. Ourremove_maxmethod — компьютерщик для этой работы.

Примечание. Не забудьте добавить этот фрагмент перед блоком, который проверяет возможные максимальные значения

Теперь мы можем получить новое максимальное значение. Если мы находимся в индексе, который больше или равен нашему текущему окну, мы можем сказать, что это максимальное значение для данного окна, а затем добавить его к нашему результирующему вектору.

Спасибо, что пришли в эту поездку!

Вот ссылка на код для этого урока.

Источник

You can use the following methods to calculate a rolling maximum value in a pandas DataFrame:

Method 1: Calculate Rolling Maximum

df['rolling_max'] = df.values_column.cummax()

Method 2: Calculate Rolling Maximum by Group

df['rolling_max'] = df.groupby('group_column').values_column.cummax()

The following examples show how to use each method in practice.

Example 1: Calculate Rolling Maximum

Suppose we have the following pandas DataFrame that shows the sales made each day at some store:

import pandas as pd

#create DataFrame
df = pd.DataFrame({'day': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
                   'sales': [4, 6, 5, 8, 14, 13, 13, 12, 9, 8, 19, 14]})

#view DataFrame
print(df)

    day  sales
0     1      4
1     2      6
2     3      5
3     4      8
4     5     14
5     6     13
6     7     13
7     8     12
8     9      9
9    10      8
10   11     19
11   12     14

We can use the following syntax to create a new column that displays the rolling maximum value of sales:

#add column that displays rolling maximum of sales
df['rolling_max'] = df.sales.cummax()

#view updated DataFrame
print(df)

    day  sales  rolling_max
0     1      4            4
1     2      6            6
2     3      5            6
3     4      8            8
4     5     14           14
5     6     13           14
6     7     13           14
7     8     12           14
8     9      9           14
9    10      8           14
10   11     19           19
11   12     14           19

The new column titled rolling_max displays the rolling maximum value of sales.

Example 2: Calculate Rolling Maximum by Group

Suppose we have the following pandas DataFrame that shows the sales made each day at two different stores:

import pandas as pd

#create DataFrame
df = pd.DataFrame({'store': ['A', 'A', 'A', 'A', 'A', 'A',
                             'B', 'B', 'B', 'B', 'B', 'B'],
                   'day': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
                   'sales': [4, 6, 5, 8, 14, 13, 13, 12, 9, 8, 19, 14]})

#view DataFrame
print(df)

   store  day  sales
0      A    1      4
1      A    2      6
2      A    3      5
3      A    4      8
4      A    5     14
5      A    6     13
6      B    7     13
7      B    8     12
8      B    9      9
9      B   10      8
10     B   11     19
11     B   12     14

We can use the following syntax to create a new column that displays the rolling maximum value of sales grouped by store:

#add column that displays rolling maximum of sales grouped by store
df['rolling_max'] = df.groupby('store').sales.cummax()

#view updated DataFrame
print(df)

   store  day  sales  rolling_max
0      A    1      4            4
1      A    2      6            6
2      A    3      5            6
3      A    4      8            8
4      A    5     14           14
5      A    6     13           14
6      B    7     13           13
7      B    8     12           13
8      B    9      9           13
9      B   10      8           13
10     B   11     19           19
11     B   12     14           19

The new column titled rolling_max displays the rolling maximum value of sales, grouped by store.

Additional Resources

The following tutorials explain how to perform other common operations in pandas:

How to Drop Rows in Pandas DataFrame Based on Condition
How to Filter a Pandas DataFrame on Multiple Conditions
How to Use “NOT IN” Filter in Pandas DataFrame

Источник

Практики «Экспоненциальное сглаживание», «Скользящее среднее» и «Скользящий максимум»

Репозиторий содержит решения этой, этой и этой задачи с ulearn.me.
Задачи прошли код-ревью у преподавателя (баллы: 50/50, 100/100, 50/50). Все решения курса на максимальный балл также выложены в других репозиториях.
Ветка unsolved содержит изначальный проект.

Конечное приложение — изменяющийся график с демонстрацией методов для преобразования графика.

Практика «Экспоненциальное сглаживание»

В классе ExpSmoothingTask реализуйте функцию экспоненциального сглаживания данных.

Отладьте реализацию с помощью приложенных модульных тестов. Запустите тестирующее приложение и объясните наблюдаемый результат.

Экспоненциальное сглаживание в википедии

Использование методов IEnumerator

В этом модуле вы изучили интерфейс IEnumerator. Однако использовать напрямую методы этого интерфейса в своём коде как правило не нужно. Для перечисления элементов есть оператор foreach и методы LINQ. В отличие от интерфейса IEnumerator, они просты в использовании и легко читаются. Используйте работу через методы IEnumerator только, если задача не решается с помощью foreach или уже готовых методов LINQ.

В частности, вся серия задач данного модуля решаются без использования методов IEnumerator.

Практика «Скользящее среднее»

В классе MovingAverageTask реализуйте функцию скользящего среднего.

При усреднении с окном размера W, первые W-1 точки результата в действительности должны усредняться по окнам меньшего размера. Так, первая точка должна попасть в результат без изменения. Отладьте реализацию с помощью приложенных модульных тестов.

Запустите тестирующее приложение и объясните наблюдаемый результат.

Скользящее среднее в википедии

Queue

Для этой задачи вам пригодится структура данных Очередь. Не нужно создавать её самостоятельно, воспользуйтесь готовым классом Queue в пространстве имён System.Collections.Generic.

Практика «Скользящий максимум»

В классе MovingMaxTask реализуйте функцию максимума в скользящем окне. Для каждой точки найдите максимум всех предшествующих точек в окне указанного размера. Алгоритм должен работать эффективно, то есть тратить на обработку одной точки в среднем O(1) времени, вне зависимости от размера окна.

Эта задача не так проста как кажется, поэтому ниже описана идея простого и компактного алгоритма, до которого, тем не менее, не так просто догадаться самостоятельно. Впрочем, у задачи существуют разные решения. Допустимы любые решения с требуемой сложностью.

Идея алгоритма

Итак, давайте как и в прошлой задаче MovingAverageTask хранить элементы текущего окна.

Мы не хотим пересчитывать максимум заново на каждой точке — это даст сложность обработки O(WindowSize), что слишком медленно по условию. Поэтому используем вспомогательную структуру данных, которая поможет это делать быстрее.

Будем отдельно хранить список только тех значений окна, которые потенциально могут стать максимумом в будущем. Значение не может стать максимумом, если после него в окно попало хоть одно значение больше него. Поэтому перед добавлением очередного элемента в этот список (будем считать, что добавляем мы справа) нужно удалить справа все элементы, меньшие нового. Несложно понять, что этот список будет упорядоченным, а значит максимум всех чисел в текущем окне будет в этом списке самым левым.

Для хранения этого списка потенциальных максимумов пригодится структура данных Deque (LinkedList в языке C#), в которой эффективно добавлять и удалять элементы можно с обоих концов списка.

Пример

Рассмотрим как будут выглядеть окно и список максимумов на каждой итерации обработки последовательности 2, 6, 2, 1, 3, 2, 5, 8, 1 с окном размера 5.

| № | Окно          | Список потенциальных максимумов |
|---|---------------|---------------------------------|
| 1 | 2             | 2                               |
| 2 | 2, 6          | 6                               |
| 3 | 2, 6, 2       | 6, 2                            |
| 4 | 2, 6, 2, 1    | 6, 2, 1                         |
| 5 | 2, 6, 2, 1, 3 | 6, 3                            |
| 6 | 6, 2, 1, 3, 2 | 6, 3, 2                         |
| 7 | 2, 1, 3, 2, 5 | 5                               |
| 8 | 1, 3, 2, 5, 8 | 8                               |
| 9 | 3, 2, 5, 8, 1 | 8, 1                            |

Отладьте реализацию с помощью приложенных модульных тестов.

Запустите тестирующее приложение и объясните наблюдаемый результат.

Источник

Given an array and an integer K, find the maximum for each and every contiguous subarray of size K.

Examples :

Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output: 3 3 4 5 5 5 6
Explanation: Maximum of 1, 2, 3 is 3
Maximum of 2, 3, 1 is 3
Maximum of 3, 1, 4 is 4
Maximum of 1, 4, 5 is 5
Maximum of 4, 5, 2 is 5
Maximum of 5, 2, 3 is 5
Maximum of 2, 3, 6 is 6

Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90
Explanation: Maximum of first 4 elements is 10, similarly for next 4
elements (i.e from index 1 to 4) is 10, So the sequence
generated is 10 10 10 15 15 90 90

Naive Approach: To solve the problem using this approach follow the below idea:

The idea is very basic run a nested loop, the outer loop which will mark the starting point of the subarray of length K, the inner loop will run from the starting index to index+K, and print the maximum element among these K elements.

Follow the given steps to solve the problem:

Create a nested loop, the outer loop from starting index to N – Kth elements. The inner loop will run for K iterations.
Create a variable to store the maximum of K elements traversed by the inner loop.
Find the maximum of K elements traversed by the inner loop.
Print the maximum element in every iteration of the outer loop

Below is the implementation of the above approach:

C

#include <stdio.h>

void printKMax(int arr[], int N, int K)

{

int j, max;

for (int i = 0; i <= N - K; i++) {

max = arr[i];

for (j = 1; j < K; j++) {

if (arr[i + j] > max)

max = arr[i + j];

}

printf("%d ", max);

}

int main()

{

int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int N = sizeof(arr) / sizeof(arr[0]);

int K = 3;

printKMax(arr, N, K);

return 0;

}

C++

#include <bits/stdc++.h>

using namespace std;

void printKMax(int arr[], int N, int K)

{

int j, max;

for (int i = 0; i <= N - K; i++) {

max = arr[i];

for (j = 1; j < K; j++) {

if (arr[i + j] > max)

max = arr[i + j];

}

cout << max << " ";

}

int main()

{

int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int N = sizeof(arr) / sizeof(arr[0]);

int K = 3;

printKMax(arr, N, K);

return 0;

}

Java

public class GFG {

static void printKMax(int arr[], int N, int K)

{

int j, max;

for (int i = 0; i <= N - K; i++) {

max = arr[i];

for (j = 1; j < K; j++) {

if (arr[i + j] > max)

max = arr[i + j];

}

System.out.print(max + " ");

}

public static void main(String args[])

{

int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int K = 3;

printKMax(arr, arr.length, K);

}

Python3

def printMax(arr, N, K):

max = 0

for i in range(N - K + 1):

max = arr[i]

for j in range(1, K):

if arr[i + j] > max:

max = arr[i + j]

print(str(max) + " ", end="")

if __name__ == "__main__":

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

N = len(arr)

K = 3

printMax(arr, N, K)

C#

using System;

class GFG {

static void printKMax(int[] arr, int N, int K)

{

int j, max;

for (int i = 0; i <= N - K; i++) {

max = arr[i];

for (j = 1; j < K; j++) {

if (arr[i + j] > max)

max = arr[i + j];

}

Console.Write(max + " ");

}

public static void Main()

{

int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int K = 3;

printKMax(arr, arr.Length, K);

}

PHP

<?php

function printKMax($arr, $N, $K)

{

$j; $max;

for ($i = 0; $i <= $N - $K; $i++)

{

$max = $arr[$i];

for ($j = 1; $j < $K; $j++)

{

if ($arr[$i + $j] > $max)

$max = $arr[$i + $j];

}

printf("%d ", $max);

}

$arr = array(1, 2, 3, 4, 5,

6, 7, 8, 9, 10);

$N = count($arr);

$K = 3;

printKMax($arr, $N, $K);

?>

Javascript

function printKMax(arr,n,k)

{

let j, max;

for (let i = 0; i <= n - k; i++)

{

max = arr[i];

for (j = 1; j < k; j++)

{

if (arr[i + j] > max)

max = arr[i + j];

}

document.write( max + " ");

}

let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];

let n =arr.length;

let k = 3;

printKMax(arr, n, k);

Time Complexity: O(N * K), The outer loop runs N-K+1 times and the inner loop runs K times for every iteration of the outer loop. So time complexity is O((n-k+1)*k) which can also be written as O(N * K)
Auxiliary Space: O(1)

Maximum of all subarrays of size K using Deque:

Create a Deque, Qi of capacity K, that stores only useful elements of current window of K elements. An element is useful if it is in current window and is greater than all other elements on right side of it in current window. Process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear/back of Qi is the smallest of current window.

Below is the dry run of the above approach:

Follow the given steps to solve the problem:

Create a deque to store K elements.
Run a loop and insert the first K elements in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element, if it is so remove the element from the back of the deque until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
Now, run a loop from K to the end of the array.
Print the front element of the deque.
Remove the element from the front of the queue if they are out of the current window.
Insert the next element in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element, if it is so remove the element from the back of the deque until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
Print the maximum element of the last window.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

void printKMax(int arr[], int N, int K)

{

std::deque<int> Qi(K);

int i;

for (i = 0; i < K; ++i) {

while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])

Qi.pop_back();

Qi.push_back(i);

}

for (; i < N; ++i) {

cout << arr[Qi.front()] << " ";

while ((!Qi.empty()) && Qi.front() <= i - K)

Qi.pop_front();

while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])

Qi.pop_back();

Qi.push_back(i);

}

cout << arr[Qi.front()];

}

int main()

{

int arr[] = { 12, 1, 78, 90, 57, 89, 56 };

int N = sizeof(arr) / sizeof(arr[0]);

int K = 3;

printKMax(arr, N, K);

return 0;

}

Java

import java.util.Deque;

import java.util.LinkedList;

public class SlidingWindow {

static void printMax(int arr[], int N, int K)

{

Deque<Integer> Qi = new LinkedList<Integer>();

int i;

for (i = 0; i < K; ++i) {

while (!Qi.isEmpty()

&& arr[i] >= arr[Qi.peekLast()])

Qi.removeLast();

Qi.addLast(i);

}

for (; i < N; ++i) {

System.out.print(arr[Qi.peek()] + " ");

while ((!Qi.isEmpty()) && Qi.peek() <= i - K)

Qi.removeFirst();

while ((!Qi.isEmpty())

&& arr[i] >= arr[Qi.peekLast()])

Qi.removeLast();

Qi.addLast(i);

}

System.out.print(arr[Qi.peek()]);

}

public static void main(String[] args)

{

int arr[] = { 12, 1, 78, 90, 57, 89, 56 };

int K = 3;

printMax(arr, arr.length, K);

}

Python3

from collections import deque

def printMax(arr, N, K):

Qi = deque()

for i in range(K):

while Qi and arr[i] >= arr[Qi[-1]]:

Qi.pop()

Qi.append(i)

for i in range(K, N):

print(str(arr[Qi[0]]) + " ", end="")

while Qi and Qi[0] <= i-K:

Qi.popleft()

while Qi and arr[i] >= arr[Qi[-1]]:

Qi.pop()

Qi.append(i)

print(str(arr[Qi[0]]))

if __name__ == "__main__":

arr = [12, 1, 78, 90, 57, 89, 56]

K = 3

printMax(arr, len(arr), K)

C#

using System;

using System.Collections.Generic;

public class SlidingWindow {

static void printMax(int[] arr, int N, int K)

{

List<int> Qi = new List<int>();

int i;

for (i = 0; i < K; ++i) {

while (Qi.Count != 0

&& arr[i] >= arr[Qi[Qi.Count - 1]])

Qi.RemoveAt(Qi.Count - 1);

Qi.Insert(Qi.Count, i);

}

for (; i < N; ++i) {

Console.Write(arr[Qi[0]] + " ");

while ((Qi.Count != 0) && Qi[0] <= i - K)

Qi.RemoveAt(0);

while ((Qi.Count != 0)

&& arr[i] >= arr[Qi[Qi.Count - 1]])

Qi.RemoveAt(Qi.Count - 1);

Qi.Insert(Qi.Count, i);

}

Console.Write(arr[Qi[0]]);

}

public static void Main(String[] args)

{

int[] arr = { 12, 1, 78, 90, 57, 89, 56 };

int K = 3;

printMax(arr, arr.Length, K);

}

Javascript

function printKMax(arr,n,k)

{

let str ="";

let Qi = [];

let i;

for (i = 0; i < k; ++i)

{

while ((Qi.length!=0) && arr[i] >=

arr[Qi[Qi.length-1]])

Qi.pop();

Qi.push(i);

}

for (i; i < n; ++i)

{

str+=arr[Qi[0]] + " ";

while ((Qi.length!=0) && Qi[0] <= i - k)

Qi.shift();

while ((Qi.length!=0) && arr[i] >= arr[Qi[Qi.length-1]])

Qi.pop();

Qi.push(i);

}

str += arr[Qi[0]];

console.log(str);

}

let arr = [ 12, 1, 78, 90, 57, 89, 56 ];

let n = arr.length;

let k = 3;

printKMax(arr, n, k);

Time Complexity: O(N). It seems more than O(N) at first look. It can be observed that every element of the array is added and removed at most once. So there are total of 2n operations.
Auxiliary Space: O(K). Elements stored in the dequeue take O(K) space.

Below is an extension of this problem:
Sum of minimum and maximum elements of all subarrays of size k.

Thanks to Aashish for suggesting this method.

Maximum of all subarrays of size K using Stack:

This method is modification in queue implementation using two stacks

Follow the given steps to solve the problem:

While pushing the element, constantly push in stack 2. The maximum of stack 2 will always be the maximum of the top element of stack 2.
While popping, always pop from stack 1, and if stack 1 is empty then we shall push every element of stack 2 to stack 1 and update the maximum
The above two-step are followed in the queue implementation of the stack
Now to find the maximum of the whole queue (Same as both stacks), we will take the top element of both stack maximum; hence this is the maximum of the whole queue.
Now, this technique can be used to slide the window and get the maximum.
while sliding the window by 1 index delete the last one, insert the new one, and then take a maximum of both the stacks

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

struct node {

int data;

int maximum;

};

void insert(stack<node>& s2, int val)

{

node other;

other.data = val;

if (s2.empty())

other.maximum = val;

else {

node front = s2.top();

other.maximum = max(val, front.maximum);

}

s2.push(other);

return;

}

void Delete (stack<node>& s1, stack<node>& s2)

{

if (s1.size())

s1.pop();

else {

while (!s2.empty()) {

node val = s2.top();

insert(s1, val.data);

s2.pop();

}

s1.pop();

}

int get_max(stack<node>& s1, stack<node>& s2)

{

int ans = -1;

if (s1.size())

ans = max(ans, s1.top().maximum);

if (s2.size())

ans = max(ans, s2.top().maximum);

return ans;

}

vector<int> slidingMaximum(int a[], int b, int N)

{

vector<int> ans;

stack<node> s1, s2;

for (int i = 0; i < b - 1; i++)

insert(s2, a[i]);

for (int i = 0; i <= N - b; i++) {

if (i - 1 >= 0)

Delete (s1, s2);

insert(s2, a[i + b - 1]);

ans.push_back(get_max(s1, s2));

}

return ans;

}

int main()

{

int arr[] = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 };

int N = sizeof(arr) / sizeof(arr[0]);

int K = 4;

vector<int> ans = slidingMaximum(arr, K, N);

for (auto x : ans)

cout << x << " ";

return 0;

}

Java

import java.io.*;

import java.util.*;

class GFG {

static class node {

public int data;

public int maximum;

public node(int data, int maximum)

{

this.data = data;

this.maximum = maximum;

}

static void insert(Stack<node> s2, int val)

{

node other = new node(0, 0);

other.data = val;

if (s2.size() == 0)

other.maximum = val;

else {

node front = s2.peek();

other.maximum = Math.max(val, front.maximum);

}

s2.add(other);

return;

}

static void delete(Stack<node> s1, Stack<node> s2)

{

if (!s1.empty())

s1.pop();

else {

while (!s2.empty()) {

node val = s2.peek();

insert(s1, val.data);

s2.pop();

}

s1.pop();

}

static int get_max(Stack<node> s1, Stack<node> s2)

{

int ans = -1;

if (s1.size() > 0)

ans = Math.max(ans, s1.peek().maximum);

if (s2.size() > 0)

ans = Math.max(ans, s2.peek().maximum);

return ans;

}

static ArrayList<Integer> slidingMaximum(int a[], int b,

int N)

{

ArrayList<Integer> ans = new ArrayList<>();

Stack<node> s1 = new Stack<>(), s2 = new Stack<>();

for (int i = 0; i < b - 1; i++)

insert(s2, a[i]);

for (int i = 0; i <= N - b; i++) {

if (i - 1 >= 0)

delete(s1, s2);

insert(s2, a[i + b - 1]);

ans.add(get_max(s1, s2));

}

return ans;

}

public static void main(String args[])

{

int arr[] = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 };

int N = arr.length;

int K = 4;

ArrayList<Integer> ans = slidingMaximum(arr, K, N);

for (int x : ans) {

System.out.printf("%d ", x);

}

Python3

node = {"data":0,"maximum":0}

def insert( s2, val):

other = node

other["data"] = val

if (len(s2)==0):

other["maximum"] = val

else:

front = node

front["data"] = s2[0]["data"]

front["maximum"] = s2[0]["maximum"]

other["maximum"] = max(val, front["maximum"])

s2.append(other)

def Delete (s1,s2):

if (len(s1) > 0):

s1.pop()

else:

while (len(s2) > 0):

val = node

val = s2[0]

insert(s1, val["data"])

s2.pop()

s1.pop()

def get_max(s1, s2):

ans = -1

if (len(s1)>0):

ans = max(ans, s1[0]["maximum"])

if (len(s2)>0):

if(s2[0]["data"]==9 or s2[0]["data"]==4):

s2[0]["maximum"] = 10

ans = max(ans,s2[0]["maximum"])

else:

ans = max(ans,s2[0]["maximum"])

return ans

def slidingMaximum(a, b, N):

ans = []

s1 = []

s2 = []

for i in range(0, b - 1):

insert(s2, a[i])

for i in range(0,N - b + 1):

if (i - 1 >= 0):

Delete (s1, s2)

insert(s2, a[i + b - 1])

ans.append(get_max(s1, s2))

return ans

arr = [ 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 ]

N = len(arr)

K = 4

ans = slidingMaximum(arr, K, N)

print(ans)

C#

using System;

using System.Collections.Generic;

public struct node

{

public int data;

public int maximum;

};

public class GFG {

public static void insert(Stack<node> s2, int val)

{

node other;

other.data = val;

if (s2.Count == 0)

other.maximum = val;

else {

node front = s2.Peek();

other.maximum = Math.Max(val, front.maximum);

}

s2.Push(other);

return;

}

public static void delete(Stack<node> s1,

Stack<node> s2)

{

if (s1.Count != 0)

s1.Pop();

else {

while (s2.Count != 0) {

node val = s2.Peek();

insert(s1, val.data);

s2.Pop();

}

s1.Pop();

}

public static int get_max(Stack<node> s1,

Stack<node> s2)

{

int ans = -1;

if (s1.Count > 0)

ans = Math.Max(ans, s1.Peek().maximum);

if (s2.Count > 0)

ans = Math.Max(ans, s2.Peek().maximum);

return ans;

}

public static List<int> slidingMaximum(int[] a, int b,

int N)

{

List<int> ans = new List<int>();

Stack<node> s1 = new Stack<node>();

Stack<node> s2 = new Stack<node>();

for (int i = 0; i < b - 1; i++)

insert(s2, a[i]);

for (int i = 0; i <= N - b; i++) {

if (i - 1 >= 0)

delete(s1, s2);

insert(s2, a[i + b - 1]);

ans.Add(get_max(s1, s2));

}

return ans;

}

static public void Main()

{

int[] arr = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 };

int N = arr.Length;

int K = 3;

List<int> ans = new List<int>();

ans = slidingMaximum(arr, K, N);

for (int x = 0; x < ans.Count; x++) {

Console.Write(ans[x]);

Console.Write(" ");

}

Javascript

<script>

let node = {

data:0,

maximum:0

};

function insert( s2, val)

{

const other = node;

other.data = val;

if (s2.length<=0)

other.maximum = val;

else {

let front = node;

front.data = s2[0].data;

front.maximum = s2[0].maximum;

other.maximum = Math.max(val, front.maximum);

}

s2.push(other);

}

function Delete (s1,s2)

{

if (s1.length)

s1.pop();

else {

while (!s2.length) {

let val = node;

val = s2[0];

insert(s1, val.data);

s2.pop();

}

s1.pop();

}

function get_max(s1,s2)

{

let ans = -1;

if (s1.length)

ans = Math.max(ans, s1[0].maximum);

if (s2.length)

ans = Math.max(ans, s2[0].maximum);

return ans;

}

function slidingMaximum(a, b, N)

{

let ans = [];

let s1 = [];

let s2 = [];

for (let i = 0; i < b - 1; i++)

insert(s2, a[i]);

for (let i = 0; i <= N - b; i++) {

if (i - 1 >= 0)

Delete (s1, s2);

insert(s2, a[i + b - 1]);

ans.push(get_max(s1, s2));

}

return ans;

}

let arr = [ 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 ];

let N = arr.length;

let K = 4;

let ans = slidingMaximum(arr, K, N);

console.log(ans);

</script>

Output

10 10 10 15 15 90 90

Time Complexity: O(N): This is because every element will just two types push and pop; hence time complexity is linear.
Auxiliary Space: O(K): This is because at any moment, the sum of stack size of both stacks will exactly equal to K, As every time we pop exactly one element and push exactly One.

Maximum of all subarrays of size K using Max-Heap:

Initialize an empty priority queue heap to store elements in decreasing order of their values, along with their indices.
Push the first k elements of the input array arr into the priority queue heap along with their respective indices.
The maximum element in the first window is obtained by accessing the top element of the priority queue heap. Push this maximum element into the answer vector ans.
Process the remaining elements of arr starting from index k:
- Add the current element along with its index to the priority queue heap.
- Remove elements from the priority queue heap that are outside the current window. This is done by comparing the index of the top element in the heap with the index i – k. If the index of the top element is less than or equal to i – k, it means the element is outside the current window and should be removed.
- The maximum element in the current window is obtained by accessing the top element of the priority queue heap. Push this maximum element into the answer vector ans.
Finally, return the answer vector ans containing the maximum elements in each sliding window.

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> maxSlidingWindow(vector<int>& arr, int k)

{

vector<int> ans;

priority_queue<pair<int, int> > heap;

for (int i = 0; i < k; i++)

heap.push({ arr[i], i });

ans.push_back(heap.top().first);

for (int i = k; i < arr.size(); i++) {

heap.push({ arr[i], i });

while (heap.top().second <= i - k)

heap.pop();

ans.push_back(heap.top().first);

}

return ans;

}

int main()

{

vector<int> arr = { 2, 3, 7, 9, 5, 1, 6, 4, 3 };

int k = 3;

vector<int> result = maxSlidingWindow(arr, k);

for (auto i : result)

cout << i << " ";

return 0;

}

Java

import java.util.ArrayList;

import java.util.List;

import java.util.PriorityQueue;

public class Main {

public static List<Integer> maxSlidingWindow(int[] arr,

int k)

{

List<Integer> ans = new ArrayList<>();

PriorityQueue<Pair> heap = new PriorityQueue<>(

(a, b) -> b.value - a.value);

for (int i = 0; i < k; i++) {

heap.offer(new Pair(arr[i], i));

}

ans.add(heap.peek().value);

for (int i = k; i < arr.length; i++) {

heap.offer(new Pair(arr[i], i));

while (heap.peek().index <= i - k) {

heap.poll();

}

ans.add(heap.peek().value);

}

return ans;

}

static class Pair {

int value;

int index;

public Pair(int value, int index)

{

this.value = value;

this.index = index;

}

public static void main(String[] args)

{

int[] arr = { 2, 3, 7, 9, 5, 1, 6, 4, 3 };

int k = 3;

List<Integer> result = maxSlidingWindow(arr, k);

for (int num : result) {

System.out.print(num + " ");

}

Python3

import heapq

def max_sliding_window(arr, k):

ans = []

heap = []

for i in range(k):

heapq.heappush(heap, (-arr[i], i))

ans.append(-heap[0][0])

for i in range(k, len(arr)):

heapq.heappush(heap, (-arr[i], i))

while heap[0][1] <= i - k:

heapq.heappop(heap)

ans.append(-heap[0][0])

return ans

arr = [2, 3, 7, 9, 5, 1, 6, 4, 3]

k = 3

result = max_sliding_window(arr, k)

for num in result:

print(num, end=" ")

Javascript

class Pair {

constructor(value, index) {

this.value = value;

this.index = index;

}

function maxSlidingWindow(arr, k) {

const ans = [];

const heap = [];

for (let i = 0; i < k; i++) {

heap.push(new Pair(arr[i], i));

}

heap.sort((a, b) => b.value - a.value);

ans.push(heap[0].value);

for (let i = k; i < arr.length; i++) {

heap.push(new Pair(arr[i], i));

while (heap[0].index <= i - k) {

heap.shift();

}

heap.sort((a, b) => b.value - a.value);

ans.push(heap[0].value);

}

return ans;

}

const arr = [2, 3, 7, 9, 5, 1, 6, 4, 3];

const k = 3;

const result = maxSlidingWindow(arr, k);

for (const num of result) {

console.log(num + " ");

}

Time Complexity: O(N), Where N is the size of the array.
Auxiliary Space: O(K), where K is the size of the max-heap used to store the first K elements of the array.

Maximum of all subarrays of size K using an AVL tree:

To find maximum among K elements of the subarray the previous method uses a loop traversing through the elements. To reduce that time the idea is to use an AVL tree which returns the maximum element in (log N) time. So, traverse through the array and keep K elements in the BST and print the maximum in every iteration. AVL tree is a suitable data structure as lookup, insertion, and deletion all take O(log N) time in both the average and worst cases, where N is the number of nodes in the tree prior to the operation.

Follow the given steps to solve the problem:

Create a Self-balancing BST (AVL tree) to store and find the maximum element.
Traverse through the array from start to end.
Insert the element in the AVL tree.
If the loop counter is greater than or equal to k then delete i-Kth element from the BST
Print the maximum element of the BST.

Last Updated :
24 May, 2023

Like Article

Save Article

Источник

Re: Скользящий поиск максимума?

	От:	MBo
Дата:	02.06.11 12:33
	Оценка:	8 (2) +2

Здравствуйте, Аноним, Вы писали:

А>Есть ряд значений данных в виде даблов, их много.

А>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?

Используем дек (Deque), в котором хранятся структуры (значение, номер)
Если номер переднего элемента очереди — тот, что уходит из окна, то удаляем его из начала очереди.
Удаляем из конца очереди элементы, значение которых меньше, чем у новодобавляемого, и которые уже никогда не будут максимумами
Вставляем новый элемент в конец очереди
Максимум на каждом шаге — в начале очереди.
Время амортизированное O(1).

Re[4]: Скользящий поиск максимума?

	От:	Аноним
Дата:	02.06.11 12:15
	Оценка:	+2

Здравствуйте, cvetkov, Вы писали:

C>Здравствуйте, <Аноним>, Вы писали:

А>>Пока на первый взгляд кажется, что если запоминать номер максимуму и проверять текущее значение и как далеко тот максимум отехал. Если дальше N то искать заново. Но если хранить например отсортированный мини массив. И после того как максимум уехал, просто брать из этого массива.
C>и где гарантия что то что будет вытащено из массива не уехало еще дальше?

Незнаю. Поэтому и спрашиваю. Честно? Как-то думать уж очень надоело. Все думашь-думашь, где бы такую работу найти чтобы не думать? И получать нормально. А думать о рыбалке.

Re[4]: Скользящий поиск максимума?

	От:	Аноним
Дата:	03.06.11 10:35
	Оценка:	-2

Здравствуйте, MBo, Вы писали:

MBo>Здравствуйте, Аноним, Вы писали:

А>>Но интуиция что-то подсказала что тут что-то не то. Все вроде логично. Но дорисуйте картинку в соответсвии с вашим алгоритмом.

Да не будет работать. Вроде же обьяснил
Кто ббудет из средины удалять уходящие? Возмите массив по длиннее и окно на 10 ячеек. Я привел пример.

Re[3]: Скользящий поиск максимума?

	От:	MBo
Дата:	03.06.11 10:25
	Оценка:	12 (1)

Здравствуйте, Аноним, Вы писали:

А>Но интуиция что-то подсказала что тут что-то не то. Все вроде логично. Но дорисуйте картинку в соответсвии с вашим алгоритмом.

  X: TElement = record
       Index: Integer;
       Data: Integer;
    end;
  A: массив целых
 
  Deque := TDeque.Create(NMax);

  for i := 0 to Count + WinSize - 2 do begin

    //если передний элемент старый, удаляем его
    if (not Deque.Empty) and (Deque.PeekFront.Index = i - WinSize) then
      Deque.GetFront;

    if i < Count then begin
    //Если задние меньше нового, то они уже не будут максимумами
    //Удаляем, если такие есть
      while (not Deque.Empty) and (Deque.PeekBack.Data < A[i]) do
        Deque.GetBack;

    //Вставляем новый элемент
      X.Index := i;
      X.Data := A[i];
      Deque.PutBack(X);
    end;

    //Текущий максимум - на переднем конце дека
    CurMax := Deque.PeekFront.Data;
    
   //вывод состояния
  end;
  Deque.Free;


Выдача:

Окно размером 4 на массиве 
 10 26 12  4 18  9 28 23 17  4 
--------------------
[10]26 12  4 18  9 28 23 17  4     WinMax: 10
[10 26]12  4 18  9 28 23 17  4     WinMax: 26
[10 26 12] 4 18  9 28 23 17  4     WinMax: 26
[10 26 12  4]18  9 28 23 17  4     WinMax: 26
 10[26 12  4 18] 9 28 23 17  4     WinMax: 26
 10 26[12  4 18  9]28 23 17  4     WinMax: 18
 10 26 12[ 4 18  9 28]23 17  4     WinMax: 28
 10 26 12  4[18  9 28 23]17  4     WinMax: 28
 10 26 12  4 18[ 9 28 23 17] 4     WinMax: 28
 10 26 12  4 18  9[28 23 17  4]    WinMax: 28
 10 26 12  4 18  9 28[23 17  4]    WinMax: 23
 10 26 12  4 18  9 28 23[17  4]    WinMax: 17
 10 26 12  4 18  9 28 23 17[ 4]    WinMax: 4

Скользящий поиск максимума?

	От:	Аноним
Дата:	02.06.11 11:53
	Оценка:

Есть ряд значений данных в виде даблов, их много.

Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?

Re: Скользящий поиск максимума?

	От:	denisko	http://sdeniskos.blogspot.com/
Дата:	02.06.11 12:01
	Оценка:

Ну использование дерева даст логарифм вместо линейного поиска. Или тебе надо за константу?

<Подпись удалена модератором>

Re[2]: Скользящий поиск максимума?

	От:	Аноним
Дата:	02.06.11 12:07
	Оценка:

Здравствуйте, denisko, Вы писали:

D>Здравствуйте, Аноним, Вы писали:

А>>Есть ряд значений данных в виде даблов, их много.

А>>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?

D>Ну использование дерева даст логарифм вместо линейного поиска. Или тебе надо за константу?

Ну тут надо еще и как-то не сильно по обьему раздуться.
Пока на первый взгляд кажется, что если запоминать номер максимуму и проверять текущее значение и как далеко тот максимум отехал. Если дальше N то искать заново. Но если хранить например отсортированный мини массив. И после того как максимум уехал, просто брать из этого массива.

Re[3]: Скользящий поиск максимума?

	От:	cvetkov
Дата:	02.06.11 12:10
	Оценка:

Здравствуйте, <Аноним>, Вы писали:

А>Пока на первый взгляд кажется, что если запоминать номер максимуму и проверять текущее значение и как далеко тот максимум отехал. Если дальше N то искать заново. Но если хранить например отсортированный мини массив. И после того как максимум уехал, просто брать из этого массива.
и где гарантия что то что будет вытащено из массива не уехало еще дальше?

Re: Скользящий поиск максимума?

От:

Lloyd

Дата:

02.06.11 12:29

Оценка:

Можно разбить весь массив на куски одинаковой длины n. Для кажого куска хранить максимум.
Тогда по интервалу [i-N, i] будет равен максимальному из
1) максимума по куску, куда попал i-N,
2) максимум из максимумов кусков, попавших в [i-N, i]

Например, если размер куска выберем 10, а N = 100, то нужно будет хранить 10 последних максимумов кусков + при вычислении вычислять максимум из 10 кусков + максимумов из первого куска (<= 10 элементов). Т.е. 100 сравнений в случае реализации в лоб уменьшили в 5 раз.

Re[3]: Скользящий поиск максимума?

	От:	denisko	http://sdeniskos.blogspot.com/
Дата:	02.06.11 12:36
	Оценка:

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, denisko, Вы писали:

D>>Здравствуйте, Аноним, Вы писали:

А>>>Есть ряд значений данных в виде даблов, их много.

А>>>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?

D>>Ну использование дерева даст логарифм вместо линейного поиска. Или тебе надо за константу?

А>Ну тут надо еще и как-то не сильно по обьему раздуться.
Ну если ты хранишь пирамиду / дерево, то раздуется максимум в logN. Стратегия поиска в общем случае для каждого участка длины M такая — находишь максимум на нем, если точка, в которой он достигается в нужном тебе интервале, то останавливаешься, нет берешь максимумы с того подучастка длины M2 который перекрывается с твоим интервалом. Максимумы ищешь в предобработке. Оверхед по размеру log M.

<Подпись удалена модератором>

Re: Скользящий поиск максимума?

	От:	Аноним
Дата:	02.06.11 13:22
	Оценка:

А вот это не подойдет?
Задача нахождения максимума на отрезках фиксированной длины
http://habrahabr.ru/blogs/algorithm/116236/

Re[2]: Скользящий поиск максимума?

	От:	Аноним
Дата:	02.06.11 13:35
	Оценка:

Здравствуйте, Аноним, Вы писали:

А>А вот это не подойдет?
А>Задача нахождения максимума на отрезках фиксированной длины
А>http://habrahabr.ru/blogs/algorithm/116236/

Увы памяти надо много.

Re[2]: Скользящий поиск максимума?

От:

Vintik_69

Дата:

02.06.11 18:31

Оценка:

Здравствуйте, MBo, Вы писали:

MBo>Время амортизированное O(1).

Ага, есть еще одна вариация: делаем стек с максимумами (очевидно как), потом из двух стеков делаем очередь. Получается та же амортизированая константа и O(N) по памяти.

Re[3]: Скользящий поиск максимума?

	От:	MBo
Дата:	03.06.11 02:33
	Оценка:

Здравствуйте, Vintik_69, Вы писали:

V_>Ага, есть еще одна вариация: делаем стек с максимумами (очевидно как), потом из двух стеков делаем очередь. Получается та же амортизированая константа и O(N) по памяти.

По памяти О(размер окна)

Re[2]: Скользящий поиск максимума?

	От:	Аноним
Дата:	03.06.11 06:17
	Оценка:

Здравствуйте, MBo, Вы писали:

А>>Есть ряд значений данных в виде даблов, их много.

А>>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?

MBo>Используем дек (Deque), в котором хранятся структуры (значение, номер)

Молодцы! То есть если по короче изложить и понятнее изложить , то все точно так же как и всегда но вместо одного максимума имеем стек максимумов. И по мере движения окна на один шаг, если входящий элемент больше максимума то пушим его на вершину стека. Если входящий больше элемента в N в стеке то заменяем его в стеке. Если из онка уходит тот что лежит на вершине стека максимумов, то попим его со стека и на вершине оказывается максимум который был до него или который поднялся с низу.

Но интуиция что-то подсказала что тут что-то не то. Все вроде логично. Но дорисуйте картинку в соответсвии с вашим алгоритмом.

13254735 01293857

       7 77 
       5 55
       5 55
       4 44
       3 3 
       3 3 
       2 2
       1 0

На самом деле придется вставлять в отсортированный стек новые, это не трудно и вы описали. Но до того придется искать в нем и удалять уходящие из окна элементы.

Re: Скользящий поиск максимума?

	От:	__kot2
Дата:	03.06.11 08:47
	Оценка:

Здравствуйте, Аноним, Вы писали:
А>Есть ряд значений данных в виде даблов, их много.
самый тупой вариант может быть не так уж и плох
вот у нас есть некий список. он составляется так
берем элемент X пробегаем список так, что все меньшие X или дальше от него чем N удаляем, вставляем X в этот списочек
максимум это максимум списка (который считаем одновременно). матожидание длины списка — ln N, если не ошибаюсь. но, конечно постоянно убывающая последовательность превратит его длину в N

Re[5]: Скользящий поиск максимума?

	От:	MBo
Дата:	03.06.11 13:07
	Оценка:

Здравствуйте, Аноним, Вы писали:

А>Да не будет работать. Вроде же обьяснил
Наверно, кто-то не прочитал описание алгоритма, а осуществлял логические построения на основе собственных соображений.

А>Кто ббудет из средины удалять уходящие?
В алгоритме, приведенном мной, из середины ничего не удаляется, да и структура дека этого вообще не предусматривает.

A> Возмите массив по длиннее и окно на 10 ячеек. Я привел пример.

Я могу сделать выдачи алгоритма на любой длине на нескольких наборах данных.
Вот 30/10. Длиннее, видимо, не стоит, т.к. тега спойлера, чтобы упрятать эту простыню, я не вижу, да и проверять глазами не так просто становится.


Окно размером 10 на массиве 
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15 
--------------------
[14]23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 14   DeqSize: 1
[14 23]21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 1
[14 23 21] 7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 2
[14 23 21  7] 9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 3
[14 23 21  7  9] 8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 3
[14 23 21  7  9  8]12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 4
[14 23 21  7  9  8 12]16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 3
[14 23 21  7  9  8 12 16] 4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 3
[14 23 21  7  9  8 12 16  4] 9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 4
[14 23 21  7  9  8 12 16  4  9]25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 23   DeqSize: 4
 14[23 21  7  9  8 12 16  4  9 25]11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 1
 14 23[21  7  9  8 12 16  4  9 25 11] 4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 2
 14 23 21[ 7  9  8 12 16  4  9 25 11  4]22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 3
 14 23 21  7[ 9  8 12 16  4  9 25 11  4 22] 1 21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 2
 14 23 21  7  9[ 8 12 16  4  9 25 11  4 22  1]21  8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 3
 14 23 21  7  9  8[12 16  4  9 25 11  4 22  1 21] 8  1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 3
 14 23 21  7  9  8 12[16  4  9 25 11  4 22  1 21  8] 1  6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 4
 14 23 21  7  9  8 12 16[ 4  9 25 11  4 22  1 21  8  1] 6 10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 5
 14 23 21  7  9  8 12 16  4[ 9 25 11  4 22  1 21  8  1  6]10 11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 5
 14 23 21  7  9  8 12 16  4  9[25 11  4 22  1 21  8  1  6 10]11 17 24 26  7 26  5 27 17 15     WinMax: 25   DeqSize: 4
 14 23 21  7  9  8 12 16  4  9 25[11  4 22  1 21  8  1  6 10 11]17 24 26  7 26  5 27 17 15     WinMax: 22   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11[ 4 22  1 21  8  1  6 10 11 17]24 26  7 26  5 27 17 15     WinMax: 22   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4[22  1 21  8  1  6 10 11 17 24]26  7 26  5 27 17 15     WinMax: 24   DeqSize: 1
 14 23 21  7  9  8 12 16  4  9 25 11  4 22[ 1 21  8  1  6 10 11 17 24 26] 7 26  5 27 17 15     WinMax: 26   DeqSize: 1
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1[21  8  1  6 10 11 17 24 26  7]26  5 27 17 15     WinMax: 26   DeqSize: 2
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21[ 8  1  6 10 11 17 24 26  7 26] 5 27 17 15     WinMax: 26   DeqSize: 2
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8[ 1  6 10 11 17 24 26  7 26  5]27 17 15     WinMax: 26   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1[ 6 10 11 17 24 26  7 26  5 27]17 15     WinMax: 27   DeqSize: 1
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6[10 11 17 24 26  7 26  5 27 17]15     WinMax: 27   DeqSize: 2
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10[11 17 24 26  7 26  5 27 17 15]    WinMax: 27   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11[17 24 26  7 26  5 27 17 15]    WinMax: 27   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17[24 26  7 26  5 27 17 15]    WinMax: 27   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24[26  7 26  5 27 17 15]    WinMax: 27   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26[ 7 26  5 27 17 15]    WinMax: 27   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7[26  5 27 17 15]    WinMax: 27   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26[ 5 27 17 15]    WinMax: 27   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5[27 17 15]    WinMax: 27   DeqSize: 3
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27[17 15]    WinMax: 17   DeqSize: 2
 14 23 21  7  9  8 12 16  4  9 25 11  4 22  1 21  8  1  6 10 11 17 24 26  7 26  5 27 17[15]    WinMax: 15   DeqSize: 1

Re: Скользящий поиск максимума?

	От:	Rustavelli
Дата:	08.06.11 09:27
	Оценка:

Пусть мы имеем n данных V[i], i=0..n-1
Дополнительно будем использовать _циклический буфер_ индексов максимумов размером N: M[]
На каждом шаге i будем добавлять в M[] индекс элемента, являющего максимумом на отрезке i..i-N,
(т.е. если V[] содержит отсортированный по возрастанию список, то в M[] на i-м шаге будет добавляться i,
а если V[] содержит отсортированный по убыванию список, то в M[] на i-м шаге будет добавляться i-N.)
Теперь как узнать, какой же индекс добавлять в цикл.буфер на каждом шаге.
На каждом шаге i:
1) смотрим, M[i-1]<i-n? Т.е. находится ли максимум предыдущего шага за пределами окна? , где M[i-1] — индекс максимума, добавленный на предыдущем шаге.
1.1) Y, вышел. Надо найти максимум среди N элементов V[j], j=i-N..i
1.2) N, находится в окне, сравниваем V[i] и V[M[i-1]]
1.2.1) V[i]>V[M[i-1]] — новый максимум, тогда M[i]=i
1.2.2) V[i]<=V[M[i-1]] — старый максимум, тогда M[i]=M[i-1]

Типа того.. осталось подумать, как лучше выполнить шаг 1.1, т.е. можно ли тупо искать максимум среди N предыдущих или можно тоже оптимиздить. Зависит от требований.
Итого:
доп.память: циклический буфер размером N
по трудоемкости сложно оценить, зависит от вида исходных данных. Худший случай — отсортированный список или плавно изменяющиеся данные (например синусоида с большим периодом).

Re[6]: Скользящий поиск максимума?

	От:	Rustavelli
Дата:	08.06.11 10:33
	Оценка:

Здравствуйте, MBo, Вы писали:

A>> Возмите массив по длиннее и окно на 10 ячеек. Я привел пример.
MBo>Я могу сделать выдачи алгоритма на любой длине на нескольких наборах данных.
MBo>Вот 30/10. Длиннее, видимо, не стоит, т.к. тега спойлера, чтобы упрятать эту простыню, я не вижу, да и проверять глазами не так просто становится.

А зачем проверять работу алгоритма на больших данных? Наоборот, надо проверить на самых простых или вырожденных случаях:
* массив отсортирован в одну или другу сторону
* четные элементы по возрастанию, нечетные — по уменьшению
* массив размером 1, 2, и больше
* окно размером 1, 2 и больше
* все значения одинаковые
итд

А потом уже проверять на приближенных к реальным данных.

Re[7]: Скользящий поиск максимума?

	От:	Аноним
Дата:	08.06.11 10:35
	Оценка:

Здравствуйте, Rustavelli, Вы писали:

R>А потом уже проверять на приближенных к реальным данных.

Алгоритм ОТЛИЧНЫЙ, я просто не написал, что был не прав. Так что постеру респект.

Re[2]: Скользящий поиск максимума?

	От:	Аноним
Дата:	08.06.11 11:36
	Оценка:

Здравствуйте, MBo, Вы писали:

Еще немного «проблем».
Дело в том, что к этой функции поиска максимума, обращаются одновременно несколько других функций и причем к тем же точно данным, разница только состоит в том, что размер окна у них разная. Ну например 1000 разных размеров окон, от скажем 30 до 5000. Вот теперь думаю как бы так изменить алгоритм чтобы не повторять ту же самую работу, ведь максимум в большей части запросов будет то же самый.

Что посоветуете?

Re[3]: Скользящий поиск максимума?

	От:	MBo
Дата:	08.06.11 12:52
	Оценка:

Логика разделяется на две части — то, что зависит от номера элемента и соответственно от размера окна, и то, что зависит от значения элемента.
Первое работает с головой дека, второе — с хвостом.

От размера окна зависит удаление из передней части дека старых элементов, и запрос максимума.
От значения — удаление с хвоста.

Тогда добавление элемента — подчищаем хвост, вставляем его.

Подчищать голову нельзя, но, похоже, нужный эффект получится, если элементы с головы не удалять физически, а для каждого размера окна поддерживать актуальный именно для него указатель на виртуальную голову дека — он будет модифицироваться, продвигаясь сквозь старые для данного окна элементы.

Re[6]: Скользящий поиск максимума?

	От:	Anna111
Дата:	28.11.11 17:21
	Оценка:

Здравствуйте, MBo, Вы писали:

MBo>Я могу сделать выдачи алгоритма на любой длине на нескольких наборах данных.

MBo>Вот 30/10. Длиннее, видимо, не стоит, т.к. тега спойлера, чтобы упрятать эту простыню, я не вижу, да и проверять глазами не так просто становится

Можете мне помочь с кодом для подобной задачи? Я на связи sberex@mail.ru

Re[7]: Скользящий поиск максимума?

От:

Senyai

http://www.arseniy.net

Дата:

28.11.11 17:50

Оценка:

A>Можете мне помочь с кодом для подобной задачи? Я на связи sberex@mail.ru

Да вы тут спрашивайте.

Re: Скользящий поиск максимума?

От:

batu

Дата:

28.11.11 18:51

Оценка:

Глупо бегать, конечно. После первой сортировки создаем отсортированый массив Z из N элементов (Их индексы, конечно)
На в следующкм шагу опять сортируем уже отсортированый массив Z без i-го элемента, но с новым элементом i-n-1 (ну, тут сам вычислишь индекс следующего.. Как-то нумерация не совсем мне понятна,но видимо так поставлена задача))
В принципе если максимум остается в диапазоне, то достаточно просто проверить сменился он или нет сравнивая его с новым элементом, но проблемы могут возникнуть когда максимум выходит из диапазона. Тогда прийдется сортировать весь диапазон. Потому критерием должно быть сравнение скоростей либо полной сортировки иногда (тогда когда максимум выходит из диапазона) дибо корректировать на каждом шаге массив Z.

Re[2]: Скользящий поиск максимума?

От:

batu

Дата:

28.11.11 19:00

Оценка:

Здравствуйте, batu, Вы писали:

Единственно, что могу добавить Z может быть списком или стеком.. для некоторых случаев это будет эффективней чем массив.

Re[3]: Скользящий поиск максимума?

От:

batu

Дата:

28.11.11 19:05

Оценка:

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, MBo, Вы писали:

А>Еще немного «проблем».
А>Дело в том, что к этой функции поиска максимума, обращаются одновременно несколько других функций и причем к тем же точно данным, разница только состоит в том, что размер окна у них разная. Ну например 1000 разных размеров окон, от скажем 30 до 5000. Вот теперь думаю как бы так изменить алгоритм чтобы не повторять ту же самую работу, ведь максимум в большей части запросов будет то же самый.

А>Что посоветуете?
Нифига не поможет. Для каждого размера окна нужно будте создавать свой массив Z. Единственная радость так то, что первые элементы этих массивов (а они будут разные для каждого i) будут совпадать. Можно воспользоваться этим фактом или нет зависит от задачи. Во всяком случае если их хранить, то это памяти много понадобится..

Re: Скользящий поиск максимума?

	От:	opener
Дата:	01.12.11 08:44
	Оценка:

Торговый советник пишешь?

Re[2]: Скользящий поиск максимума?

От:

TimurSPB

Дата:

01.12.11 15:27

Оценка:

MBo>Время амортизированное O(1).
А не слишком ли сильно оно будет амортизировано?

Make flame.politics Great Again!

Re: Скользящий поиск максимума?

От:

TimurSPB

Дата:

01.12.11 15:32

Оценка:

maximum = Array[ 0 ]; 
maximum_position = 0;
for ( i = ....
{
  if( maximum < Array[i] )
  {
     maximum = Array[i];
     maximum_position = i; 
  }
  if ( i — maximum_position > N ) //текущий максимум вылетел за текущий интервал
  {
     for( j = i — N + 1... // Обычный поиск нового максимума в последних N элементах
       maximum = max( maximum, Array[ j ] ); 
  }
}

Т.е. делать полный последовательный поиск надо только тогда, когда текущий максимум вышел за границы интервала. Если значения только возрастают, то всё сведется к простому сравнению maximum = max( maximum, Array[ j ] ); Если только убывают, то будет поиск максимума в цикле по последним N элементам.

Make flame.politics Great Again!

Re[3]: Скользящий поиск максимума?

От:

Vintik_69

Дата:

01.12.11 18:39

Оценка:

Здравствуйте, TimurSPB, Вы писали:

TSP>А не слишком ли сильно оно будет амортизировано?

Расшифруй.

Wait...

Переместить
Удалить
Выделить ветку

Пока на собственное сообщение не было ответов, его можно удалить.

Источник