So sortieren Sie n^2 Elemente in 2n RAM

Kann mir bitte jemand sagen, wie man n^2 Elemente mit 2n RAM sortiert. Ein möglicher Ansatz ist die Aufteilung in n Arrays der Größe n. Und dann führe eine Merge-Sortierung innerhalb der n Elemente durch und lege dann schließlich einen Heap der Größe n auf den n Arrays. Dies würde jedoch bedeuten, dass jedes Mal, wenn ein Element platziert wird, ein Plattenlesevorgang durchgeführt wird, und jedes Mal, wenn n Elemente abgeschlossen werden, ein Plattenschreibvorgang ausgeführt wird. Irgendwelche besseren Vorschläge? Danke.So sortieren Sie n^2 Elemente in 2n RAM

Quelle

2010-11-22 user515974

Eine andere Möglichkeit, die Frage zu formulieren, ist "Wie man n Elemente in O (log (n)) RAM" sortiert. – erikkallen

Sollte das nicht O (sqrt (n)) sein? –

Knuth hat ein ganzes Kapitel über dieses Problem in * The Art of Computer Programming * Band 3. –

Es ist nicht möglich. Sie brauchen n^2 Speicher für die Elemente allein.

Wenn Sie nicht über diesen offensichtlichen Speicherverbrauch zählen, empfehle ich eine der Inplace Sortieralgorithmen, wie Heapsort. Es wird O (1) zusätzlichen Speicherplatz benötigen.

Wenn Sie nach einer externen Sortieralgorithmus, wo der externe Speicher nicht nur zählen, sondern die internen einem, empfehle ich mergesort bottom-up zu verwenden. Sie können so viel oder so wenig internen Speicher verbrauchen, wie Sie möchten; um ungefähr 2n Speicher zu verbrauchen, lese immer n/2 Elemente von jedem teilweise sortierten Satz und führe sie in ein anderes Feld von n Elementen zusammen; Schreiben Sie dann das Ergebnis zurück auf die Festplatte (vorzugsweise in eine separate Datei).

Quelle

2010-11-22 15:34:25

Es müssen nicht alle Daten zuerst geladen werden. –

Aber Sie müssen sie irgendwo speichern. Selbst auf der Festplatte benötigen sie immer noch O (n^2) Speicherbytes. –

OP, sagt er hat O (n) 'RAM', wo er sagte, er hat keinen O (n^2) Raum? Sein Vorschlag zur Problemlösung sagt genau, dass er Außenraum hat. –

Wenn Sie eine Cache-freie Prioritätswarteschlangenimplementierung haben, können Sie damit eine optimale Laufzeit für Speicherübertragungen auf jeder Ebene der Festplatten- und Speicherhierarchie erreichen (siehe http://courses.csail.mit.edu/6.897/spring05/lec/lec23.pdf).

Andernfalls, wenn Sie nur einfache Code von Grund auf neu zu schreiben, eine Disk-basierte Implementierung von Mergesort sollte gut funktionieren. Grundsätzlich können Sie einen Bereich des Arrays sortieren, indem Sie zuerst die "linken" und "rechten" Hälften rekursiv sortieren und sie anschließend mit dem 2n-Speicher zusammenführen, um die rekursiv sortierten Sub-Arrays von der Festplatte zu puffern. Für eine einfache Implementierung ist dies nicht vorhanden. Sie müssen also zwei Kopien des Arrays auf der Festplatte behalten und hin- und herpendeln.

Quelle

2010-11-22 21:06:08 jonderry

Bleib dran, wenn du n^2 Elemente hast, wie wirst du die finale Zusammenführung in 2n Speicher machen? –

Sie puffern die Nummern von der Festplatte. Sie haben zwei Listen auf der Festplatte, die Sie zusammenführen möchten, also laden Sie n von jedem in den Speicher und führen sie zusammen, indem Sie die Ergebnisse der Zusammenführung auf die Festplatte schreiben. Wenn einer der Puffer leer ist, laden Sie ihn neu. Technisch gesehen sollten Sie auch beim Schreiben auf die Festplatte puffern, so dass Sie möglicherweise auch O (n) Speicher für den Ausgabepuffer reservieren müssen. – jonderry

So sortieren Sie n^2 Elemente in 2n RAM

Antwort

Verwandte Themen