Queue Implementierung

[Wippi11223]

Hallo,

Ich bin auf der Suche nach einer einfachen limitierten Queue auf Basis FIFO.
Dieser Datenspeicher soll x Elemente halten wenn ich das x+1 hinzufüge fliegt das erste aus der Queue. Die Queues die ich gefunden habe sind aber alle speziell und meiner Meinung nach nicht dafür geeignet:

• ConcurrentLinkedQueue

• DelayQueue

• ArrayBlockingQueue

• LinkedBlockingQueue

• PriorityQueue

• PriorityBlockingQueue

Wie kann ich dies umsetzen?

Vielen Dank

 

[VfL_Freak]

Moin,

hier mal zwei Links, die Dir weiterhelfen sollten:
https://stackoverflow.com/questions/5498865/size-limited-queue-that-holds-last-n-elements-in-java
https://commons.apache.org/proper/c...ons/collections4/queue/CircularFifoQueue.html

VG Klaus

 

[httpdigest]

Was du suchst, nennt sich "Ring Buffer". Solche Datenstrukturen können gut als FIFO eingesetzt werden.
Ich habe dir mal schnell eine Beispielimplementierung gebaut:

import java.lang.reflect.Array;
import java.util.NoSuchElementException;
class RingBuffer<T> {
    private T[] array;
    private int size, write;
    public RingBuffer(int capacity) {
        array = createGenericArray(capacity);
    }
    @SafeVarargs
    @SuppressWarnings("unchecked")
    private T[] createGenericArray(int capacity, T... _dummy) {
        return (T[]) Array.newInstance(_dummy.getClass().getComponentType(), capacity);
    }
    public void add(T value) {
        array[write] = value;
        write = (write + 1) % array.length;
        size = Math.min(size + 1, array.length);
    }
    public int size() {
        return size;
    }
    public T get() {
        if (size == 0)
            throw new NoSuchElementException();
        return array[Math.floorMod(write - size--, array.length)];
    }
}
public class RingBufferTest {
    public static void main(String[] args) {
        RingBuffer<Integer> rb = new RingBuffer<>(4);
        rb.add(1);
        rb.add(2);
        rb.add(3);
        rb.get();
        rb.add(4);
        rb.add(5);
        while (rb.size() > 0) {
            System.out.println(rb.get());
        }
    }
}

 

[Wippi11223]

super vielen Dank!! genau das was ich suche...eine Frage noch:
Ich habe folgende Anforderung: ich bekomme kontinuierlich (also jede Sekunde eine 0 oder 1).
Ich möchte mir die Ratio ausrechnen von einem gewissen Zeitraum. Meine Idee wäre hier einen Queue zu implementieren wo ich mir 15 Werte speichere und mir die Ratio berechne: Summe aller Werte/Queue Size

Oder gibt es dafür eine einfachere Implementierung?

 

[httpdigest]

Es ist immer interessant, wenn Leute ihren tatsächlichen Use-Case nennen, nachdem dann Fragen zu einer Lösung diskutiert wurden, die eher dafür ungeeignet ist.
Wenn du also nur Bits hast, dann kannst du dafür wunderbar ein Bitset (in Form eines einfachen ints) nehmen:

public class RunningBits {
    private final int bitmask;
    private final int capacity;
    private int bits;
    private int size;
    RunningBits(int capacity) {
        if (capacity < 1 || capacity > 32)
            throw new IllegalArgumentException();
        this.bitmask = (1 << capacity) - 1;
        this.capacity = capacity;
    }
    public void add(int bit) {
        bits = bits << 1 & bitmask | bit & 1;
        size = Math.min(size + 1, capacity);
    }
    public float ratio() {
        return (float) Integer.bitCount(bits) / size;
    }
    public static void main(String[] args) {
        RunningBits bits = new RunningBits(15);
        bits.add(1);
        bits.add(0);
        bits.add(1);
        bits.add(1);
        bits.add(0);
        bits.add(0);
        System.out.println(bits.ratio());
    }
}

 

[Wippi11223]

Vielen Dank werde mich bessern
es sind aber nicht nur bits --> es kann sein dass ich hier auch Timestamps und double drin sind

 

[mrBrown]

Für so einen gleitenden Mittelwert kann man schon einen RingPuffer nutzen (das Bitset ist ja in dem Beispiel nichts anderes, nur eben für Bits optimiert).

Entweder eine fertige Implementierung (Apache Commons und Google Guava müssten beide passendes haben) oder eben was eigenes, was im Hintergrund einfach ne bestehende Queue/List nutzt.