source

과도한 요소를 제거하는 고정 크기의 큐가 있습니까?

lovecheck 2022. 11. 28. 21:15
반응형

과도한 요소를 제거하는 고정 크기의 큐가 있습니까?

일정한 크기의 큐가 필요합니다.요소를 추가하고 큐가 꽉 차면 가장 오래된 요소가 자동으로 삭제됩니다.

이를 위한 기존 구현이 Java에 있습니까?

실제로 Linked Hash Map은 사용자가 원하는 대로 작동합니다.재지정할 필요가 있습니다.removeEldestEntry★★★★★★ 。

요소가 최대 10개인 큐의 예:

  queue = new LinkedHashMap<Integer, String>()
  {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest)
     {
        return this.size() > 10;   
     }
  };

removeEldestEntry가 true를 반환하면 가장 오래된 엔트리가 맵에서 삭제됩니다.

네, 둘

이 정답을 가진 나의 중복된 질문에서 나는 두 가지를 배웠다.


는 구아바를 했다.EvictingQueue , 잘 작동했습니다.

EvictingQueuestatic factory 메서드를 호출하여 최대 크기를 지정합니다.

EvictingQueue< Person > people = com.google.common.collect.EvictingQueue.create( 100 ) ;  // Set maximum size to 100. 

고정 크기 큐를 다음과 같이 구현했습니다.

public class LimitedSizeQueue<K> extends ArrayList<K> {

    private int maxSize;

    public LimitedSizeQueue(int size){
        this.maxSize = size;
    }

    public boolean add(K k){
        boolean r = super.add(k);
        if (size() > maxSize){
            removeRange(0, size() - maxSize);
        }
        return r;
    }

    public K getYoungest() {
        return get(size() - 1);
    }

    public K getOldest() {
        return get(0);
    }
}

Java Language 및 Runtime에는 기존 구현이 없습니다.모든 큐는 AbstractQueue를 확장하며, 해당 문서에는 요소를 전체 큐에 추가하는 것이 항상 예외로 끝난다고 명시되어 있습니다.필요한 기능을 갖추기 위해 큐를 자신의 클래스로 정리하는 것이 가장 좋습니다(그리고 매우 간단합니다).

다시 한 번 말하지만 모든 큐는 Abstract Queue의 자식이기 때문에 이를 내부 데이터 유형으로 사용하면 유연한 구현을 거의 즉시 실행할 수 있습니다.-)

갱신:

아래에 개략적으로 설명한 바와 같이 두 가지 개방형 구현이 있습니다(이 답변은 상당히 오래되었습니다). 자세한 내용은 이 답변을 참조하십시오.

이게 내가 했던 일이야Queue로 wrapped로 .LinkedList

public static Queue<String> pageQueue;

pageQueue = new LinkedList<String>(){
            private static final long serialVersionUID = -6707803882461262867L;

            public boolean add(String object) {
                boolean result;
                if(this.size() < 2)
                    result = super.add(object);
                else
                {
                    super.removeFirst();
                    result = super.add(object);
                }
                return result;
            }
        };


....
TMarket.pageQueue.add("ScreenOne");
....
TMarket.pageQueue.add("ScreenTwo");
.....
public class CircularQueue<E> extends LinkedList<E> {
    private int capacity = 10;

    public CircularQueue(int capacity){
        this.capacity = capacity;
    }

    @Override
    public boolean add(E e) {
        if(size() >= capacity)
            removeFirst();
        return super.add(e);
    }
}

사용 및 테스트 결과:

public static void main(String[] args) {
    CircularQueue<String> queue = new CircularQueue<>(3);
    queue.add("a");
    queue.add("b");
    queue.add("c");
    System.out.println(queue.toString());   //[a, b, c]

    String first = queue.pollFirst();       //a
    System.out.println(queue.toString());   //[b,c]

    queue.add("d");
    queue.add("e");
    queue.add("f");
    System.out.println(queue.toString());   //[d, e, f]
}

지금 설명하시는 건 순환 큐인 것 같아요.여기 가 있고 여기 더 나은 예가 있습니다.

이 클래스는 상속(여기서 다른 답변) 대신 구성을 사용하여 작업을 수행하므로 특정 부작용의 가능성을 제거합니다(Essential Java에서 Josh Bloch에서 설명함).기본 LinkedList 트리밍은 add, addAll 및 offer 메서드에서 수행됩니다.

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class LimitedQueue<T> implements Queue<T>, Iterable<T> {

    private final int limit;
    private final LinkedList<T> list = new LinkedList<T>();

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

    private boolean trim() {
        boolean changed = list.size() > limit;
        while (list.size() > limit) {
            list.remove();
        }
        return changed;
    }

    @Override
    public boolean add(T o) {
        boolean changed = list.add(o);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return list.contains(o);
    }

    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return list.toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return list.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return list.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean changed = list.addAll(c);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return list.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return list.retainAll(c);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean offer(T e) {
        boolean changed = list.offer(e);
        boolean trimmed = trim();
        return changed || trimmed;
    }

    @Override
    public T remove() {
        return list.remove();
    }

    @Override
    public T poll() {
        return list.poll();
    }

    @Override
    public T element() {
        return list.element();
    }

    @Override
    public T peek() {
        return list.peek();
    }
}

