Скачать MetaTrader 5

Алгоритм поиска наибольшего среднего арифметического некой последовательности

Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий
Sergey Dzyublik
4207
Sergey Dzyublik  

Имеем массив Muss[2000] рандомных  значений (min =  -100, max =100).

Нужно найти последовательность, длина которой не короче n = 20 элементов,

чтобы среднее арифметическое элементов найденной последоавательности было наибольшим из всех возможных вариантов последовательностей.

 

Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи 40 000 раз.

Хотелось бы находить за линейную скорость или логарифмическую, но как? 

Alexandr Bryzgalov
45237
Alexandr Bryzgalov  
ALXIMIKS:

Имеем массив Muss[1000] рандомных  значений (min =  -100, max =100).

Нужно найти последовательность, длина которой не короче n = 45 элементов,

чтобы среднее арифметическое элементов найденной последоавательности было наибольшим из всех возможных вариантов последовательностей.

 

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

Хотелось бы находить за линейную скорость, но как? 

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

Если конечно я правильно понял задачу.

ЗЫ: нет похоже задачу я понял не правильно

Sergey Dzyublik
4207
Sergey Dzyublik  

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

Прикинул что это типа затухающей синусоиды под углом -45 градусов.

Проверил в exel (увы не знаком с VB, пришлось ручками).

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

 

Sergey Dzyublik
4207
Sergey Dzyublik  

Сейчас уточню условие, так как мог непонятно описать:

нужно из большого массива выбрать подряд лежащие элементы ( но не меньше n= 20 штук чтобы было подряд) может быть n=100, n=101 ...

не важно как выбрать, главное чтобы среднее значение было больше остальных вариантов выбора последовательности.

Среднее значение - это сума подряд лежащих элементов разделенная на их количество. 

Комбинатор
16961
Комбинатор  
Максимальное среднеарифметическое для массива ищется за O(N) (N размер массива) для любого количества элементов n если n фиксировано. Если для всех n, то O(n^2)
Andrei Fandeev
18151
Andrei Fandeev  

>>>>Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.

Да доли миллисекунды это )))

НомерПервогоЭлемента=0

МаксЗнач=0 

Цикл повторяется РазмерМассива - КолЭлементовСложения

в каждой итерации суммируем все КолЭлементовСложения с очередного номера элементов в массиве, делим на КолЭлементовСложения 

Если Результат > МаксЗнач, то МаксЗнач=Результат, запоминаем НомерПервогоЭлемента из КолЭлементовСложения на текущей итерации

Продолжаем цикл.

По завершении цикла имеем номер элемента буфера, с которого будет наибольшее среднее МаксЗнач

==

Всё это работает быстрее чем я печатаю одну букву ))) 

Alexandr Bryzgalov
45237
Alexandr Bryzgalov  

делать сложение элементов так:

  1. s
  2. s+s
  3. s+s+s
  4. s+s+s+s
  5. s+s+s+s+s
  6. s+s+s+s+s+s
  7. s+s+s+s+s+s+s
  8. s+s+s+s+s+s+s+s
  9. s+s+s+s+s+s+s+s+s
  10. s+s+s+s+s+s+s+s+s+s

далее ищем максимальную разность между (i+n) и i, где i- итерация, n-количество элементов в последовательности.

дальше думаю понятно.

Alexandr Bryzgalov
45237
Alexandr Bryzgalov  
AndreiFAN:

>>>>Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.

Да доли миллисекунды это )))

НомерПервогоЭлемента=0

МаксЗнач=0 

Цикл повторяется РазмерМассива - КолЭлементовСложения

в каждой итерации суммируем все КолЭлементовСложения с очередного номера элементов в массиве, делим на КолЭлементовСложения 

Если Результат > МаксЗнач, то МаксЗнач=Результат, запоминаем НомерПервогоЭлемента из КолЭлементовСложения на текущей итерации

Продолжаем цикл.

По завершении цикла имеем номер элемента буфера, с которого будет среднее МаксЗнач

==

Всё это работает быстрее чем я печатаю одну букву ))) 

да, так будет даже быстрее чем предложил я )

ЗЫ: хотя ХЗ, суммировать и одновременно искать разность между полученной суммой и суммой (i-n)элементов, второй массив по любому нужен, тогда только один проход по массиву

Sergey Dzyublik
4207
Sergey Dzyublik  

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

 

При длине массива 2000 и минимальной длине последовательности n = 20; и при повторении задачи всего 40000 раз

считается все весьма плачевно.

Как посчитать я знаю, реализовал, посчитал - меня скорость не устраивает, должно быть проще решение чем в тупую.

Вот и спрашиваю идеи по этому поводу. 

Andrei Fandeev
18151
Andrei Fandeev  
ALXIMIKS:

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

 

При длине массива 2000 и минимальной длине последовательности n = 20; и при повторении задачи всего 40000 раз

считается все весьма плачевно.

Как посчитать я знаю, реализовал, посчитал - меня скорость не устраивает, должно быть проще решение чем в тупую.

Вот и спрашиваю идеи по этому поводу. 

При длине массива 2000 и n=20 цикл повторится всего 1980 раз.

У меня Арбитражные сканеры выполняют в сотни если не тысячи раз больше вычислений по каждому инструменту у брокера, с анализом тысячи баров в историю, в каждую секунду Таймера....  не замечаю тормозов... 

Alexandr Bryzgalov
45237
Alexandr Bryzgalov  
AndreiFAN:

При длине массива 2000 и n=20 цикл повторится всего 1980 раз.

У меня Арбитражные сканеры выполняют в сотни если не тысячи раз больше вычислений по каждому инструменту у брокера, с анализом тысячи баров в историю, в каждую секунду Таймера....  не замечаю тормозов... 

цикл повторится 2000 раз, ведь сумма первых 20 элементов не просчитана и цикл должен прокрутиться и там, делить необязательно достаточно найти сумму.
Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий