CODEWITHSUNDEEP
javaalgorithm
HideAndSeek
HideAndSeek

Reputation: 414

Calculating Moving Average with Time Window

I want to calculate a moving average over a time window:

//object init
MovingAverageTimeBased movTime = new MovingAverageTimeBased(8000f);

//this gets called every Frame (around 180 FPS -- but varies of course)
movingAvg = movTime.next(value, System.currentTimeMillis());

And this is the class:

public class MovingAverageTimeBased {

    float windowsize;
    Queue<Float> queue;
    Queue<Float> timestampQueue;
    float sum;
    float lastItemDeleted;

    public MovingAverageTimeBased(float windowsize) {
        this.windowsize = windowsize;
        this.queue = new LinkedList<Float>();
        this.timestampQueue = new LinkedList<Float>();

        this.sum = 0;
    }

    public double next(float n, float timestamp) {

        if(queue.size() > 1 && timestampQueue.size() > 1) {

            System.out.println("Timestamp diff- " + (timestamp - (float) timestampQueue.peek()));

             while (timestamp - (float) timestampQueue.peek() > windowsize) {
                    System.out.println("Unqueue item");

                    sum = sum - (float) queue.poll();
                    timestampQueue.poll();
             }
        }

        queue.offer(n);
        timestampQueue.offer(timestamp);

        sum = sum + n;
        return (float) sum / queue.size();
    }

}

My error is that, that entries never seem to get deleted as the difference of the timestamps are always 0?

What could be the mistake?

Upvotes: 0

Views: 1604

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59174

The big problem is that you used a Queue<Float> for your time stamps.

System.currentTimeMillis() is currently 1544100776456

rounded to the nearest float, this is 1.5441007E12

As you can see, we lost some digits. You need to wait about a minute before the float value will change.

You should use Long or Double in that queue.

Then you have to check queue size > 0 for every iteration of the while loop, not just the first one.

Upvotes: 2

HPCS
HPCS

Reputation: 1454

Your code is ok, but you are storing timestamp as float(float is not big enough for timestamp) store timestamps as long

public class MovingAverageTimeBased {

  long windowsize;
  Queue<Float> queue;
  Queue<Long> timestampQueue;
  float sum;
  float lastItemDeleted;

  public MovingAverageTimeBased(long windowsize) {
    this.windowsize = windowsize;
    this.queue = new LinkedList<Float>();
    this.timestampQueue = new LinkedList<Long>();

    this.sum = 0;
  }

  public double next(float n, long timestamp) {

    if(queue.size() > 1 && timestampQueue.size() > 1) {

      System.out.println("Timestamp diff- " + (timestamp - timestampQueue.peek()));

      while(timestamp - timestampQueue.peek() > windowsize) {
        System.out.println("Unqueue item");

        sum = sum - queue.poll();
        timestampQueue.poll();
      }
    }

    queue.offer(n);
    timestampQueue.offer(timestamp);

    sum = sum + n;
    return (float) sum / queue.size();
  }

}

Upvotes: 1

Related Questions