Geek asks and answers

Sliding Window: Implementation and Performance (Java)

I want to implement a very simple sliding window. In other words, I will have some kind of list with objects inserted from the right end of this list and omitted from the left end. In each insert, previous objects are shifted left by one index. When the list is filled with objects, in each insert from the right end the object will be deleted from the left end (and previous objects, of course, will be shifted to the left by one index, as usual).

I meant either LinkedList or ArrayDeque. Probably the latter is the best choice, because as far as I know, inserting AND removing to / from either end is O (1 )'s constant effort for ArrayDeque, which is not for LinkedList. Is it correct?

In addition, I would like to ask the following: the left shift of all previous objects stored in the sliding window when I insert a new object requires intensive processing for a large sliding window with 100,000 or even 1,000,000 objects, as in my case, Are there is there any other data structure that might work better in my application?

NOTE. I use the term “sliding window” for what I want to implement, maybe there is another term that describes it better, but I think I want to do what I want to do from the description above.

+3
source share
2 answers

ArrayDeque , . . . , , , .

ArrayDeque , . . LinkedList .

BTW , , - .

double last = 0;
long lastTime = 0;
double halfLife = 60 * 1000; // 60 seconds for example.

public static double ewma(double sample, long time) {
    double alpha = Math.exp((lastTime - time) / halfLife);
    lastTime = time;
    return last = sample * alpha + last * (1 - alpha); 
}

, Math.exp

public static double ewma(double sample, long time) {
    long delay = time - lastTime
    double alpha = delay >= halfLife ? 1.0 : delta / halfLife;
    lastTime = time;
    return last = sample * alpha + last * (1 - alpha); 
}

, .

+5

Queue? java.util.LinkedList , Queue. , LinkedList push, pop - O (1), get - O (N).

: ​​ LinkedList:

Link<ET> next = link.next;
Link<ET> newLink = new Link<ET>(object, link, next);
link.next = newLink;
next.previous = newLink;
link = newLink;
lastLink = null;
pos++;
expectedModCount++;
list.size++;
list.modCount++;
0

More articles:


All Articles