Алгоритм поиска наибольшего среднего арифметического некой последовательности
Имеем массив Muss[1000] рандомных значений (min = -100, max =100).
Нужно найти последовательность, длина которой не короче n = 45 элементов,
чтобы среднее арифметическое элементов найденной последоавательности было наибольшим из всех возможных вариантов последовательностей.
Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.
Хотелось бы находить за линейную скорость, но как?
отсортировать, найти среднее арифметической нужного количества элементов с большего края массива, наверное это значение и будет "наибольшим из всех возможных вариантов последовательностей".
Если конечно я правильно понял задачу.
ЗЫ: нет похоже задачу я понял не правильно
Посидел подумал, про то как будет выглядеть график зависимости максимального среднеарифметического значения от количеств элементов.
Прикинул что это типа затухающей синусоиды под углом -45 градусов.
Проверил в exel (увы не знаком с VB, пришлось ручками).
Справа то что нарисовал до проверки - слева один из результатов рандомной генерации
Сейчас уточню условие, так как мог непонятно описать:
нужно из большого массива выбрать подряд лежащие элементы ( но не меньше n= 20 штук чтобы было подряд) может быть n=100, n=101 ...
не важно как выбрать, главное чтобы среднее значение было больше остальных вариантов выбора последовательности.
Среднее значение - это сума подряд лежащих элементов разделенная на их количество.
>>>>Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.
Да доли миллисекунды это )))
НомерПервогоЭлемента=0
МаксЗнач=0
Цикл повторяется РазмерМассива - КолЭлементовСложения
в каждой итерации суммируем все КолЭлементовСложения с очередного номера элементов в массиве, делим на КолЭлементовСложения
Если Результат > МаксЗнач, то МаксЗнач=Результат, запоминаем НомерПервогоЭлемента из КолЭлементовСложения на текущей итерации.
Продолжаем цикл.
По завершении цикла имеем номер элемента буфера, с которого будет наибольшее среднее МаксЗнач
==
Всё это работает быстрее чем я печатаю одну букву )))
делать сложение элементов так:
- s
- s+s
- s+s+s
- s+s+s+s
- s+s+s+s+s
- s+s+s+s+s+s
- s+s+s+s+s+s+s
- s+s+s+s+s+s+s+s
- s+s+s+s+s+s+s+s+s
- s+s+s+s+s+s+s+s+s+s
далее ищем максимальную разность между (i+n) и i, где i- итерация, n-количество элементов в последовательности.
дальше думаю понятно.
>>>>Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.
Да доли миллисекунды это )))
НомерПервогоЭлемента=0
МаксЗнач=0
Цикл повторяется РазмерМассива - КолЭлементовСложения
в каждой итерации суммируем все КолЭлементовСложения с очередного номера элементов в массиве, делим на КолЭлементовСложения
Если Результат > МаксЗнач, то МаксЗнач=Результат, запоминаем НомерПервогоЭлемента из КолЭлементовСложения на текущей итерации.
Продолжаем цикл.
По завершении цикла имеем номер элемента буфера, с которого будет среднее МаксЗнач
==
Всё это работает быстрее чем я печатаю одну букву )))
да, так будет даже быстрее чем предложил я )
ЗЫ: хотя ХЗ, суммировать и одновременно искать разность между полученной суммой и суммой (i-n)элементов, второй массив по любому нужен, тогда только один проход по массиву
Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.
При длине массива 2000 и минимальной длине последовательности n = 20; и при повторении задачи всего 40000 раз
считается все весьма плачевно.
Как посчитать я знаю, реализовал, посчитал - меня скорость не устраивает, должно быть проще решение чем в тупую.
Вот и спрашиваю идеи по этому поводу.
Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.
При длине массива 2000 и минимальной длине последовательности n = 20; и при повторении задачи всего 40000 раз
считается все весьма плачевно.
Как посчитать я знаю, реализовал, посчитал - меня скорость не устраивает, должно быть проще решение чем в тупую.
Вот и спрашиваю идеи по этому поводу.
При длине массива 2000 и n=20 цикл повторится всего 1980 раз.
У меня Арбитражные сканеры выполняют в сотни если не тысячи раз больше вычислений по каждому инструменту у брокера, с анализом тысячи баров в историю, в каждую секунду Таймера.... не замечаю тормозов...
При длине массива 2000 и n=20 цикл повторится всего 1980 раз.
У меня Арбитражные сканеры выполняют в сотни если не тысячи раз больше вычислений по каждому инструменту у брокера, с анализом тысячи баров в историю, в каждую секунду Таймера.... не замечаю тормозов...
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования
Имеем массив Muss[2000] рандомных значений (min = -100, max =100).
Нужно найти последовательность, длина которой не короче n = 20 элементов,
чтобы среднее арифметическое элементов найденной последоавательности было наибольшим из всех возможных вариантов последовательностей.
Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи 40 000 раз.
Хотелось бы находить за линейную скорость или логарифмическую, но как?