Java에서 마지막 N 요소를 포함하는 크기 제한 대기열

Java에서 마지막 N 요소를 포함하는 크기 제한 대기열

Java 라이브러리에 대한 매우 간단하고 빠른 질문: 를 구현하는 기성 클래스가 있는가?Queue고정된 최대 크기(즉, 항상 요소의 추가를 허용하지만 새로 추가된 요소의 공간을 수용하기 위해 머리 요소를 자동으로 제거함)

물론 수동으로 구현하는 것은 사소한 일이다.

import java.util.LinkedList;

public class LimitedQueue<E> extends LinkedList<E> {
    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > limit) { super.remove(); }
        return true;
    }
}

내가 보기엔 자바 stdlibs에는 표준 구현이 없지만, 아파치 커먼즈에는 표준 구현이 있을 수도 있어.

아파치 커먼스 컬렉션 4에는 당신이 찾고 있는 CircularFifoQueue가 있다.자바독의 인용:

CircularFifoQueue는 꽉 찬 경우 가장 오래된 요소를 대체하는 고정 크기를 가진 첫 번째 입력 대기열이다.

    import java.util.Queue;
    import org.apache.commons.collections4.queue.CircularFifoQueue;

    Queue<Integer> fifo = new CircularFifoQueue<Integer>(2);
    fifo.add(1);
    fifo.add(2);
    fifo.add(3);
    System.out.println(fifo);

    // Observe the result: 
    // [2, 3]

이전 버전의 아파치 커먼스 컬렉션(3.x)을 사용하는 경우 제네릭 없이 기본적으로 동일한 CircularFifoBuffer를 사용할 수 있다.

업데이트: 제네릭을 지원하는 커먼스 컬렉션 버전 4 릴리스 이후 답변 업데이트.

Guava는 이제 새로운 요소를 큐에 추가하려고 하면 큐의 머리에서 요소를 자동으로 제거하여 가득 찬 차단되지 않는 큐인 EvictingQueue를 가지고 있다.

import java.util.Queue;
import com.google.common.collect.EvictingQueue;

Queue<Integer> fifo = EvictingQueue.create(2); 
fifo.add(1); 
fifo.add(2); 
fifo.add(3); 
System.out.println(fifo); 

// Observe the result: 
// [2, 3]

나는 @FractalizeR 솔루션을 좋아한다.하지만 나는 또한 super.add(o)의 값을 유지하고 반환할 것이다!

public class LimitedQueue<E> extends LinkedList<E> {

    private int limit;

    public LimitedQueue(int limit) {
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
           super.remove();
        }
        return added;
    }
}

확장되지 않은 구성을 사용하십시오(예: 확장됨, Java의 확장 키워드에 대한 참조와 예, 상속임).구현을 완전히 차단하여 동급 사용자에게 영향을 주지 않고 구현을 변경할 수 있기 때문에 구성이 더욱 우수하다.

이런 것을 시도해 볼 것을 추천한다(나는 이 창에 직접 타이핑을 하고 있으므로 구매자는 구문 오류를 주의한다).

public LimitedSizeQueue implements Queue
{
  private int maxSize;
  private LinkedList storageArea;

  public LimitedSizeQueue(final int maxSize)
  {
    this.maxSize = maxSize;
    storageArea = new LinkedList();
  }

  public boolean offer(ElementType element)
  {
    if (storageArea.size() < maxSize)
    {
      storageArea.addFirst(element);
    }
    else
    {
      ... remove last element;
      storageArea.addFirst(element);
    }
  }

  ... the rest of this class

더 나은 옵션(Asaf의 답변에 기반)은 Apache Collections CircularFifoBuffer를 일반 클래스로 포장하는 것일 수 있다.예를 들면 다음과 같다.

public LimitedSizeQueue<ElementType> implements Queue<ElementType>
{
    private int maxSize;
    private CircularFifoBuffer storageArea;

    public LimitedSizeQueue(final int maxSize)
    {
        if (maxSize > 0)
        {
            this.maxSize = maxSize;
            storateArea = new CircularFifoBuffer(maxSize);
        }
        else
        {
            throw new IllegalArgumentException("blah blah blah");
        }
    }

    ... implement the Queue interface using the CircularFifoBuffer class
}

공간이 제한된 유일한 것은 BlockingQueue 인터페이스(예: ArrayBlockingQueue 클래스에 의해 구현됨)뿐이지만 채워지면 첫 번째 요소를 제거하지 않고 대신 공간이 확보될 때까지(다른 스레드에 의해 제거됨) 풋 작업을 차단한다.

내가 알기로는 너의 사소한 실행이 그런 행동을 하는 가장 쉬운 방법인 것으로 알고 있다.

MinMaxPriority를 사용할 수 있음Google Guava에서, Javadoc에서 대기열:

최소-최대 우선 순위 대기열은 최대 크기로 구성할 수 있다.만일 그렇다면, 큐의 크기가 그 값을 초과할 때마다, 큐는 비교기( 방금 추가된 요소일 수도 있음)에 따라 자동으로 가장 큰 요소를 제거한다.이는 가득 차면 새로운 요소를 차단하거나 거부하는 기존의 경계 대기열과는 다르다.

LRUMAP는 아파치 커먼즈에서도 가능하다.

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html

좋아, 내가 이 옵션을 공유할게.이것은 내부적으로 배열을 사용하고 항목을 재사용하는 꽤 효과적인 옵션이다.그것은 안전한 스레드 입니다. 그리고 당신은 목록으로 내용을 검색할 수 있다.

static class FixedSizeCircularReference<T> {
    T[] entries

    FixedSizeCircularReference(int size) {
        this.entries = new Object[size] as T[]
        this.size = size
    }
    int cur = 0
    int size

    synchronized void add(T entry) {
        entries[cur++] = entry
        if (cur >= size) {
            cur = 0
        }
    }

    List<T> asList() {
        int c = cur
        int s = size
        T[] e = entries.collect() as T[]
        List<T> list = new ArrayList<>()
        int oldest = (c == s - 1) ? 0 : c
        for (int i = 0; i < e.length; i++) {
            def entry = e[oldest + i < s ? oldest + i : oldest + i - s]
            if (entry) list.add(entry)
        }
        return list
    }
}

    public class ArrayLimitedQueue<E> extends ArrayDeque<E> {

    private int limit;

    public ArrayLimitedQueue(int limit) {
        super(limit + 1);
        this.limit = limit;
    }

    @Override
    public boolean add(E o) {
        boolean added = super.add(o);
        while (added && size() > limit) {
            super.remove();
        }
        return added;
    }

    @Override
    public void addLast(E e) {
        super.addLast(e);
        while (size() > limit) {
            super.removeLast();
        }
    }

    @Override
    public boolean offerLast(E e) {
        boolean added = super.offerLast(e);
        while (added && size() > limit) {
            super.pollLast();
        }
        return added;
    }
}

참조URL: https://stackoverflow.com/questions/5498865/size-limited-queue-that-holds-last-n-elements-in-java