Gibt es Algorithmen zum Sortieren von Daten von der seriellen Eingabe mit Puffer, der kleiner ist als die Datenlänge?Serielle Daten mit Puffer sortieren
Zum Beispiel habe ich 100 Bytes serielle Daten, die nur einmal gelesen werden können, und 40 Bytes Puffer. Und ich muss sortierte Bytes ausdrucken.
Ich brauche es in Javascript, aber alle allgemeinen Ideen sind willkommen.
Diese Art der Sortierung ist nicht in einem Durchgang möglich.
Verwenden Sie Ihr Beispiel: Angenommen, Sie haben Ihren 40-Byte-Puffer gefüllt, so müssen Sie beginnen, Bytes auszudrucken, um Platz für den nächsten zu schaffen. Um sortierte Daten auszudrucken, müssen Sie zuerst das kleinste Byte drucken. Wenn jedoch das kleinste Byte nicht gelesen wurde, können Sie es möglicherweise noch nicht ausdrucken!
Die am ehesten zutreffende Antwort auf Ihre Frage sind external sorting Algorithmen, die mehrere Durchgänge erfordern, um Daten zu sortieren, die nicht in den Speicher passen. Das heißt, wenn Sie Peripheriegeräte haben, die die Ausgabe eines Verarbeitungspasses speichern können, können Sie Daten, die größer sind als Ihr Speicher, in O (log (N/M)) - Pässe sortieren, wobei N die Größe des Problems und M die Größe Ihres Gedächtnisses.
Das klassische Speicherperipheriegerät für die externe Sortierung ist das Bandlaufwerk; Die gleichen Algorithmen funktionieren jedoch auch für Festplattenlaufwerke (egal welcher Art). Da Cache-Hierarchien in der Tiefe wachsen, werden die Prinzipien der externen Sortierung auch für In-Memory-Sortierungen relevanter - werfen Sie einen Blick auf Algorithmen.
Ich bin ziemlich sicher, dass es nicht möglich ist, es sei denn, die Daten sind zu einem gewissen Grad vorbestellt. Wenn das letzte Byte, das Sie erhalten, in der Ausgabe an erster Stelle stehen soll, können Sie keine Bytes vorher ausgeben und es immer noch zuerst herauskommen lassen, aber Sie können nicht alle dazwischenliegenden Daten in einem Puffer speichern, der kleiner ist Daten belegen. Sie könnten etwas wie das Komprimieren der Daten versuchen, aber das kann fehlschlagen und es größer machen. –