Здравствуйте, Аноним, Вы писали:
А>Есть ряд значений данных в виде даблов, их много.
А>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?
Используем дек (Deque), в котором хранятся структуры (значение, номер)
Если номер переднего элемента очереди — тот, что уходит из окна, то удаляем его из начала очереди.
Удаляем из конца очереди элементы, значение которых меньше, чем у новодобавляемого, и которые уже никогда не будут максимумами
Вставляем новый элемент в конец очереди
Максимум на каждом шаге — в начале очереди.
Время амортизированное O(1).
Здравствуйте, cvetkov, Вы писали:
C>Здравствуйте, <Аноним>, Вы писали:
А>>Пока на первый взгляд кажется, что если запоминать номер максимуму и проверять текущее значение и как далеко тот максимум отехал. Если дальше N то искать заново. Но если хранить например отсортированный мини массив. И после того как максимум уехал, просто брать из этого массива. C>и где гарантия что то что будет вытащено из массива не уехало еще дальше?
Незнаю. Поэтому и спрашиваю. Честно? Как-то думать уж очень надоело. Все думашь-думашь, где бы такую работу найти чтобы не думать? И получать нормально. А думать о рыбалке.
А>Но интуиция что-то подсказала что тут что-то не то. Все вроде логично. Но дорисуйте картинку в соответсвии с вашим алгоритмом.
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; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?
Здравствуйте, Аноним, Вы писали:
А>Есть ряд значений данных в виде даблов, их много.
А>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?
Ну использование дерева даст логарифм вместо линейного поиска. Или тебе надо за константу?
<Подпись удалена модератором>
Re[2]: Скользящий поиск максимума?
От:
Аноним
Дата:
02.06.11 12:07
Оценка:
Здравствуйте, denisko, Вы писали:
D>Здравствуйте, Аноним, Вы писали:
А>>Есть ряд значений данных в виде даблов, их много.
А>>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?
D>Ну использование дерева даст логарифм вместо линейного поиска. Или тебе надо за константу?
Ну тут надо еще и как-то не сильно по обьему раздуться.
Пока на первый взгляд кажется, что если запоминать номер максимуму и проверять текущее значение и как далеко тот максимум отехал. Если дальше N то искать заново. Но если хранить например отсортированный мини массив. И после того как максимум уехал, просто брать из этого массива.
Здравствуйте, <Аноним>, Вы писали:
А>Пока на первый взгляд кажется, что если запоминать номер максимуму и проверять текущее значение и как далеко тот максимум отехал. Если дальше N то искать заново. Но если хранить например отсортированный мини массив. И после того как максимум уехал, просто брать из этого массива.
и где гарантия что то что будет вытащено из массива не уехало еще дальше?
Здравствуйте, Аноним, Вы писали:
А>Есть ряд значений данных в виде даблов, их много.
А>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( 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 раз.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, denisko, Вы писали:
D>>Здравствуйте, Аноним, Вы писали:
А>>>Есть ряд значений данных в виде даблов, их много.
А>>>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?
D>>Ну использование дерева даст логарифм вместо линейного поиска. Или тебе надо за константу?
А>Ну тут надо еще и как-то не сильно по обьему раздуться.
Ну если ты хранишь пирамиду / дерево, то раздуется максимум в logN. Стратегия поиска в общем случае для каждого участка длины M такая -- находишь максимум на нем, если точка, в которой он достигается в нужном тебе интервале, то останавливаешься, нет берешь максимумы с того подучастка длины M\2 который перекрывается с твоим интервалом. Максимумы ищешь в предобработке. Оверхед по размеру log M.
Здравствуйте, MBo, Вы писали:
MBo>Время амортизированное O(1).
Ага, есть еще одна вариация: делаем стек с максимумами (очевидно как), потом из двух стеков делаем очередь. Получается та же амортизированая константа и O(N) по памяти.
Здравствуйте, 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 в стеке то заменяем его в стеке. Если из онка уходит тот что лежит на вершине стека максимумов, то попим его со стека и на вершине оказывается максимум который был до него или который поднялся с низу.
Но интуиция что-то подсказала что тут что-то не то. Все вроде логично. Но дорисуйте картинку в соответсвии с вашим алгоритмом.
На самом деле придется вставлять в отсортированный стек новые, это не трудно и вы описали. Но до того придется искать в нем и удалять уходящие из окна элементы.
Здравствуйте, Аноним, Вы писали: А>Есть ряд значений данных в виде даблов, их много.
самый тупой вариант может быть не так уж и плох
вот у нас есть некий список. он составляется так
берем элемент X пробегаем список так, что все меньшие X или дальше от него чем N удаляем, вставляем X в этот списочек
максимум это максимум списка (который считаем одновременно). матожидание длины списка — ln N, если не ошибаюсь. но, конечно постоянно убывающая последовательность превратит его длину в N
Здравствуйте, Аноним, Вы писали:
А>Да не будет работать. Вроде же обьяснил
Наверно, кто-то не прочитал описание алгоритма, а осуществлял логические построения на основе собственных соображений.
А>Кто ббудет из средины удалять уходящие?
В алгоритме, приведенном мной, из середины ничего не удаляется, да и структура дека этого вообще не предусматривает.
A> Возмите массив по длиннее и окно на 10 ячеек. Я привел пример.
Я могу сделать выдачи алгоритма на любой длине на нескольких наборах данных.
Вот 30/10. Длиннее, видимо, не стоит, т.к. тега спойлера, чтобы упрятать эту простыню, я не вижу, да и проверять глазами не так просто становится.
Здравствуйте, Аноним, Вы писали:
А>Есть ряд значений данных в виде даблов, их много.
А>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( 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 и больше
* все значения одинаковые
итд
А потом уже проверять на приближенных к реальным данных.
Re[7]: Скользящий поиск максимума?
От:
Аноним
Дата:
08.06.11 10:35
Оценка:
Здравствуйте, Rustavelli, Вы писали:
R>А потом уже проверять на приближенных к реальным данных.
Алгоритм ОТЛИЧНЫЙ, я просто не написал, что был не прав. Так что постеру респект.
Re[2]: Скользящий поиск максимума?
От:
Аноним
Дата:
08.06.11 11:36
Оценка:
Здравствуйте, MBo, Вы писали:
Еще немного "проблем".
Дело в том, что к этой функции поиска максимума, обращаются одновременно несколько других функций и причем к тем же точно данным, разница только состоит в том, что размер окна у них разная. Ну например 1000 разных размеров окон, от скажем 30 до 5000. Вот теперь думаю как бы так изменить алгоритм чтобы не повторять ту же самую работу, ведь максимум в большей части запросов будет то же самый.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, MBo, Вы писали:
А>Еще немного "проблем". А>Дело в том, что к этой функции поиска максимума, обращаются одновременно несколько других функций и причем к тем же точно данным, разница только состоит в том, что размер окна у них разная. Ну например 1000 разных размеров окон, от скажем 30 до 5000. Вот теперь думаю как бы так изменить алгоритм чтобы не повторять ту же самую работу, ведь максимум в большей части запросов будет то же самый.
А>Что посоветуете?
Логика разделяется на две части — то, что зависит от номера элемента и соответственно от размера окна, и то, что зависит от значения элемента.
Первое работает с головой дека, второе — с хвостом.
От размера окна зависит удаление из передней части дека старых элементов, и запрос максимума.
От значения — удаление с хвоста.
Тогда добавление элемента — подчищаем хвост, вставляем его.
Подчищать голову нельзя, но, похоже, нужный эффект получится, если элементы с головы не удалять физически, а для каждого размера окна поддерживать актуальный именно для него указатель на виртуальную голову дека — он будет модифицироваться, продвигаясь сквозь старые для данного окна элементы.
MBo>Я могу сделать выдачи алгоритма на любой длине на нескольких наборах данных. MBo>Вот 30/10. Длиннее, видимо, не стоит, т.к. тега спойлера, чтобы упрятать эту простыню, я не вижу, да и проверять глазами не так просто становится
Можете мне помочь с кодом для подобной задачи? Я на связи sberex@mail.ru
Здравствуйте, Аноним, Вы писали:
А>Есть ряд значений данных в виде даблов, их много.
А>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( i) до ( i-N ). То есть надо находить максимум в массиве их N значений. Но так как текущее значение смещается то как-то глупо бегать назад и искать максимум. Например расчет среднего делается в режиме sum -= Array[i-N]; sum += Array[i] ; sum /=N; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?
Глупо бегать, конечно. После первой сортировки создаем отсортированый массив Z из N элементов (Их индексы, конечно)
На в следующкм шагу опять сортируем уже отсортированый массив Z без i-го элемента, но с новым элементом i-n-1 (ну, тут сам вычислишь индекс следующего.. Как-то нумерация не совсем мне понятна,но видимо так поставлена задача))
В принципе если максимум остается в диапазоне, то достаточно просто проверить сменился он или нет сравнивая его с новым элементом, но проблемы могут возникнуть когда максимум выходит из диапазона. Тогда прийдется сортировать весь диапазон. Потому критерием должно быть сравнение скоростей либо полной сортировки иногда (тогда когда максимум выходит из диапазона) дибо корректировать на каждом шаге массив Z.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, MBo, Вы писали:
А>Еще немного "проблем". А>Дело в том, что к этой функции поиска максимума, обращаются одновременно несколько других функций и причем к тем же точно данным, разница только состоит в том, что размер окна у них разная. Ну например 1000 разных размеров окон, от скажем 30 до 5000. Вот теперь думаю как бы так изменить алгоритм чтобы не повторять ту же самую работу, ведь максимум в большей части запросов будет то же самый.
А>Что посоветуете?
Нифига не поможет. Для каждого размера окна нужно будте создавать свой массив Z. Единственная радость так то, что первые элементы этих массивов (а они будут разные для каждого i) будут совпадать. Можно воспользоваться этим фактом или нет зависит от задачи. Во всяком случае если их хранить, то это памяти много понадобится..
Здравствуйте, Аноним, Вы писали:
А>Есть ряд значений данных в виде даблов, их много.
А>Мы их просматриваем от начала и до конца в цикле. В этом цикле в процессе просмотра надо определять максимум в интервале от текущего значения ( 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; То есть считается скользящая сумма. А тут как быть. Как находить максимум по такому же принципу?
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 элементам.
Поэтому и спрашиваю. Честно? Как-то думать уж очень надоело. Все думашь-думашь, где бы такую работу найти чтобы не думать? И получать нормально. А думать о рыбалке. 
