Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

queue with time stamped elements within a time period

I want to store in a queue, datastructure does not matter, only the elements that I have inserted within say last 5 minutes from current time. Anything older should get removed - so that any time I get the size of the queue it will give count of the objects inserted in last 5 minutes.

Basically all I have to know is how many times my app has made a http call to a sever in last 5 minutes before making the next call.

If anyone knows of some existing library that may have this implementation please share.

like image 514
user759326 Avatar asked Jul 11 '11 00:07

user759326


People also ask

Is priority queue LIFO or FIFO?

Typical stacks and queues are technically types of priority queues. The highest priority element in a stack is the most recently inserted one (LIFO), while the highest priority element in a queue is the least recently inserted one (FIFO).

What is Element () priority queue?

Priority Queue is an abstract data type that is similar to a queue, and every element has some priority value associated with it. The priority of the elements in a priority queue determines the order in which elements are served (i.e., the order in which they are removed).

How do I check if a queue has an element?

Check if Queue Contains Element You can check if a Java Queue contains a certain element via its contains() method. The contains() method will return true if the Queue contains the given element, and false if not.

How are elements ordered in a priority queue?

The elements of the priority queue are ordered according to the natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. In the below priority queue, an element with a maximum ASCII value will have the highest priority.


2 Answers

You can use a Priority Queue with timestamps as your keys. So that when you call Peek() you always get the oldest timestamp still in the queue. Then each time you go to query for the number of items inside your window size: you cleanup the items outside your window and return the number of items still in the Priority queue.

For example:

public class CountInWindow {

    /**
     * Adding a main just for testing 
     * @param args
     * @throws InterruptedException 
     */
    public static void main(String[] args) throws InterruptedException {
        System.out.println("test started");
        CountInWindow test = new CountInWindow(5000); //5 seconds for testing
        test.debug = true;
        test.insertTimeStamp(System.currentTimeMillis());
        Thread.sleep(100);//sleep 
        test.insertTimeStamp(System.currentTimeMillis());
        Thread.sleep(100);//sleep 
        test.insertTimeStamp(System.currentTimeMillis());
        Thread.sleep(100);//sleep 
        test.insertTimeStamp(System.currentTimeMillis());
        Thread.sleep(5040);//sleep 5 secs
        test.insertTimeStamp(System.currentTimeMillis());
        Thread.sleep(100);//sleep 
        test.insertTimeStamp(System.currentTimeMillis());
        System.out.println(test.getWindowCount()); //Should be 2 not 6.
        System.out.println("test done");
    }

    java.util.PriorityQueue<Long> window;
    public static final long FIVE_MINS_IN_MS = 300000l;
    public final long WINDOW_SIZE;
    public boolean debug = false;

    //Constructor which defaults to 5mins
    public CountInWindow(){
        WINDOW_SIZE = FIVE_MINS_IN_MS;
        window = new java.util.PriorityQueue<Long>();
    }
    //Constructor for any size window
    public CountInWindow(long windowSize){
        WINDOW_SIZE = windowSize;
        window = new java.util.PriorityQueue<Long>();
    }
    /**
     * Add a new timestamp to the window's queue
     * @param ts
     */
    public void insertTimeStamp(long ts){
        window.add(ts);
    }
    /**
     * Clean up items outside the window size and then return the count of times still in the window.
     * @return A count of timestamps still inside the 5 mins window.
     */
    public int getWindowCount(){
        long currTime = System.currentTimeMillis();
        //Clean out old Timestamps
        while((currTime - window.peek().longValue()) > WINDOW_SIZE){
            long drop = window.remove().longValue();
            if(debug)System.out.println("dropping item:" + drop);
        }
        return window.size();
    }
}
like image 82
eSniff Avatar answered Oct 12 '22 16:10

eSniff


In what language? Is the queue persistent or in-memory?

If you need this behavior in Java, you can use a DelayedQueue, and have a separate thread calling queue.take() continuously in a tight loop to drain out expired items. queue.size() will then give you the size of remaining unexpired items in the queue. This requires that the items you put in the DelayedQueue implement the Delayed interface and return the value 5 minutes to the .getDelay() method.

like image 26
Moe Matar Avatar answered Oct 12 '22 16:10

Moe Matar