Warteschlangen (Queues)

Den ersten von 1000 Werten mit shift aus einem JavaScript-Array zu nehmen, verschiebt die anderen 999; ein Ringpuffer erledigt dieselbe Aufgabe in einem Schritt.

First in, first out

Eine Warteschlange ist wie die Schlange an einer Ladenkasse. Man stellt sich hinten an und wird vorn bedient, also geht als Erstes, wer zuerst kam. Die Regel heißt first in, first out (FIFO). Die beiden Operationen sind Einreihen (enqueue), das einen Wert hinten anfügt, und Entnehmen (dequeue), das den Wert vorn entfernt. In den Unterlagen von MIT 6.006 ist eine Warteschlange die Sequenz-Schnittstelle, beschränkt auf insert last(x) und delete first().

Warteschlangen gibt es überall, wo Arbeit in der Reihenfolge des Eintreffens erledigt werden muss: Dokumente, die auf einen Drucker warten, Tastendrücke, die auf ein Programm warten, Nachrichten, die auf einen Server warten. Die Breitensuche aus dem Algorithmenkurs hält die Felder, die sie noch besuchen muss, in einer Warteschlange, und genau deshalb erkundet sie in Ringen gleichen Abstands.

Der einfache Weg und seine versteckten Kosten

In JavaScript ist die naheliegende Warteschlange ein Array: push zum Einreihen hinten und shift zum Entnehmen vorn. Das funktioniert, und für kurze Warteschlangen ist es in Ordnung. Aber sieh dir an, was shift tut. MDN sagt, es verschiebe „alle Werte um 1 nach links“, und die ECMAScript-Spezifikation schreibt es als Schleife, die für jedes k das Element k an Position k − 1 kopiert. Der Anfang eines Arrays ist das teure Ende, wie die erste Einheit gezeigt hat. Das Entnehmen aus einer Warteschlange mit n Werten kostet 1 Lesevorgang plus n − 1 Verschiebungen, eine Warteschlange mit 1000 Werten kostet also 1000 Schritte pro Entnahme. (Engines nutzen intern vielleicht Abkürzungen, aber die Spezifikation verspricht keine.)

Reihst du 5 Werte in ein leeres Array ein und entnimmst dann alle 5, kosten die Einreihungen 5 Schritte und die Entnahmen 5 + 4 + 3 + 2 + 1 = 15, zusammen 20. Das meiste davon ist das Verschieben von Werten, die gar nicht entfernt werden.

Nicht die Werte bewegen, sondern den Anfang

Die Lösung: aufhören, Werte zu verschieben, und sich stattdessen merken, wo der Anfang ist. Führ einen Index namens head. Entnehmen liest den Wert bei head und erhöht head um 1; sonst bewegt sich nichts. Der Haken: Die Zellen vor head sind verschwendet. Ein Ringpuffer (zirkulärer Puffer) verwendet sie wieder: Das Array hat eine feste Zahl von Zellen, sagen wir 8, und die Positionen laufen im Kreis, die Zelle nach 7 ist also 0. Speichere head und size. Das nächste Einreihen geht in Zelle (head + size) mod 8, und ein Entnehmen nimmt Zelle head und setzt head auf (head + 1) mod 8. Beide Operationen kosten 1 Schritt. Der Preis ist eine feste Kapazität: Erreicht size den Wert 8, ist die Warteschlange voll, außer du kopierst alles in einen größeren Ring, wie es ein dynamisches Array tun würde.

Was solltest du nehmen? Für eine Warteschlange, die nie mehr als ein paar Dutzend Werte enthält, ist push und shift kurz und klar, und das Verschieben kostet fast nichts. Für eine Warteschlange, durch die Tausende Elemente laufen, etwa die Felder einer großen Breitensuche, hält ein head-Index oder ein Ringpuffer jedes Entnehmen bei einem Schritt, und der Unterschied wächst mit der Länge der Schlange.