一个时间段内带有时间戳元素的队列

2022-01-21 00:00:00 data-structures queue java

我想存储在队列中，数据结构无关紧要，只有我在当前时间最后 5 分钟内插入的元素.任何较旧的东西都应该被删除——这样每当我得到队列的大小时，它就会给出最后 5 分钟内插入的对象的计数.

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.

基本上我只需要知道我的应用在进行下一次调用之前的最后 5 分钟内对服务器进行了多少次 http 调用.

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.

推荐答案

您可以使用带有时间戳的优先队列作为键.因此，当您调用 Peek() 时，您始终会获得仍在队列中的最旧时间戳.然后每次查询窗口大小内的项目数时:清理窗口外的项目并返回仍在优先级队列中的项目数.

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.

例如:

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();
    }
}

相关文章