Zusammenfassung

Abbildung 15: Ressourcenverbrauch für die Invertierung von 5 Gbytes.

Abbildung 15 zeigt sowohl Platz- als auch Zeitkomplexität der hier vorgestellten Algorithmen. Einige Bemerkungen sind an dieser Stelle angebracht.

Die höhere Zeitkomplexität des sortierbasierten und komprimierten Algorithmus gegenüber dem einfachen sortierbasierten Algorithmus bedarf einer genaueren Erklärung. Die Einträge der temporären Datei können nur dann komprimiert werden, wenn sie vom Anfang an sortiert vorliegen. Das war beim einfachen sortierbasierten Algorithmus nicht der Fall, erst nach einer internen Sortierphase lagen sortierte Läufe vor. Damit die temporäre Datei schon bei ihrer Erzeugung sortierte Bereiche enthält, müssen diese zuerst im Speicher sortiert werden, und werden erst danach auf Platte geschrieben. Um dies zu bewerksteligen, braucht man sowohl für die interne Datenstruktur, die die Terme aufnimmt, als auch für den Sortierpuffer Speicher. Es ist klar, daß dadurch weniger Einträge gleichzeitig für die interne Sortierung im Speicher gehalten werden können, es entstehen mehr Läufe, deren Zusammenfügen logischerweise auch mehr Zeit in Anspruch nimmt.

Für die sortierbasierten und komprimierten Algorithmen wurde in Abbildung 15 der Bedarf an Sekundärspeicher als 600 Mbytes angegeben. Strenggenommen müsste hier das Doppelte stehen, denn es werden während der merge-Phase zwei solche Dateien benötigt. Man muß aber auch das Ergebnis der Inversion (die invertierte Datei) betrachten, und das ist nun mal eine Datei der selben Größenordnung wie eine temporäre Datei. Diese drei Dateien sind aber niemals alle zur gleichen Zeit zu speichern, die eine temporäre Datei kann nämlich gelöscht werden, sobald mit der Erstellung der invertierten Datei begonnen wird.