Поиск максимума и минимума

Booster

в алгосе незаметно, что там выбрасываются элементы, если это так, то понятен такой прирост, но это вероятностный алгос - где такая жесть нужна - это новая загадка)

 

Yashin_Sergey

вопрос: сущесвует ли в массиве хотя бы один элемент, который ты нисчем не сравниваешь???

 

Он не ВЕРОЯТНОСТНЫЙ )))

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

Смотри:

1. находим мин. макс.
2. переходим к новому элементу.
3. вышли прошлые мин. или макс. за границу плавающего окна ?
3.1 если вышли: заново находим мин. макс. из 10 тыс. соседних элементов.
3.2 если не вышли: сравниваем новый элемент: больше макс. значит это новый макс., меньше мин. значит это новый мин.


в пункте 3.2. не выполняется цикл по 10 тыс. соседним эелементам ЭТО НЕ ЗАМЕТНО ?

я с лет 4-5 умею читать, а может и раньше )) уже не помню.

 

Конечно есть ))
и их мноооого ))
очень много.... очень очень. и при этом сравнивать с ними необходимость отпадает.

Тебе вобще зачем надо то всё это ? копить алгоритмы или времени много тратить на то, что бы доказать обратное ?

2 * 2 = 4, .... докажи обратное тогда я поспорю.

 

Yashin_Sergey
Уже спрашивал #69.
Интересно в каком виде у вас результат.

 

UbIvItS

Что-то я не догнал товой однопроходный алгос, там же вроде нету пересечений диапазонов?

Yashin_Sergey
Твой алгоритм смахивает на Бойера-Мура для нахождения подстрок. И его можно улучшить, так же как есть несколько вариантов Бойера-Мура. А объясняешь ты действильно странно:

IMHO 3. вышли прошлые позиции мин. или макс. элементов за границу плавающего окна ?
IMHO надо так, а иначе не сразу врубаешься о чём это.
Или может я чего тоже не понимаю?

 

Всё верно, но уж простите, кому как доходчивее - не разберешь, да и описание - вольное а не подробное.

 

В результате получается максимумов 190 тыс. и столько же минимумов.
почему 190 тыс. ? потому что, максимум и минимум мы ищем по 10 тыс. соседним элементам.

соседние это элементы с меньшими индексами по массиву т.е.

1, 2, 3, 4, 5

у элемента "5", элементы 1, 2, 3,4 - соседние.


Про вид результата - не понял.

Вы имели ввиду что из себя результат представляет ?

Это индикатор для ценового потока, в итоге представляет из себя график.

 

Yashin_Sergey
Так и понял, что для потоковой обработки. Длинный однако график.
Разве не проще хранить индексы измененных крайних значений. Или исходные данные затираются?

 

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

 

Yashin_Sergey
Пусть дана последовательность: 1, 5, 3, 3, 4, 8. Размер окна 2.
1) [1, 5] мин.=1 макс.=5; записываем в ИндексМин[1] = 1, ИндексМакс[1] = 2;
2) [5, 3] мин.=1 макс.=5; ничего не записываем;
3) [3, 3] мин.=1 макс.=5; ничего не записываем;
4) [3, 4] мин.=1 макс.=5; ничего не записываем;
5) [4, 8] мин.=1 макс.=8; дописываем в ИндексМакс[2] = 6.
Итого: ИндексМин = [1], ИндексМакс = [2, 6].

Преимущества:
Сократится размер массивов с мин. и макс. на порядок и соответственно обработка этих массивов.
Проще масштабировать график.

 

Спасибо.

Я приблизительно так и делаю.

 

Booster

там нет ничего сложного скопируй себе и запусти
Yashin_Sergey
скажи какое у тебя суммарное колво итераций - считай на нижнем цикле, плззззз

 

UbIvItS

Я вообще-то в курсе. -).
Просто в твоём алгосе идёт разбивка на диапазоны без пересечений. А задача как раз с пересечениями.

 

Booster
мда, так что значит соседний элемент??

 

UbIvItS

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

 

Booster
твоё понимание задачи верно - я ошибался: мой алгос и, впрямь, не катит)

 

я подумаю как его в один цикл организовать - интересная задача)

 

Мда, развели дискуссию...
UbIvItS, похоже ты уперся в неверное понимание статистического\вероятностного алгоритма. Я ведь уже пояснял
1) Алгоритм м.б. детерминированным, но использоваться для статистических задач, например, формула расчета выборочного среднего, или выборочной дисперсии. Попутно для ясности скажу о скользящем окне - можно брать независимые оценки дисперсии на непересекающихся интервалах в 10тыс.отсчетов. Но если процесс нестационарный и его дисперсия изменяется во времени, то мы будем получать какие-то случайные значения через большие интервалы времени, не зная как изменяется дисперсия внутри интервала. В этом случае можно искать дисперсию в скользящем окне, тогда на выходе будем иметь график плавного изменения дисперсии. В данном случае задача точно такая же, только вместо дисперсии нужно определять Min и Max значения, которые характеризуют максимальный разброс (размах) значений на выборочном интервале.

2) Алгоритм м.б. детерминированным, но время расчета может быть случайным, зависящим от статистики распределения обрабатываемых величин. Я уже приводил пример c Бойером-Муром. Но даже при использовании самого тупого поиска строки с поиском первого символа и ипользованием условных переходов время поиска будет существенно зависеть от того насколько часто и регулярно попадается первый символ в тексте из-за того, что предсказанный условный переход или непереход выполняется на современных компах за 0-1 такт, а непредсказанный за 10-30 тактов в зависимости от проца.

Резюме: Рассматриваемый алгос является детерминированным, он производит сравнение каждого нового элемента хотя бы один раз и результат получает совершенно однозначно без всяких там "с вероятностью ...". Но время обработки ес-но зависит от распределения величин в массиве - на монотонном росте или спаде ес-но будут тормоза, но при наличии экстремумов на интервале 10тыс. в любом случае будет выигрыш, т.к. если на i-м шаге мы нашли Min и Max, ближайший из которых находится например на позиции +1000 от начала текущего окна, то мы гарантированно эти 1000 шагов пройдем без повторного пересчета, а если к тому же за эти 1000 шагов справа в окно влезут другие значения Min\Max, которые перепишут старые значения, то и еще 8-9тыс шагов пройдем без повторных пересчетов. Поэтому в полученном выигрыше в сотню с небольшим раз ничего удивительного нет

 

leo
Согласен полностью. Просто сразу не вникнув в суть вопроса (с решением - скользящее окно), выдал

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