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

[Dmitry Fedoseev]

AndreiFAN:
Urain прав. Это как бы и доказывать не требуется.

Ыы. Данные не монотонно возрастают и убывают

[Dmitry Fedoseev]

void OnStart(){
   
   // параметры
   
   int size=1000;
   int min=45;
   
   //
   
   double a[];
   double s[];
   ArrayResize(a,size);
   
   // заполнение массива случайными значениями
   MathSrand(1);
   for(int i=0;i<size;i++){ // по горизонтали
      a[i]=MathRand()%100-MathRand()%100;
   }
   
   //=== вычисления ===
   
   ArrayResize(s,size); // массив для сумм для всез периодов от 1 до 1000
   
   // начальные суммы
   
   s[0]=a[0];   
   for(int i=1;i<size;i++){ 
      s[i]=s[i-1]+a[i];
   }
   
   // === 
   
   double mv=-999999;
   int mi=-1;
   int mj=-1;
   
   for(int i=min-1;i<size;i++){ // по периодам
      int p=i+1; // период
      //из начальной суммы
      double aver=s[i]/p;
      if(aver>mv){
         mv=aver;
         mi=i;
         mj=i;
      }
      for(int j=p;j<size;j++){ // скользим по данным
         s[i]+=a[j];
         s[i]-=a[j-p];
         aver=s[i]/p;
         if(aver>mv){
            mv=aver;
            mi=i;
            mj=j;
         }
      }
   }

   Alert("val=",mv,", пер=",(mi+1)," инд=",mj);
   
}

Вот такой вот вариантик (отсутствие ошибок не гарантируется, но вот такой вот принцип). 

[Alexandr Bryzgalov]

Integer:
Ыы. Данные не монотонно возрастают и убывают

а МАшка всё равно правильно покажет где было максимальное среднее.

тогда код сокращается, но вариант не самый быстрый.

[Mykola Demko]

Integer:
Ыы. Данные не монотонно возрастают и убывают

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

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

Самый высокий максимум будет у машки с периодом 1 те тупо сам график. Заметь машка сзади и до текущего значения никогда не превышает и не находится ниже графика.

Машка это усреднение и она всегда находится в средине экстремумов. 

[Dmitry Fedoseev]

данные 100 0 100

по два: 50 50

по три: 200/3=66 

[Mykola Demko]

Integer:

данные 100 0 100

по два: 50 50

по три: 200/3=66 

Данных мало, закольцуй буфер и ты получишь в периоде 2 среднее 100.

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

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

[Sergey Dzyublik]

AndreiFAN:
Urain прав. Это как бы и доказывать не требуется.

ок, я намудрил с примером, брал из головы не подумав ((

Вы утверждаете что машка с большим переодом не может иметь максимальное  среднеарифметическое значение чем машка с меньшим периодом для одних и тех же данных?

 вот ексель с расчетами - убедитесь сами в неправоте (при вводе в любую пустую ячейку чего-то генерируется новый набор данных). 

[Dmitry Fedoseev]

Urain:
Данных мало, закольцуй буфер и ты получишь в периоде 2 среднее 100.

Зачем их закольцовывать, если их не надо закольцовывать? Это просто пример показывающий, что ваши рассуждения неверны.

[Sergey Dzyublik]

AndreiFAN:

не совсем понял...  45 и 20...  опечатка?

Так вот, а зачем вам суммы нескольких первых элементов, количественно меньше ? Сумма первых пяти например, зачем? 

Потому я и сделал i<ArraySize(Buffer)-N   чтобы не смотреть последние...

Ок. Наверно можно и так. 

Кстати, да, в моём примере тоже можно не складывать 20 элементов, а отнимать один элемент (начальный в предыдущей итерации), и прибавлять следующий в массиве....  

Сложение 20-ти только один раз, в начале цикла 

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

Мужики, реально спасибо за энтузиазм,

но предлагаемый вами алгоритм в нужной мне вариации реализован и он медленный 

скорость алгоритма перебора КВАДРАТИЧНА а мне надо изменить его в что-то по проще - хотя бы в логарифмическую или О(n logn)

Более полная задача - это найти координаты всех точек (от n=20 до 2000)  

Грубо говоря и опираясь на пример с машками:

накладываем машки от 20 до 2000, выбираем 1500-й бар и двигаемся с самого верха вниз вдоль этого бара до первого пересичения с какой-то машкой,

вот эту точку и надо узнать (но их еще тысяча с лишним штук)

Потом выбираем новый бар, соседний, и опять двигаемся вниз. 

Это полная задача что надо, просто сразу не знал как сформулировать доступно.

 

Задача с барами ни как не связана, пример с машками просто для наглядного описания. (в реальности есть просто много массивов 40000 и для каждого надо одно и тоже)

 

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

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

но это на глаз все пока (( и не подойдет к маленьким n.

[Mykola Demko]

Integer:
Зачем их закольцовывать, если их не надо закольцовывать? Это просто пример показывающий, что ваши рассуждения неверны.

http://ru.wikipedia.org/wiki/%D0%A7%D0%B0%D1%81%D1%82%D0%BE%D1%82%D0%B0_%D0%9D%D0%B0%D0%B9%D0%BA%D0%B2%D0%B8%D1%81%D1%82%D0%B0&nbsp;

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

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