Another one of those "Aha" interview questions: Long-running averages

Let this be a lesson to all those who believe a CS degree should amount to nothing more than "Learn Blub in 21 Days Vocational Training" :-)

What leads you to believe that the order of the inputs is significant? The derivation makes sense, the final form makes sense, and I tried a few inputs.

(also, a high pass filter does not necessarily settle to its input over time)

It's easy to prove that linear space is optimal -- you can't store N bits of information using less than N bits of space.

Sounds about right for what we do to compute Geometric Brownian Motion.

  function create_sliding_averager (window_span, debug) 
      local window_span = window_span -- seconds
      local tally = 0
      local fifo = { tail = 1, head = 0 }
      local debug = debug
  
      return function (amount, current_time)
          local head = fifo.head + 1
          local tail = fifo.tail
  
          fifo[head] = { timestamp = current_time, amount = amount }
          tally = tally + amount
  
          local cutoff, old_time = current_time - window_span, nil

          if fifo[tail] then
            old_time = fifo[tail].timestamp
          end
  
          if debug then
              print ('cutoff: ', cutoff, 'old time:',
                    old_time, 'current:', current_time)
          end

          while old_time ~= nil and old_time < cutoff do
              tally = tally - fifo[tail].amount
              if debug then
                print ('expiring: ', fifo[tail].timestamp, fifo[tail].amount)
              end
              fifo[tail] = nil
              tail = tail + 1
              old_time = fifo[tail].timestamp
          end
  
          fifo.tail = tail
          fifo.head = head

          if debug then print(tail, head) end
          return 'avg: '..(tally / (head - tail + 1)), 'size: '..(head - tail + 1)
      end
  end
  
  averager = create_sliding_averager(10) -- 10 second average
  
  while true do
      local rand = math.random()
      local time = os.time()
      print (averager(rand, time))
  end

This is a pretty brute-force solution. I'll see if I can think of something more elegant.

But that doesn't mean that you won't run into someone out there asking a question like this.