Sauron hat in seinem Heer von Untergebenen nur eine begrenzte Menge an Platz. Als Ringliebhaber möchte er diese Untergebenen in einem sogenannten Ringbuffer organisieren.
Untergebene werden in der Reihenfolge des Eintritts in sein Heer gespeichert. Möchte Sauron mal einen Untergebenen loswerden, entfernt er immer den “dienstältesten” (am frühesten in das Heer eingetretenen) Untergebenen zuerst. Möchte Sauron einen neuen Untergebenen in sein Heer aufnehmen, hat aber keinen Platz mehr, wird der älteste untergebene automatisch durch den neuen Untergebenen ersetzt. Sauron möchte außerdem zu jedem Zeitpunkt erfahren können, wie viele Untergebene teil seines Heers sind, und wieviel Platz in seinem Heer ist.
RingBuffer(capacity): Erzeugt einen neuen Ringbuffer mit Kapazität capacity.RingBuffer.push(e): Fügt das Element e als neuestes Element in den Ringbuffer ein. Ist der Ringbuffer voll, wird das älteste Element verdrängt (und das bis dahin zweitälteste Element wird somit zum ältesten Element).RingBuffer.pop(): Gibt das älteste (am frühesten Eingefügte) Element des Ringbuffers aus (welches sich noch im Speicher befindet) und entfernt es aus dem Ringbuffer (aber nicht gezwungenermaßen aus dem unterliegenden Speicher). Ist der Ringbuffer leer, wird None zurückgegeben.RingBuffer.peek(): Gibt das älteste Element des Ringbuffers aus, ohne es zu entfernen. Ist der Ringbuffer leer, wird None zurückgegeben.len(RingBuffer): Gibt die Anzahl an Elementen, welche sich aktuell im Ringbuffer befinden, aus. Siehe auch die Dokumentation zu “special method names” __len__.RingBuffer.capacity: Gibt zurück wie viele Elemente in den Ringbuffer passen.Du kannst das folgende Template benutzen um deinen Ringbuffer zu Implementieren. Die Tests können dabei Helfen zu überprüfen, ob deine Implementierung korrekt ist. Sie werden mit Ausführung der Datei ausgeführt.
from typing import Any, Optional
class RingBuffer:
def __init__(self, capacity: int):
pass
def __len__(self) -> int:
raise NotImplementedError
def push(self, element: Any):
raise NotImplementedError
def pop(self) -> Optional[Any]:
raise NotImplementedError
def peek(self) -> Optional[Any]:
raise NotImplementedError
def test():
# Test normal operation without overwrites
buffer = RingBuffer(3)
assert buffer.capacity == 3
assert len(buffer) == 0
buffer.push(1)
buffer.push(3)
buffer.push(4)
assert buffer.peek() == 1
assert len(buffer) == 3
assert buffer.pop() == 1
assert buffer.pop() == 3
assert buffer.pop() == 4
assert buffer.pop() is None
# Test operation with overwrites
buffer.push(10)
buffer.push(20)
buffer.push(30)
buffer.push(40)
buffer.push(50)
assert buffer.pop() == 30
assert buffer.pop() == 40
assert buffer.pop() == 50
assert buffer.pop() is None
if __name__ == "__main__":
test()
Zur Speicherung der Daten eignet sich zum beispiel eine list.
Diese sollte beim initialisieren der Klasse die feste Größe capacity bekommen.
Das lässt sich zum beispiel durch self.buffer = [None for _ in range(capacity)] in der __init__ Methode realisieren.
Hierfür speichert man sich am besten zwei Attribute self.newest und self.oldest, welche den Index des aktuell neuesten und ältesten Elements beinhalten.
Ist der unterliegende buffer leer, kann es sinnvoll sein in self.newest den Index zu speichern vor dem man als nächstes einfügen möchte, und in self.oldest genau den Index zu speichern, in den man als nächstes Einfügt.
Das ist aber kein muss, sondern nur optimierung.
Bei einem push oder pop müssen diese Indizes gegebenenfalls verschoben werden.
Wenn der unterliegende Speicher eine Länge von 3 hat (also der größte Index 2 ist) und unser neuestes Element bereits am Index 2 liegt, wäre der nächste Index zum Einfügen der Index 0 (also quasi am “rechten” Rand / Ende des Speichers raus, und am linken Rand / Anfang wieder angefangen).
Um bei einer Inkrementierung des Indexes auch auf diesen Wert zu kommen, kann der Modulo operator % zusammen mit der Kapazität des Ringbuffers genutzt werden.