очередь с элементами с метками времени в течение периода времени

Question

Я хочу сохранить в очереди, структура данных не имеет значения, только элементы, которые я вставил в течение, скажем, последних 5 минут от текущего времени.Все, что старше, должно быть удалено - так что каждый раз, когда я получу размер очереди, он будет подсчитывать количество объектов, вставленных за последние 5 минут.

По сути, все, что мне нужно знать, - это сколько раз мое приложение выполняло http-запрос к серверу за последние 5 минут, прежде чем сделать следующий вызов.может иметь эту реализацию, пожалуйста, поделитесь.

Answer 1

Вы можете использовать приоритетную очередь с временными метками в качестве ключей. Так что, когда вы вызываете Peek (), вы всегда получаете самую старую отметку времени, все еще находящуюся в очереди. Затем каждый раз, когда вы отправляете запрос на количество элементов в вашем размере окна: вы очищаете элементы за пределами вашего окна и возвращаете количество элементов, все еще находящихся в очереди Приоритет.

Например:

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

Answer 2

На каком языке? Очередь постоянна или находится в памяти?

Если вам нужно такое поведение в Java, вы можете использовать DelayedQueue и иметь отдельный поток, непрерывно вызывающий queue.take() в узком цикле для истечения истекших элементов. queue.size() даст вам размер оставшихся в очереди элементов в очереди. Для этого необходимо, чтобы элементы, которые вы поместили в DelayedQueue, реализовали интерфейс Delayed и возвращали значение 5 минут методу .getDelay().

Answer 3

Я реализовал FadingLinkedList как

public class FadingLinkedList<E> {

private transient Entry<E> header = new Entry<E>(null, null);

/**
 * ms
 */
private long livingTime;

/**
 * Constructs FadingLinkedList with elements of living time livingTime in
 * milliseconds
 */
public FadingLinkedList(long livingTime) {
    this.livingTime = livingTime;
}

/**
 * remove all faded elements,
 *
 * @return the count of not faded
 */
public synchronized int removeFaded() {
    long now = System.nanoTime();
    int count = 0;
    Entry<E> prev = header;// the last living Entry in the loop
    for (Entry<E> e = header.next; e != null; e = e.next) {
        if (TimeUnit.NANOSECONDS.toMillis(now - e.birthTime) >= livingTime) {
            // cut off this list here.
            prev.next = null;
            break;
        }
        count++;
        prev = e;
    }
    return count;
}

/**
 * Returns the number of elements that not faded.
 */
public int size() {
    return removeFaded();
}

public synchronized void push(E e) {
    Entry<E> newEntry = new Entry<E>(e, header.next);
    header.next = newEntry;
}

private static class Entry<E> {
    E element;
    Entry<E> next;
    long birthTime;

    Entry(E element, Entry<E> next) {
        this.element = element;
        this.next = next;
        this.birthTime = System.nanoTime();
    }
}

public synchronized void clear() {
    header.next = null;
}

public synchronized int getAndClear() {
    int size = size();
    clear();
    return size;
}

}