Effizient Ergebnisse anzeigen

Question

Ich habe eine Reihe von Objekten herumschweben, nennen wir sie Bestellungen. Verarbeitet werden. Die Regel meines (Test-) Systems ist jedoch, dass ich zur Ausgabe der Ergebnisse die Ausgabe in sequentieller Reihenfolge (nach Auftrags-ID) benötige.

Dies bedeutet, dass ein Auftrag, der markiert wurde, dass er fertig ist (abgeschlossene Bearbeitung), nicht als abgeschlossen markiert werden kann, es sei denn, alle Aufträge mit Auftrags-IDs < sind bereits ausgefüllt.

• Aufträge können fertige Verarbeitung in jeder beliebigen Reihenfolge

• Reihenfolge ids einzigartig und zugeordnet sind in der Reihenfolge der anfänglichen Auftragserstellung

  Klasse Ordnung { int id gekennzeichnet werden; Boolean finishedProcessing = false; Boolescher Abschluss = false; }

Kann jemand eine effiziente Lösung für dieses Problem vorschlagen? Ich kann nur daran denken, eine HashMap (Bestell-ID, abgeschlossen) zu erstellen und eine Bestellung in der Karte zu kennzeichnen, sobald die Bestellung abgeschlossen ist, und festzustellen, ob eine Bestellung abgeschlossen werden kann. Anschließend wird die gesamte Karte durchlaufen, um zu sehen, ob alle vorhergehenden Bestellungen markiert wurden abgeschlossen.

Es ist der letzte Teil, der Bugs bedeutet, scheint sehr ineffizient. Gibt es einen besseren Weg?

Answer 1

Wenn IDs in der Reihenfolge der Erstellung zugewiesen werden, fügen Sie die Bestellungen bei der Erstellung zu einem Deque hinzu. Die Deque wird dann implizit nach ID geordnet.

Wenn eine Bestellung als abgeschlossen markiert ist, überprüfen Sie den ersten Eintrag in der Deque. Wenn es abgeschlossen ist, entfernen Sie es aus dem Deque (oder verschieben Sie es zu einem anderen). Überprüfen Sie dann den nächsten (jetzt ersten) Eintrag in der Deque erneut, falls mehrere Aufträge bereit sind, und wiederholen Sie diese bei Bedarf.

Das Deque der unvollständigen Aufträge wird unabhängig von Map gepflegt, die Sie möglicherweise zum Nachschlagen der Bestellung von ID benötigen.