运行数组中最后n个整数的总和

Question

假设一个进程每60秒收到一个新的整数.我想保留最后5个数字的总计.例如:

3 1 99 10 8 0 7 9 --> running total is 10+8+0+7+9==34
       <--------->

六十秒后,我们收到一个新的整数.收到的整数列表现在看起来像这样:

3 1 99 10 8 0 7 9 2 --> running total is now 8+0+7+9+2==26
          <-------->

如果你有存储空间来保存最后5个整数,这很容易实现.我正在尝试提出一种比这更有效的内存算法.有人有什么想法吗？

Answer 1

由于您可以重建最后n个数字,例如,如果您输入n个零,则您执行的任何操作都相当于存储最后n个数字.

假设数字可以是真正随机的并且每个数字是b位长,则任何正确的算法因此可以精确地再现nb随机位.这需要至少nb位存储.

Answer 2

我不认为你能解决这个问题.

对于最近两个最近整数的运行总和,必须至少存储第一个整数和当前运行总和,以重建第二个(或最后一个)整数.这意味着存储两个整数.

给出第一个整数:

一个₁

最后两个索引i和j的运行总和s _i,j可以迭代计算为整数a ₂,依此类推进入流中,重用前一个运行总和:

s _1,2 = a ₁ + a ₂

s _2,3 = s _1,2 - a ₁ + a ₃

s _3,4 = s _2,3 - (s _1,2 - a ₁)+ a ₄

s _4,5 = s _3,4 - (s _2,3 - (s _1,2 - a ₁))+ a ₅

...

等等,以递归的方式.

如您所见,两个整数的运行总和至少需要₁和运行总和s _i-2,i-1来重建倒数第二个元素.

同样,对于最近三个最近整数的运行总和,您必须至少存储前两个整数和当前运行总和,以重建第三个(或倒数第二个)整数.

给定第一个和第二个整数:

a ₁,a ₂

最后三个索引i,j和k的运行和s _i,j,k可以迭代计算为整数a ₃等进入流,重新使用先前运行的和:

s _1,2,3 = a ₁ + a ₂ + a ₃

s _2,3,4 = s _1,2,3 - a ₁ + a ₄

s _3,4,5 = s _2,3,4 - a ₂ + a ₅

s _4,5,6 = s _3,4,5 - (s _1,2,3 - a ₁ - a ₂)+ a ₅

...

同样,您必须为运行总和存储尽可能多的整数,以便重建缺少的整数.通过归纳,如果您要消除任何一个变量,您将无法概括缺失的值.

Answer 3

为了讨论,我正在简化这个问题.在实践中,将有8000个左右的这样的列表,我将需要保留最后5,60和3600个元素的运行总和.

听起来你想要在过去5秒,60秒和1小时内的总数.

你真的需要你的60秒总计准确到秒吗？或者可以每5秒更新一次？同样,您是否需要每小时总计精确到秒,或者每分钟更新一次是否正常？

如果您不需要每分钟和每小时的总计精确到秒,那么您可以节省很多存储空间.在这种情况下,5 + 12 + 60 = 77,而不是3600.

然后算法运行如下:

//these are the running totals that will be displayed
int last1 = 0;    //updated every second
int last5 = 0;    //updated every second
int last60 = 0;   //updated every 5 seconds
int last3600 = 0; //updated every minute

// 3 circular buffers:
// last 5 1-second periods (updated every second)
int period1[5] = {0};
// last 12 5-second periods (updated every 5 seconds)
int period5[12] = {0};
// last 60 1-minute periods (updated every minute)
int period60[60] = {0};

//indexes for the circular buffers
int index1 = 0;
int index5 = 0;
int index60 = 0;
while (1) {
    printf("1s 5s 1m 1h\n");
    printf("%2d %2d %2d %2d\n", last1, last5, last60, last3600);

    sleep(1);
    last1 = getNewValue();

    //update last5 by subtracting the expiring period and adding the new one
    last5 -= period1[index1];
    last5 += last1;
    //and save the new period to circular buffer
    period1[index1] = last1;
    index1++;

    //if we get to the end of the circular buffer we must go to the start
    //we have also completed a 5s period so we can update last60
    if (index1 >= 5) {
        index1 = 0;

        //similar to before
        last60 -= period5[index5];
        last60 += last5;

        period5[index5] = last5;
        index5++

        //similar to above, but now we have completed a 60s period
        //so we can update last3600
        if (index5 >= 12) {
            index5 = 0;

            //similar to before
            last3600 -= period60[index60];
            last3600 += last60;

            period60[index60] = last60;
            index60++

            if (index60 >= 60) {
                index60 = 0;
            }
        }
    }
}

正如您所看到的,只需要84个整数,并且不会进行循环,因此性能会很好.

如果您希望每秒更新60秒,而不是每5秒更新一次,则可以执行此操作.你也可以变得更加繁琐,例如每20秒更新1小时.但是,代码如此简洁的部分原因是每次完成每个句点时都会更新.

请注意,3600秒的总计是使用最多内存的那个,所以这是你需要最小心的.

Answer 4

我不相信你能做到这一点.你需要一个能够容纳最后n值的滑动窗口.

关于你可以做的最好的事情是使用模运算来将数组视为循环缓冲区,保持运行总和并随着计数进行计数,以避免迭代整个缓冲区来计算值的总和.像这样的东西:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define WINDOW_SIZE 5

static int   *window      ;
static int    i           ;
static double sum         ;
static double cnt         ;

double record_value( int value )
{
  double mean ;

  i          = (i+1) % WINDOW_SIZE ;
  sum        = sum - window[i] + value ;
  cnt       += cnt < WINDOW_SIZE ? 1 : 0 ;
  window[i]  = value ;

  mean = sum/cnt ;
  return mean ;
}

void log_message( double avg )
{
  int x = 0 ;

  printf( "%f = ( " , avg ) ;
  for ( int x = 0 ; x < cnt ; ++x )
  {
    printf( "%s%d" , x > 0 ? " + " : "" , window[x] ) ;
  }
  printf( " ) / %d\r\n" , (int)cnt ) ;
  return ;
}

int main( int argc, char* argv[] )
{
  int j ;

  window      = calloc( WINDOW_SIZE , sizeof(window[0]) ) ;
  i           = WINDOW_SIZE - 1 ;
  sum         = 0 ;
  cnt         = 0 ;

  for ( j = 0 ; j < 100 ; ++j )
  {
    int    v   = rand() ;
    double avg = record_value( v ) ;

    log_message( avg ) ;

  }

  return 0 ;
}