Java 2 methods comparison and analysis Queue and Array


  • 0

    storing previous average is better than storing accumulate sum as the sum might be out of range of double with increasing data.

    public class MovingAverage {
        private Queue<Integer> queue;
        private int windowSize;
        private double average;
        
        public MovingAverage(int size) {
            queue = new LinkedList<>();
            windowSize = size;
        }
        
        public double next(int val) {
            int prevSize = queue.size();
            int out = queue.size() == windowSize ? queue.poll() : 0;
            queue.offer(val);
            return average = (average * prevSize - out + val) / queue.size(); 
        }
    }
    
    
     The array implementation is faster as low overhead. But it might crash if the count exceeds Integer.MAX_VALUE and goes negative.
     
     
     
     public class MovingAverage {
        private int[] window;
        private int count;//previous count, total number of next() calls
        private double average;//previous average
        
        public MovingAverage(int size) {
            window = new int[size];
        }
        
        public double next(int val) {
            count++;
            int out = window[count % window.length];
            window[count % window.length] = val;
            // count-1 previous count
            return average = (average * Math.min(count - 1, window.length) - out + val) / Math.min(count, window.length);
        }
    }

  • 0
    This post is deleted!

  • 0

    Actually, I don't think you need to keep increasing count. You could just keep a boolean to indicate whether you have reached window.length and then do count = (count + 1) % window.length to avoid overflow. I didn't do it in Python cause it can handle big numbers well (although it wouldn't hurt). Do you agree?


  • 0

    you are absolutely right. another way is if (count == 2 * n + 1) count = n + 1, same idea


  • 0

    you are absolutely right. another way is if (count == 2 * n + 1) count = n + 1, same idea


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.