Schritt-für-Schritt-Anleitung zur Berechnung der Fusionskosten bei externer Sortierung

Externe Sortierung ist eine Technik, die verwendet wird, um große Datensätze zu verarbeiten, die nicht in den Hauptspeicher passen. Ein wichtiger Aspekt der externen Sortierung ist die Berechnung der Fusionskosten, was hilft, die Effizienz des Sortierprozesses zu bestimmen.

Externe Sortierung verstehen

Externe Sortierung beinhaltet die Aufteilung der Daten in überschaubare Brocken, die Sortierung jedes Brockens einzeln und dann die Zusammenführung dieser sortierten Brocken in eine einzige sortierte Datei. Der Zusammenführungsprozess kann in Abhängigkeit von der Anzahl der Brocken und dem verfügbaren Speicher in mehreren Durchgängen durchgeführt werden.

Komponenten der Fusionskosten

Die Kosten für die Zusammenführung hängen in erster Linie von der Anzahl der Durchgänge und der Menge der Daten ab, die während jedes Durchgangs verarbeitet werden.

• Anzahl der sortierten Erstläufe (Chunks)
• Die Anzahl der Dateien gleichzeitig zusammengeführt (Fan-in)
• Gesamtgröße der Daten

Berechnung der Fusionskosten

Die Gesamtkosten für Zusammenschlüsse können nach folgender Formel berechnet werden:

Merge Cost = Anzahl der Pässe × Gesamtdaten, die in jedem Pass verarbeitet werden

Um die Anzahl der Pässe zu bestimmen, verwenden Sie die Formel:

Zahl der Pässe = log_fan-in (Anzahl der Erstläufe))

Wenn es beispielsweise 16 erste Durchläufe gibt und das System 4 Dateien gleichzeitig zusammenführen kann, dann:

Anzahl der Pässe = log₄ 16 = 2

Die Gesamtdaten, die in jedem Durchgang verarbeitet werden, entsprechen der Gesamtgröße aller Daten, die während dieses Durchgangs zusammengeführt werden.