With circular buffer one can use a simple array with that window size and once it's full keep replacing elements from beginning of array with new elements using an additional index. Once that index reaches the end simply reset it. So not much overhead of a queue.
If I use an ArrayList instead of a Queue, and keep removing the 0th element each time, using list.remove(0), will that be equally efficient as using a Queue? or would that be slower?
ArrayList will be much slower. Removing the first element of an array is usually done by making a new array and copying all of the values minus the first one over, or by moving every element but the first one to the left. Either way, this takes O(n) operations where n is the size of the array. Java's ArrayDequeue will optimize this specific case if you use the poll() method, but will still be O(n) if you use the remove(0) method. LinkedList's .remove(0) and poll() methods are both O(1) time.
better solution: int[] buff; int size; int total = 0; int count = 0; public MovingAveragefromDataStream (int size) { this.size=size; buff = new int[size]; } public double next (int val) { int minus = buff[count]; buff[count] = val; total = total - minus + val; count++; if (count==size) count=0; return (double)total/(double)size; } you don't need a queue, just a buffer with a pointer of count%size.
![แฉกลโกงงานวัด 2024 [ โกงมั้ยครับ ep.106 ] | DOM](http://i.ytimg.com/vi/taC5dpP3HXA/mqdefault.jpg)
Thank you Kevin, same format question were asked on HACKER EARTH HIRING CONTEST 1 month ago.
Anytime, hope it helped!
Exactly same can be used to smooth data also...this is actually a concept of Digital Image Processing....to remove the noise this idea is used
I had no idea what the question and example was asking me to do. They need better clarification on the question. Thaks for the clarification.
Hey this is great! A more memory efficient way of doing this is using a circular buffer :)
How is circular buffer better? Can you explain @craig williams
With circular buffer one can use a simple array with that window size and once it's full keep replacing elements from beginning of array with new elements using an additional index. Once that index reaches the end simply reset it. So not much overhead of a queue.
Do you mean a circular queue?
I had to clap for you after watching this video. Great thoughts right there.
Good Explanation. Thanks for making this video.
If I use an ArrayList instead of a Queue, and keep removing the 0th element each time, using list.remove(0), will that be equally efficient as using a Queue? or would that be slower?
ArrayList will be much slower. Removing the first element of an array is usually done by making a new array and copying all of the values minus the first one over, or by moving every element but the first one to the left. Either way, this takes O(n) operations where n is the size of the array. Java's ArrayDequeue will optimize this specific case if you use the poll() method, but will still be O(n) if you use the remove(0) method. LinkedList's .remove(0) and poll() methods are both O(1) time.
Hi can you solve more OO design questions?
Fantastic thank you so much
Thank you and anytime!
Thanks!
better solution:
int[] buff;
int size;
int total = 0;
int count = 0;
public MovingAveragefromDataStream (int size) {
this.size=size;
buff = new int[size];
}
public double next (int val) {
int minus = buff[count];
buff[count] = val;
total = total - minus + val;
count++;
if (count==size)
count=0;
return (double)total/(double)size;
}
you don't need a queue, just a buffer with a pointer of count%size.
Subbed !
Cory Catherall thanks Cory!!! :)
great code