Re[5]: Скользящий поиск максимума? - Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Незнаю.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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

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

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

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

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

  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

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

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

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

Да не будет работать. Вроде же обьяснил

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

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

А>Да не будет работать. Вроде же обьяснил

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

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

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

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

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

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

Пусть мы имеем 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
по трудоемкости сложно оценить, зависит от вида исходных данных. Худший случай — отсортированный список или плавно изменяющиеся данные (например синусоида с большим периодом).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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