Invarianten vor Algorithmen¶
Eine nützliche Invariante sagt, was während des Algorithmus gilt und worauf der Aufrufer danach vertrauen darf. Schreiben Sie sie vor der Schleife.
Teilbaumintervalle in Präorder¶
Der Baum werde in Präorder ausgegeben: Jeder Knoten kommt vor seinen Kindern, jeder Teilbaum ist zusammenhängend. \(e_i\) sei der erste Index nach Knoten \(i\) und allen seinen Nachfahren.
Behauptung. Der Durchlauf kann den Teilbaum überspringen, indem er zu \(e_i\) vorrückt.
Beweis. Wegen der Zusammenhängigkeit liegen alle Nachfahren vor \(e_i\). Nach Definition des exklusiven Endes liegen spätere Knoten bei \(e_i\) oder dahinter. Der Sprung überspringt daher genau den Teilbaum. Der Validator prüft die Voraussetzungen, bevor ein Renderer darauf vertraut.
Ein vollständiger Durchlauf besucht jeden Knoten einmal und kostet \(O(N)\). Ein Teilbaumsprung erfordert nur eine Indexänderung. Nutzdatenverarbeitung hat weiterhin ihre eigenen Kosten. Ein Sprung in konstanter Zeit bedeutet keine Darstellung in konstanter Zeit.
Vor der Ausgabe messen¶
Der Renderer misst zunächst die Bytezahl \(m\). Die Ausgabekapazität des Aufrufers sei \(c\).
Messung und Ausgabe folgen denselben Regeln. Eine erfolgreiche Ausgabe schreibt genau \(m\) Bytes. Fehler liefern kein gültiges Teilartefakt. Der Host verwaltet die Veröffentlichung; unvollständige Bytes können daher keine frühere Ausgabe ersetzen.
Gültigkeit des Caches¶
Ein Cache-Schlüssel muss alle ergebniswirksamen Daten erfassen. Quellen allein genügen nicht: Includes, Vorlagen, Konfiguration, Referenzauflösung, Ressourcen und Adapterversionen wirken mit. Wiederverwendung setzt übereinstimmende dokumentierte Abhängigkeiten voraus. Fehlende Ausgabe verhindert sie auch bei passendem Schlüssel.
Tests setzen fehlschlagende Allokatoren an der Kerngrenze ein und vergleichen die Ausgabe. Sie prüfen auch Imports. Bloßes Zählen von Allokationen könnte eine Ablehnung übersehen, die Dokumentteile stillschweigend verwirft.