Amortisierte Analyse
Lesen anpassen
Nach dieser Lektion kannst du
erklären, warum ein dynamisches Array mit Verdopplung pro Anhängen amortisiert konstant viel kostet,
amortisierte Kosten mit der Aggregatmethode, der Buchhaltermethode und der Potentialmethode bestimmen,
den Binärzähler mit allen drei Methoden analysieren,
begründen, warum man ein Array erst bei Viertelfüllung halbiert,
amortisierte Kosten vom Durchschnittsfall unterscheiden.
Vorausgesetzt: Laufzeit messen: Operationen zählen und O-Notation, Rekursion und Rekurrenzgleichungen
Listen in Python oder Java können beliebig wachsen: Du hängst ein Element nach dem anderen an, ohne vorher die Länge festzulegen. Im Speicher liegt aber ein Feld fester Länge. Ist es voll, muss das Programm ein größeres Feld anlegen und alle Elemente umkopieren. Bei einer Liste mit einer Million Elementen kostet dieses eine Anhängen eine Million Kopierschritte.
Die schlechteste Laufzeit einer einzelnen Operation ist also . Wer daraus schließt, dass Anhängeoperationen kosten, hat zwar recht, aber die Schranke ist viel zu grob: Die teuren Operationen sind selten, und zwischen zwei teuren liegen viele billige.
Die amortisierte Analyse nimmt diese Beobachtung ernst. Sie schätzt die Gesamtkosten einer ganzen Folge von Operationen ab und verteilt sie gleichmäßig auf die einzelnen Operationen, wie man eine große Anschaffung auf viele Monate umlegt. Wahrscheinlichkeiten kommen dabei nicht vor: Das Ergebnis gilt für jede Folge, auch die ungünstigste.
Ein Feld wird jedes Mal, wenn es voll ist, auf die doppelte Kapazität vergrößert, und alle Elemente werden umkopiert. Wie hoch sind die Gesamtkosten von Anhängeoperationen, beginnend mit einem leeren Feld?
Dynamisches Array mit Verdopplung
Ein dynamisches Array besteht aus einem Feld der Länge (Kapazität) und der Zahl der belegten Plätze. Es beginnt leer mit . Anhängen:
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 2 | |
| 4 | 2 | |
| 5 | 2 | |
| 6 | 1 | |
| 7 | 1 |
Als Kosten zählen wir die Schreibzugriffe auf Elemente: für Zeile 6 und je für jede Kopie in Zeile 4. Die -te Anhängeoperation kostet also , wenn Platz frei ist, und , wenn vorher Elemente in einem vollen Feld lagen:
| danach |
Amortisierte Kosten
Betrachte eine Datenstruktur, die leer beginnt, und eine Folge von Operationen mit tatsächlichen Kosten . Weist man jeder Operation einen Betrag zu, sodass für jede solche Folge und jedes
gilt, dann heißen die amortisierte Kosten. Sind alle für eine Konstante , so kosten Operationen zusammen höchstens , und man sagt, eine Operation kostet amortisiert .
Das ist eine Garantie für den schlechtesten Fall, aber über die ganze Folge statt für jede einzelne Operation. Eine einzelne Operation darf teuer sein. Es gibt drei Methoden, amortisierte Kosten nachzuweisen.
Aggregatmethode für das dynamische Array
Die Aggregatmethode berechnet direkt die Gesamtkosten und teilt durch . Für das dynamische Array mit Verdopplung gilt: Anhängeoperationen ab dem leeren Feld kosten zusammen weniger als . Jede kostet also amortisiert höchstens .
Jede Operation schreibt ihr eigenes Element, das ergibt . Kopiert wird nur, wenn vor der Operation das Feld voll ist. Weil die Kapazität nacheinander die Werte annimmt, geschieht das bei den Füllständen , und dabei werden Elemente kopiert. Die Füllstände vor den Operationen sind bis .
Die Kopien zusammen sind also , wobei die größte Zweierpotenz mit ist (für gibt es keine Kopie). Nach der Formel für die geometrische Summe ist das . Zusammen mit den eigenen Schreibzugriffen bleiben die Gesamtkosten unter .
Wie hoch sind die tatsächlichen Gesamtkosten der ersten Anhängeoperationen in der Tabelle oben?
Buchhaltermethode: jedes Element zahlt seinen Umzug im Voraus
Buchhaltermethode: jedes Element zahlt seinen Umzug im Voraus
Die Buchhaltermethode (auch Kontomethode) legt für jede Operation einen festen Preis fest. Ist der Preis höher als die tatsächlichen Kosten, wird der Rest als Guthaben in der Datenstruktur gespeichert, zum Beispiel an einem bestimmten Element. Eine teure Operation bezahlt aus dem Guthaben. Darf das Guthaben nie negativ werden, so sind die Gesamtkosten höchstens die Summe der Preise.
Beim dynamischen Array verlangen wir pro Anhängen. Davon bezahlt das Schreiben des neuen Elements, und werden an diesem Element als Guthaben abgelegt.
Warum reicht das? Kurz nach einer Verdopplung von Kapazität auf liegen alte Elemente im Feld, deren Guthaben für die Kopie gerade verbraucht wurde. Bis das Feld wieder voll ist, kommen neue Elemente dazu, die zusammen Guthaben mitbringen. Die nächste Verdopplung kopiert genau Elemente und wird damit vollständig bezahlt. Jedes neue Element bezahlt also seinen eigenen künftigen Umzug und den Umzug eines alten Elements, das nichts mehr hat.
Die erste Verdopplung von auf kopiert nichts, die von auf kopiert ein Element mit Guthaben . Das Guthaben ist also nie negativ, und Operationen kosten höchstens .
Potentialmethode
Statt Guthaben an einzelne Elemente zu heften, misst die Potentialmethode das gespeicherte Guthaben mit einer Funktion (gesprochen „Phi“), die jedem Zustand der Datenstruktur eine reelle Zahl zuordnet. Sei der leere Anfangszustand und der Zustand nach der -ten Operation. Man verlangt und für alle und definiert
.
Eine billige Operation, die das Potential erhöht, spart an. Eine teure Operation, die das Potential stark senkt, gibt Erspartes aus. Beim Summieren heben sich die Potentiale bis auf das erste und das letzte weg (Teleskopsumme):
Potentialmethode für das dynamische Array
Potentialmethode für das dynamische Array
Wähle . Am Anfang ist . Nach jeder Operation ist das Feld mindestens halb voll, also .
Anhängen ohne Vergrößern: , steigt um , bleibt. Also steigt um :
Der Binärzähler mit allen drei Methoden
Der Binärzähler mit allen drei Methoden
Ein Zähler aus Bits beginnt bei ; ist das niedrigste Bit. Erhöhen um setzt die Einsen am Ende auf und die erste Null auf :
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 2 | |
| 5 | 1 |
Die Kosten sind die Zahl der geänderten Bits. Von nach ändern sich vier Bits, von nach nur eines. Die ersten acht Erhöhungen kosten , zusammen . Eine einzelne Erhöhung kann kosten.
Aggregat: Bit ändert sich bei jeder -ten Erhöhung, in Erhöhungen also Mal. Zusammen sind das weniger als .
Buchhalter: Preis . Davon bezahlt das Setzen eines Bits auf , und bleibt als Guthaben an diesem Bit liegen. Wird das Bit später auf gesetzt, bezahlt es das selbst. Jede Eins trägt also stets Guthaben.
Potential: ist die Zahl der Einsen. Sind bis Einsen, aber eine Null (mit ), kostet die Erhöhung , und die Zahl der Einsen ändert sich um :
Läuft der Zähler über (alle Bits sind ), kostet die Erhöhung und fällt um , also . In jedem Fall ist , und Erhöhungen ab ändern weniger als Bits, unabhängig von .
Ein Feld wird nicht verdoppelt, sondern bei jedem Vollsein um genau einen Platz vergrößert (Kapazität ). Wie viele Kopien entstehen bei Anhängeoperationen ab dem leeren Feld?
Schrumpfen: warum erst bei einem Viertel halbieren?
Schrumpfen: warum erst bei einem Viertel halbieren?
Wenn Elemente am Ende entfernt werden, soll das Feld wieder kleiner werden, damit nicht viel Speicher leer bleibt. Entfernen kostet , Halbieren der Kapazität kopiert alle Elemente in ein halb so langes Feld.
Naheliegend wäre: halbieren, sobald das Feld nur noch halb voll ist. Nimm ein volles Feld mit Elementen und Kapazität , und hänge dann abwechselnd an und entferne:
| Operation | Kosten | Füllstand / Kapazität danach |
|---|---|---|
| anhängen | ||
| entfernen, halbieren | ||
| anhängen | ||
| entfernen, halbieren |
Jede Operation kostet etwa , eine Folge von solchen Operationen . Das Feld springt an der Grenze hin und her.
Die Lösung: halbieren erst, wenn nach dem Entfernen nur noch ein Viertel belegt ist (, für ). Nach jeder Größenänderung ist das Feld dann ungefähr halb voll. Bis zur nächsten Änderung muss es entweder ganz voll werden (etwa Anhängeoperationen) oder auf ein Viertel fallen (etwa Entfernungen). Die nächste Größenänderung kopiert höchstens Elemente, und davor liegen mindestens etwa billige Operationen, die sie bezahlen können. Im Beispiel oben kosten dieselben abwechselnden Operationen zusammen nur statt .
Mit diesem Potential rechnet man nach, dass jede Operation, Anhängen wie Entfernen, amortisiert höchstens kostet. Das Potential wächst, wenn sich der Füllstand von der Hälfte entfernt, nach oben wie nach unten, und spart so für die nächste Größenänderung an. Eine der Rechnungen führst du in den Übungen.
Amortisiert heißt nicht „im Durchschnitt bei zufälligen Eingaben“
Amortisiert heißt nicht „im Durchschnitt bei zufälligen Eingaben“
Man liest „Anhängen kostet amortisiert “ und schließt: Im Durchschnitt über alle möglichen Eingaben ist Anhängen schnell, aber bei ungünstigen Eingaben kann eine lange Folge von Operationen trotzdem quadratisch teuer werden. Oder umgekehrt: Jede einzelne Operation ist in .
Beides stimmt nicht. Die amortisierte Schranke gilt für jede Folge von Operationen, auch die ungünstigste, ohne Wahrscheinlichkeiten. Sie garantiert die Gesamtkosten , nicht die Kosten jeder einzelnen Operation: Ein einzelnes Anhängen kann kosten. Die Durchschnittsanalyse dagegen mittelt über zufällige Eingaben. Quicksort mit dem ersten Element als Pivot braucht im Mittel über alle Anordnungen Vergleiche, auf einer sortierten Eingabe aber , und das jedes Mal. Wo jede einzelne Operation schnell sein muss, etwa in Echtzeitsystemen, hilft eine amortisierte Schranke nicht.
Zusammenfassung
Amortisierte Analyse schätzt die Gesamtkosten einer Folge von Operationen im schlechtesten Fall ab und verteilt sie auf die Operationen.
Ein dynamisches Array mit Verdopplung kostet für Anhängeoperationen weniger als , also amortisiert pro Operation, obwohl eine einzelne kosten kann.
Aggregatmethode: Gesamtkosten direkt summieren, hier mit einer geometrischen Summe.
Buchhaltermethode: fester Preis pro Operation, der Überschuss liegt als Guthaben in der Datenstruktur und darf nie negativ werden.
Potentialmethode: mit und ; die Summe teleskopiert.
Binärzähler: Erhöhungen ändern weniger als Bits; Potential ist die Zahl der Einsen.
Wachstum um einen konstanten Faktor ist nötig; Wachstum um eine konstante Zahl führt zu . Halbiert wird erst bei Viertelfüllung, sonst springt das Feld an der Grenze hin und her.
Amortisiert ist eine Garantie für jede Folge, keine Aussage über zufällige Eingaben und keine Schranke für jede einzelne Operation.
Übungen
Ein dynamisches Array mit Verdopplung beginnt leer mit Kapazität . Wie hoch sind die tatsächlichen Gesamtkosten (Schreibzugriffe einschließlich Kopien) von Anhängeoperationen?
Ein Binärzähler mit genügend vielen Bits beginnt bei und wird -mal erhöht. Wie viele Bits ändern sich insgesamt?
Ein Feld wächst immer um Plätze, wenn es voll ist (Kapazität ). Wie viele Kopien entstehen bei Anhängeoperationen ab dem leeren Feld?
Was garantiert die Aussage „Diese Operation kostet amortisiert “ für eine Datenstruktur, die leer beginnt?
Ein dynamisches Array verdreifacht seine Kapazität, wenn es voll ist (Kapazität ). Zeige mit der Aggregatmethode, dass Anhängeoperationen ab dem leeren Feld zusammen weniger als Schreibzugriffe kosten.
Der Binärzähler mit Bits soll jetzt auch vermindern können (um verringern; dabei werden die Nullen am Ende zu Einsen und die letzte Eins zu einer Null). Zeige, dass dann Operationen ab einem geeigneten Zählerstand Bitänderungen kosten können. Warum versagt das Potential „Zahl der Einsen“?
Das Feld halbiert seine Kapazität, wenn nach dem Entfernen gilt (). Zeige mit dem Potential aus der Lektion ( für , sonst ), dass ein Entfernen mit Halbieren amortisiert höchstens kostet.