Wie würden Sie eine Million 32-Bit-Integer in 2 MB RAM sortieren?

StackOverflow https://stackoverflow.com/questions/134158

Frage

Bitte, Code-Beispiele in der Sprache Ihrer Wahl zur Verfügung stellen.

Aktualisieren : Keine Einschränkungen setzen auf externe Speicher.

Beispiel: Ganze Zahlen werden empfangen / über das Netzwerk gesendet. Es gibt einen ausreichenden Platz auf dem lokale Festplatte für Zwischenergebnisse.

Andere Tipps

Split das Problem in Stücke klein genug, um in den verfügbaren Speicher passen, dann verwenden Sie Mergesort kombinieren sie.

1 Million 32-Bit-Integer = 4 MB Speicher.

Sie sollten sie sortieren einige Algorithmus, externe Speicher verwendet. Mergesort, zum Beispiel.

Sie benötigen mehr Informationen zu liefern. Was zusätzlicher Speicherplatz zur Verfügung steht? Wo soll man das Ergebnis speichern?

Ansonsten ist die allgemeinste Antwort: 1. Laden der ersten Hälfte der Daten in den Speicher (2 MB), sortiert sie nach irgendeinem Verfahren der Ausgang es Datei. 2. Laden die zweite Hälfte der Daten in den Speicher (2 MB), sortieren sie durch jedes Verfahren, halten sie im Speicher. 3. Verwendung Merge-Algorithmus die beiden sortierten Hälften und geben die vollständige sortierten Daten in eine Datei gesetzt fusionieren.

Das Wikipedia-Artikel über externe Sortierung einige nützliche Informationen.

Dual-Turnier Art mit mehrphasigen merge 

#!/usr/bin/env python
import random
from sort import Pickle, Polyphase


nrecords = 1000000
available_memory = 2000000 # number of bytes
    #NOTE: it doesn't count memory required by Python interpreter 

record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size 
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
              file_maker=Pickle, 
              verbose=True,
              heap_size=heap_size,
              max_files=4 * (nrecords / heap_size + 1))

# put records
maxel = 1000000000
for _ in xrange(nrecords):
    p.put(random.randrange(maxel))

# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
    if el > last: # elements must be in descending order
        print "not sorted %d: %d %d" % (n, el ,last)
        break
    last = el

assert nrecords == (n + 1) # check all records read
  • Um, speichern sie alle in einer Datei.
  • Speicher die Datei Karte (Sie sagte, dass es nur 2 M RAM, lassen Sie sich den Adressraum groß genug ist, Speicherzuordnung eine Datei übernehmen).
  • sortieren sie die Datei Sicherungsspeicher verwenden, als ob es jetzt Realspeicher waren!

Hier ist eine gültige und Spaß Lösung.

Last der Hälfte der Zahlen in dem Speicher. Heap sie an ihrem Platz sortieren und die Ausgabe in eine Datei schreiben. Wiederholen Sie dies für die andere Hälfte. Verwenden Sie externe Art (im Grunde eine Mergesort das braucht Datei i / o berücksichtigt) die beiden Dateien zusammenführen.

Neben:   Machen Sie die Stapelsortier schneller angesichts der langsamen externen Speicher:

  • Starten Sie den Heap-Konstruktion vor allem die ganzen Zahlen im Speicher befinden.

  • Starten Sie die ganzen Zahlen zurück in die Ausgabedatei setzen, während die Stapelsortier noch Elemente extrahieren

Da die Menschen über Erwähnungsart int von 32bit 4 MB.

so viel „Nummer“ wie möglich zu passen in so wenig Raum wie möglich unter Verwendung der Typen int, kurz und char in C ++. Man könnte glatt sein (aber haben ungerade schmutzigen Code) von überall verschiedene Arten von Casting zu stopfen, Dinge zu tun.

Hier ist es über den Rand meines Sitzes.

alles, was weniger als 2 ^ 8 (0 - 255) als char (1 Byte-Daten) gespeichert wird

alles, was weniger ist als 2 ^ 16 (256 bis 65.535) und> 2 ^ 8 als Kurz gespeichert wird (2 Byte-Datentyp)

Der Rest der Werte setzen würde in int werden. (4 Byte-Datentyp)

Sie würden wollen, angeben, wo die char Abschnitt beginnt und endet, wo die kurzen Abschnitt beginnt und endet und wo die int Abschnitt beginnt und endet.

Kein Beispiel, aber Bucketsort hat eine relativ geringe Komplexität und ist leicht genug, um zu implementieren

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top