Еще немного "проблем".
Дело в том, что к этой функции поиска максимума, обращаются одновременно несколько других функций и причем к тем же точно данным, разница только состоит в том, что размер окна у них разная. Ну например 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 элементам.
