Формула для расчета среднего числа на расширение массива данных

Question

Say, если бы я был окончательный массив чисел, скажем:

{1, 5, 7, 2} 

среднее значение для них будет:

(1 + 5 + 7 + 2)/4; //Or, sum of all elements, divided by their number 

Но что, если мой массив постоянно растет, и мне нужно знать текущее среднее число в момент времени, когда полный массив пока не известен. Как вы это вычисляете?

Скажите, например, когда я пытаюсь отобразить текущую скорость передачи данных.

Answer 1

Я бы пошел с простым подходом, имея running total (совокупный) с постоянной сложностью пространства (1). И по запросу avg, верните результат, который равен running total/total number of item. Отсутствие расширенной временной сложности, так как мы не итерации массива впоследствии, чтобы найти кумулятивную сумму.

Answer 2

Моя ставка заключается в том, что вы хотите что-то быстро, иначе у вас уже есть свой ответ. Суммируйте все числа, которые у вас уже есть по длине массива, который у вас уже есть. Это очень просто.

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

редактировать:

х против 1000x происходит от алго сложности. Предположим, что вы суммируете 5 чисел, то есть 5 операций, тогда вы делите на 5, другая операция для всего 6 (для примера мы предположим, что все они принимают одно и то же время компьютера, но на самом деле деление происходит медленно по сравнению с добавлением). Если вы берете тот же код, но с 1000 номерами, вы выполняете 1001 операцию, которая займет гораздо больше времени, чем в первом случае!

С помощью «скользящей средней» вы всегда берете фиксированное количество чисел, чтобы ваш алгоритм занимал фиксированное количество времени, независимо от того, имеете ли вы 5 или 1000 чисел.

Скользящее среднее - это всего лишь причудливая формулировка, чтобы сказать, что вы не принимаете одинаковые числа в своем массиве от одного раза к другому. Представьте себе следующий массив:

int x = { 1, 4, 6, 3, 1 };
int arrayLength = 5;

Тогда будет среднее значение этого массива

int runningTotal = 0; 
for(int i = 0; i < arrayLength; i++) 
{ 
    runningTotal += x[i]; 
} 
double average = runningTotal/arrayLength 

Скользящее среднее из 3 значений будет

int movingLength = 3; 
int runningTotal = 0; 
for(int i = 0; i < movingLength; i++) 
{ 
    runningTotal += x[arrayLength - i - 1]; 
} 
double average = runningTotal/movingLength; 

Итак первые значения в полях array не являются частью вычисления, когда массив растет.

Answer 3

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

Для передачи данных это проблематичный подход. Подумайте о сценарии, когда вы начинаете передачу с высокой пропускной способностью, а затем соединение падает, и с простым усреднением может потребоваться много времени для того, чтобы ваш пользовательский интерфейс отражал, что текущая скорость передачи равна 0. Использование взвешенной скользящей средней является быстрым способ сделать ваш интерфейс более отзывчивым.

Простейшая реализация этого является образцом скорость передачи данных периодически (скажем, каждые 5 секунд) и рассчитать скорость что-то вроде:

float weight = 2.0; //you are going to want to tweak this to get the right balance between "responsive" and "noisy" 

void UpdateAverage(float newValue) 
{ 
    this.Average = (this.Average + (newValue*weight))/(weight+1) 
} 

Answer 4

Вы ищете скользящее среднее:

static void Main(string[] args) { 
     var nums = Enumerable.Range(1, 5).Select(n => (double)n); 
     nums = nums.Concat(nums.Reverse()); 

     var sma3 = SMA(3); 
     var sma5 = SMA(5); 

     foreach (var n in nums) { 
      Console.WriteLine("{0} (sma3) {1,-16} (sma5) {2,-16}", n, sma3(n), sma5(n)); 
     } 
    } 

    static Func<double, double> SMA(int p) { 
     Queue<double> s = new Queue<double>(p); 
     return (x) => { 
      if (s.Count >= p) { 
       s.Dequeue(); 
      } 
      s.Enqueue(x); 
      return s.Average(); 
     }; 
    } 

Источник: http://rosettacode.org/wiki/Averages/Simple_moving_average#C.23

Answer 5

Предполагая, что вы не хотите скользящее среднее ..

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

Если массив это ...

Array = {1, 5, 7, 2} 
Sum = 1 + 5 + 7 + 2 = 15 
Number of elements = 4 
Average = Sum/Number of elements = 3.75 

Вы добавляете пару элементов и ваш массив выглядит следующим образом ...

Array = {1, 5, 7, 2, 10, 6} 

Если предположить, что фактический массив намного больше .. . Для того, чтобы пересчитать ваш средний ..

Sum = ([previous sum] + [sum of new elements])/[number of elements] 
Number of elements = 6 
Average = ((15 * 4) + 10 + 6)/6 = 5.1666667 

Edit: I f вы обеспокоены точностью и размером проверить BigInteger

Answer 6

Я знаю, что опаздываю на вечеринку, но в 2000 году я решил аналогичную проблему, когда создавал адаптивный балансировщик нагрузки. Стандарт в среднем имеет две проблемы, как упоминалось в ответах:

1. Сценарий переполнения
- Ведение нарастающим итогом приведет к переполнению
2. Перерасчет средней
- Как правило, вы должны сделать это для каждого отдельного образца

Таким образом, вы можете превратить обычный средний расчет в то, что математический народ называют «рекуррентным отношением», что означает, что вы сохраняете предыдущее среднее значение, которое затем используется для вычисления нового (сродни ответу Яура, который у меня есть согласиться с ahmed, я не вижу, чтобы это было проголосовано). Я написал оригинал в Delphi в тот же день, поэтому я совсем недавно сделал то же самое в .NET и сравнил его со стандартным процессом вычисления постоянных средних значений, поскольку списки предметов становятся больше.

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

http://goadingtheitgeek.blogspot.co.uk/2014/05/blast-from-past.html

Надеюсь, вы сочтете это полезным.

Answer 7

если средняя длина буфера меняет мою старую программу.

namespace WindowsFormsApplication1 
{ 
    public partial class ComTester : Form 
    { 
    public int []sAvgArr=new int [251]; 
    public int sAvgAdr,sAvgCnt; 

    private void Calc_Values(object sender, int v)//v is value 
    { 
     int n = AverageLength; 
     if (n > 250) n = 250;//average buffer maksimum 
     if (n > 0) 
     { 
      sAvgArr[sAvgAdr] = v; 
      sAvgAdr += 1; 
      sAvgCnt += 1; 
      if (n <= sAvgAdr) sAvgAdr = 0; 
      if (n <= sAvgCnt) sAvgCnt = n; 
      n = sAvgCnt; 
      int f = 0, l = 0; ; 
      for (l = 0; l < n; l += 1) 
       f += sAvgArr[l]; 
      f = f/sAvgCnt; 
      sAvgVal = f; 
     } 
     else 
     { 
      sAvgVal=v; 
     } 
    } 
    } 
} 

Answer 8

using System; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      int n = 3 , x , sum = 0 ; 
      double ave; 

      for (int i = 0; i < n; i++) 
      { 
       Console.WriteLine("enter the number:"); 
       x = Convert.ToInt16(Console.ReadLine()); 
       sum += x; 
      } 

      ave = (double)(sum)/3; 
      Console.WriteLine("average:"); 
      Console.WriteLine(ave); 
      Console.ReadLine(); 
     } 
    } 
}