add 메서드에 추가 스니펫이 포함되어 있어 너무 길면 목록이 잘리는 일반적인 목록처럼 들립니다.

너무 간단하면 문제의 설명을 편집해야 할 수도 있습니다.

SO 질문 또는 ArrayBlockingQueue도 참조하십시오(차단 주의, 고객님의 경우 바람직하지 않을 수 있습니다).

이 질문을 하게 된 계기가 된 요건이 무엇인지 명확하지 않습니다.고정 크기의 데이터 구조가 필요한 경우 다른 캐시 정책을 검토할 수도 있습니다.단, 큐가 있기 때문에 라우터 기능을 찾고 있는 것이 가장 좋은 추측입니다.이 경우 첫 번째 인덱스와 마지막 인덱스를 가진 배열인 링 버퍼로 하겠습니다.요소가 추가될 때마다 마지막 요소 인덱스를 증가시키고 요소가 제거되면 첫 번째 요소 인덱스를 증가시킵니다.두 경우 모두 어레이 크기를 모듈화하며 필요에 따라 다른 인덱스를 증가시킵니다.즉, 큐가 꽉 차거나 비어 있는 경우입니다.

또, 라우터 타입의 애플리케이션인 경우는, Random Early Dropping(RED; 랜덤 조기 드롭)등의 알고리즘을 사용해 시험해 보는 것도 좋습니다.Random Early Dropping(RED; 랜덤 조기 드롭)은, 큐가 가득 차기도 전에 랜덤하게 요소를 드롭 합니다.경우에 따라서는 RED가 폐기하기 전에 큐가 꽉 차도록 하는 단순한 방법보다 전체적인 퍼포먼스가 우수하다는 것이 판명되었습니다.

실제로 Linked List를 기반으로 자신의 임팩트를 작성할 수 있습니다.이것은 매우 간단합니다.add 메서드를 덮어쓰고 스태프를 수행하기만 하면 됩니다.

가장 잘 맞는 답은 이 질문에서 나온 것 같아요.

Apache Commons Collections 4에는 Circular Fifo Queue가 있습니다.이것이 당신이 찾고 있는 것입니다.javadoc 인용:

Circular Fifo Queue는 full일 경우 가장 오래된 요소를 대체하는 고정 크기의 선입선출 큐입니다.

심플한 솔루션은 아래 "String" 큐입니다.

LinkedHashMap<Integer, String> queue;
int queueKeysCounter;

queue.put(queueKeysCounter++, "My String");
queueKeysCounter %= QUEUE_SIZE;

이렇게 하면 큐에 있는 항목의 순서가 유지되지는 않지만 가장 오래된 항목이 대체됩니다.

OOP에서 알 수 있듯이 상속보다는 구성을 선호해야 합니다.

이 점을 염두에 둔 솔루션을 소개합니다.

package com.choiceview;

import java.util.ArrayDeque;

class Ideone {
    public static void main(String[] args) {
        LimitedArrayDeque<Integer> q = new LimitedArrayDeque<>(3);
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q);

        q.add(4);
        // First entry ie 1 got pushed out
        System.out.println(q);
    }
}

class LimitedArrayDeque<T> {

    private int maxSize;
    private ArrayDeque<T> queue;

    private LimitedArrayDeque() {

    }

    public LimitedArrayDeque(int maxSize) {
        this.maxSize = maxSize;
        queue = new ArrayDeque<T>(maxSize);
    }

    public void add(T t) {
        if (queue.size() == maxSize) {
            queue.removeFirst();
        }
        queue.add(t);
    }

    public boolean remove(T t) {
        return queue.remove(t);
    }

    public boolean contains(T t) {
        return queue.contains(t);
    }

    @Override
    public String toString() {
        return queue.toString();
    }
}

좋아요, 제 버전도 폐기하겠습니다. :-) 이것은 매우 퍼포먼스를 발휘하도록 설계되어 있습니다.중요할 때를 위해서입니다.Linked List를 기반으로 하지 않으며 스레드 안전합니다(적어도 안전합니다).선입선출

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
    }
}

언급URL : https://stackoverflow.com/questions/1963806/is-there-a-fixed-sized-queue-which-removes-excessive-elements

반응형