Скачать MetaTrader 5

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

Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий
Скачай документацию одним файлом. Это просто!
Sergey Dzyublik
4818
Sergey Dzyublik 2014.09.08 18:54 

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

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

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

 

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

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

Alexandr Bryzgalov
27515
Alexandr Bryzgalov 2014.09.08 19:38  
ALXIMIKS:

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

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

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

 

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

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

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

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

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

Sergey Dzyublik
4818
Sergey Dzyublik 2014.09.08 19:38  

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

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

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

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

 

Sergey Dzyublik
4818
Sergey Dzyublik 2014.09.08 19:43  

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

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

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

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

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

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

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

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

МаксЗнач=0 

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

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

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

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

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

==

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

Alexandr Bryzgalov
27515
Alexandr Bryzgalov 2014.09.08 20:01  

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

  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
27515
Alexandr Bryzgalov 2014.09.08 20:02  
AndreiFAN:

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

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

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

МаксЗнач=0 

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

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

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

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

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

==

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

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

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

Sergey Dzyublik
4818
Sergey Dzyublik 2014.09.08 20:10  

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

 

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

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

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

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

Andrei Fandeev
18176
Andrei Fandeev 2014.09.08 20:16  
ALXIMIKS:

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

 

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

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

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

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

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

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

Alexandr Bryzgalov
27515
Alexandr Bryzgalov 2014.09.08 20:18  
AndreiFAN:

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

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

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