Ich suche nach einer Antwort auf diese Frage, die aus einer Klasse über Datenstrukturen und Algorithmen stammt. Ich habe von der Merge-Sortierung erfahren, erinnere mich aber nicht an Cluster und Puffer. Ich bin mir nicht ganz sicher, ob ich die Frage verstehe. Kann jemand helfen, es zu erklären oder zu beantworten?
Eine Datei der Größe 1 Million Cluster ist mit 128 Eingabepuffern sortiert werden einer Clustergröße. Da ist ein Ausgabepuffer einer Clustergröße. Wie Viele Disk I / O werden benötigt, wenn der balanced k-way merge sort (a Mehrschritt-Merge) -Algorithmus wird verwendet?
Es fragt nach der Gesamtzahl der Festplattenoperationen, ein Cluster kann hier eine beliebige Größe haben.
Sie müssen wissen, wie viele Disk-IOs pro Iteration einer ausgeglichenen K-Way-Merge-Sortierung benötigt werden. (Hinweis: Jeder Merge-Pass erfordert das Lesen und Schreiben aller Werte im Array von und auf die Festplatte)
Dann berechnen Sie, wie viele Iterationen durchgeführt werden müssen, um Ihre Daten zu lesen.
Die Gesamtzahl der Platten-IOs kann dann berechnet werden.
Tags und Links data-structures