Sortieralgorithmus für ein nicht-Vergleich auf Basis Art Problem?
https://stackoverflow.com/questions/297035
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin derzeit mit einem schwierigen Problem konfrontiert Sortieranlage. Ich habe eine Sammlung von Ereignissen, die gegeneinander sortiert werden müssen (a Vergleich sortieren ) und gegen ihre relative Position in der Liste.
In der einfachsten Form I Liste der Ereignisse, die jeweils eine Priorität (integer), eine Dauer (in Sekunden) und eine früheste Zeitpunkt des Auftretens, dass das Ereignis in der Liste angezeigt werden kann. Ich brauche die Ereignisse auf Priorität zu sortieren, aber kein Ereignis in der Liste vor der frühesten Eintrittszeit erscheinen. Hier ist ein Beispiel, um (hoffentlich) machen es klarer:
// Psuedo C# code
class Event { int priority; double duration; double earliestTime ; }
void Example()
{
Event a = new Event { priority = 1, duration = 4.0, earliestTime = 0.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 6.0 };
Event c = new Event { priority = 3, duration = 3.0, earliestTime = 0.0 };
Event d = new Event { priority = 4, duration = 2.0, earliestTime = 0.0 };
// assume list starts at 0.0 seconds
List<Event> results = Sort( new List<Event> { a, b, c, d } );
assert( results[ 0 ] == a ); // 4.0 seconds elapsed
assert( results[ 1 ] == c ); // 7.0 seconds elapsed
assert( results[ 2 ] == b ); // 12.0 seconds elapsed
assert( results[ 3 ] == d ); // 14.0 seconds elapsed
}
Item „b“ hat zuletzt zu kommen, weil es nicht erlaubt ist, bis 6,0 Sekunden in die Liste zu beginnen, so ist es abgegrenzt und „c“ wird vor „b“ zu gehen, obwohl seine Priorität niedriger ist. (Hoffentlich wird die oben erklärt mein Problem, wenn nicht lassen Sie mich wissen und ich werde es bearbeiten.)
Meine aktuelle Idee ist ein Einfügen verwenden sortieren den Sortierprozess zu verwalten. Im Gegensatz zu vielen der anderen gemeinsamen Sortieralgorithmen entscheidet Insertionsort die Reihenfolge der Liste einen nach dem anderen, und um. Also für jeden Index soll ich in der Lage sein, das nächste niedrigste Priorität Ereignis, deren früheste Eintrittszeit zufrieden sein wird zu finden.
Ich hoffe, Ressourcen zu finden über Algorithmen und Datenstrukturen Sortier mir für diese „Art“ von Problem, eine gute Lösung zu helfen, entwerfen. Mein wirkliches Problem ist eigentlich viel komplexer als diese: hierarchische Sortierung, variable Puffer zwischen den Ereignissen, mehrere nicht-ständigen Zeitdruck, so dass die mehr Informationen oder Ideen, desto besser. Geschwindigkeit und Raum ist nicht wirklich ein Problem. Genauigkeit beim Sortieren und Wartbarkeit des Codes ist ein Anliegen.
Edit: Klärungen (basierend auf Kommentare)
- Veranstaltungen verbrauchen ihre gesamte Dauer (dh es gibt keine Überschneidungen von Veranstaltungen erlaubt)
- Veranstaltungen muss treten bei oder nach ihrer EarliestTime, können sie nicht vor ihrem EarliestTime auftreten.
- Veranstaltungen können später als ihre EarliestTime auftreten, wenn eine niedrigere Priorität Ereignisse existieren
- Veranstaltungen kann nicht unterbrochen werden
- Es gibt eine maximale Dauer die Summe aller Ereignisse, die in einer Liste passen. Dies ist nicht oben gezeigt. (In Wirklichkeit ist die Dauer aller Ereignisse wird weit größer als die Zeitliste der maximale Dauer sein.)
- Es kann keine Lücken sein. (Es gibt keine Löcher, um zu versuchen und wieder zu füllen.)
Edit: Antwort
Während David Nehme die Antwort habe ich ausgewählt, wollte ich, dass seine Antwort darauf hinweisen, eine Insertion Sorten am Herzen liegt, und mehrere andere Menschen zur Verfügung gestellt Einfügungen sortieren Antworten geben. Dies bestätigt, dass für mich eine spezielle Insertionsort ist wahrscheinlich der Weg zu gehen. Dank Ihnen allen für Ihre Antworten.
Lösung
Dies ist eigentlich mehr als ein Sortierproblem. Es ist ein Single-Maschine Scheduling Problem mit Freigabedaten. Je nachdem, was Sie versuchen, NP-schwer zu tun, könnte das Problem sein. Zum Beispiel, wenn Sie (das Gewicht der Priorität umgekehrt proportional) versuchen, die gewichtete Summe der Fertigstellungszeiten mimimize, ist das das Problem Papiere zu diesem Thema , aber es könnte sein, mehr als das, was Sie brauchen.
In Ihrem Fall sollten Sie nie eine Lösung mit Lücken, so was Sie können nur tun müssen, ist eine einfache diskrete Ereignissimulation (O (n log (n))) Zeit. Sie müssen als Prioritätswarteschlange speichern released_jobs.
unreleased_jobs = jobs // sorted list of jobs, by release date
released_jobs = {} // priority queue of jobs, by priority
scheduled_jobs = {} // simple list
while (!unreleased_jobs.empty() || !released_jobs.empty()) {
while (unreleased_jobs.top().earliestTime <= t) {
released_jobs.push(unreleased_jobs.pop())
}
if (!released_jobs.empty()) {
next_job = released_jobs.pop();
scheduled_jobs.push_back(next_job)
t = t + next_job.duration
} else {
// we have a gap
t = unreleased_jobs.top().earliestTime
}
}
Ein Problem ist, dass Sie einen niedrige Priorität Job mit einer Release-Zeit vor kurzem, nur haben könnten, mit hohen Priorität Job, aber es wird einen Zeitplan mit der Eigenschaft erzeugt, dass es keine Lücken (wenn ein Zeitplan ohne Lücken sind ist möglich).
Andere Tipps
Mit anderen Worten, mögen Sie die Gesamtlaufzeit optimieren, während zwei Einschränkungen zu formulieren (stark: frühesten Zeitpunkt der Ausführung, schwach: Priorität)? Dies ist ein Constraint Satisfaction Problem genannt. Es gibt spezielle Solver für diese Art von Problem.
Im Übrigen jakber-Lösung funktioniert nicht. Auch ohne die Dauer, scheitert das folgende Beispiel offensichtlich:
event a (priority = 1, start = 5)
event b (priority = 2, start = 0)
Die sortierten Folge a würde, b während das gewünschte Ergebnis sicherlich b ist, a.
Ich denke:
- Sortieren Aufgaben nach Priorität
- Fit Aufgaben in eine Zeitlinie, die erste verfügbare Slot nach ihrer EarliestTime nehmen, die ein Loch groß genug für die Aufgabe hat.
Konvertieren Sie die Zeitlinie in eine Liste ein Aufgaben und wartet (für die Spalte).
Fragen:
- Sind Lücken erlaubt?
- Kann Aufgaben aufgeteilt werden?
- die Aufgaben wie in der Frage gegeben: ist es besser, b zu verzögern c zu vervollständigen, oder tun d, so dass b pünktlich beginnen kann?
Edit:
Os die Antworten auf meine Fragen sind:
- Nein (ish - wenn es nichts zu laufen Ich denke, wir eine Lücke haben könnte)
- Nein
- Immer noch nicht klar, aber ich denke, das Beispiel c und Verzögerung b laufen schlägt.
In diesem Fall wird der Algorithmus könnte sein:
- Sortieren nach Priorität
- einen Zähler für die aktuelle 'Zeit' Halten Sie mit t = 0
- Suchen obwohl der sortierten Liste, für die höchste Priorität Element, das bei t gestartet werden.
- Fügen Sie den Artikel der fahrbereitem Zustand und fügen Sie seine Dauer t.
- Wiederholen 3 und 4, bis die Liste erschöpft ist. Wenn es keine Aufgaben runnable bei t sind, und es gibt Aufgaben noch anstehen, hält eine 1-Sekunden-Schlaf Aufgabe in dem laufenden Auftrag.
Dieser Algorithmus ist auch O (n ^ 2).
Ich glaube, Sie die Liste zweimal sortieren soll: zuerst nach Priorität und dann durch frühestmöglichen Zeitpunkt, unter Verwendung eines beliebigen stabil Sortieralgorithmus, zum Beispiel Insertionsort. Auf diese Weise wird die Zeit und für jede Zeit, die Dinge zu erhöhen wird nach Priorität sortiert werden.
Wenn Sie etwas sehe ich Sie nicht über die Dauer der jeweiligen Veranstaltung zum Zwecke der Art völlig ignorieren können.
Wenn Sie eine begrenzte Anzahl von Prioritätsstufen haben, könnten Sie eine Reihe von zeit sortierte Listen halten, 1 für jede Ebene. Jedes Mal, wenn Sie das nächste Ereignis benötigen, überprüfen Sie den Kopf jeder Liste in Prioritätsreihenfolge, bis Sie ein, deren Startzeit verstrichen finden. (Verfolgen Sie die Mindeststartzeit, während Sie prüfen - falls kein Ereignis wartet noch, Sie wissen, was man warten)
Klingt wie ein Problem, das ich war neulich mit, die hier beantwortet wurde .
Angenommen, Sie sind mit C # ...
Im übrigen im allgemeinsten Fall kann es keine Lösung sein (es sei denn Lücken erlaubt sind, wie Douglas darauf hingewiesen). Zum Beispiel:
Event a = new Event { priority = 1, duration = 1.0, earliestTime = 4.0 };
Event b = new Event { priority = 2, duration = 1.0, earliestTime = 4.0 };
Event c = new Event { priority = 3, duration = 1.0, earliestTime = 4.0 };
Event d = new Event { priority = 4, duration = 1.0, earliestTime = 4.0 };
Ich bin nicht ganz sicher, ob ich die Feinheiten des Problems zu verstehen, aber mein Instinkt sagt mir, Sie brauchen eine Beziehung zwischen Priorität zu definieren und Zeit beginnen. Das Beispiel wäre:
Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 };
, tun wir voran gehen und b zum Zeitpunkt start = 0, oder müssen wir für eine Zecke warten und dann a gestartet werden, da es eine höhere Priorität ist? Angenommen, es gab mehr Veranstaltungen mit mehr Prioritäten und längerer Zeit Kompromissen. Ich glaube, Sie brauchen eine Regel entlang der Linien von „, wenn das nächste Ereignis X höhere Priorität und der Spalt (zwischen jetzt und dem frühestmöglichen Zeitpunkt) ist kleiner als Y Sekunden warten und dann die höhere Priorität Ereignis beginnen. Andernfalls die niedrige Priorität starten Ereignis (also drückt die hohe Priorität ein wieder)“.
Hier finden Sie einige Python-Code entlang der Linien von Douglas Antwort. Zuerst haben wir sortieren nach Priorität, dann passen wir eine Zeitleiste in einer Auswahl-Art Mode:
#!/usr/bin/env python
MIN_PRIORITY = 100
class Event(object):
def __init__(self, name, priority, duration, earliestTime):
self.name = name
self.priority = priority
self.duration = duration
self.earliestTime = earliestTime
def __str__(self):
return "%-10s: P %3d D %3.1f T %3.1f" % (self.name, self.priority, self.duration, self.earliestTime)
def sortEvents(_events):
def comparePriority(event1, event2):
if event1.priority < event2.priority: return -1
if event1.priority > event2.priority: return 1
return 0
# Get a copy of the events and sort by priority
events = [e for e in _events]
events.sort(cmp=comparePriority)
# Select one event at a time, checking for compatibility with elapsed time
elapsedTime = 0.0
sortedEvents = []
while events:
minGap = events[0].earliestTime - elapsedTime
for e in events:
currentGap = e.earliestTime - elapsedTime
if currentGap < minGap:
minGap = currentGap
if currentGap <= 0.0:
sortedEvents.append(e)
elapsedTime += e.duration
events.remove(e)
break
# If none of the events fits, add a suitable gap
if minGap > 0:
sortedEvents.append( Event("gap", MIN_PRIORITY, minGap, elapsedTime) )
elapsedTime += minGap
return sortedEvents
if __name__ == "__main__":
#e1 = Event("event1", 1, 1.0, 4.0)
#e2 = Event("event2", 2, 1.0, 6.0)
#e3 = Event("event3", 3, 1.0, 8.0)
#e4 = Event("event4", 4, 1.0, 10.0)
e1 = Event("event1", 1, 4.0, 0.0)
e2 = Event("event2", 2, 5.0, 6.0)
e3 = Event("event3", 3, 3.0, 0.0)
e4 = Event("event4", 4, 2.0, 0.0)
events = [e1, e2, e3, e4]
print "Before:"
for event in events: print event
sortedEvents = sortEvents(events)
print "\nAfter:"
for event in sortedEvents: print event
Es klingt wie Sie eigentlich gar einen vergleichsbasierten Sortier wollen. Ihre Sortierschlüssel {EarliestTime, Priorität}, in dieser Reihenfolge. Da Ihr Beispiel pseudo-C # ist, werde ich Ihnen eine pseudo-C # Lösung:
class Event : IComparable<Event>, IComparable{
int priority;
double duration;
double earliestTime;
public int CompareTo(Event other){
if(other == null)
return 1; /* define: non-null > null */
int cmp = earliestTime.CompareTo(other.earliestTime);
if(cmp != 0)
return cmp;
/* earliestTimes were equal, so move on to next comparison */
return priority.CompareTo(other.priority);
}
int IComparable.CompareTo(object other){ /* for compatibility with non-generic collections */
if(other == null)
return 1; /* define: non-null > null */
Event e_other = other as Event;
if(e_other == null) /* must have been some other type */
throw new ArgumentException("Must be an Event", "other");
return CompareTo(e_other); /* forward to strongly-typed implementation */
}
}
Jetzt ist Ihre Liste sortieren wie Ihr behauptet erwartet.
Bearbeiten :
Meine erste Vermutung war, dass die Ereignisse um die Liste abgreifbar und an einem separaten Thread übergeben werden würde, so dass der WS-Manager das nächste Ereignis rechtzeitig abfeuern konnte, aber von den Kommentaren Ich erhielt, hatte ich die Idee, dass vielleicht ein Ansatz, der zu ihrer Startzeit Single-Thread, aber immer noch mit höherer Priorität Ereignissen erlaubt abzufeuern so nah wie möglich war, mehr wünschenswert. In diesem Fall sollte die CompareTo Funktion wie folgt ändern:
public int CompareTo(Event other){
if(other == null)
return 1; /* define: non-null > null */
int cmp = priority.CompareTo(other.priority);
if(cmp == 0)
/*
* calculate and compare the time each event will be late
* if the other one were to start first. This time may be
* negative if starting one will not make the other one late
*/
return (earliestTime + duration - other.earliestTime).CompareTo(
other.earliestTime + other.duration - earliestTime);
/*
* they're different priorities. if the lower-priority event
* (presume that greater priority index means lower priority,
* e.g. priority 4 is "lower" priority than priority 1), would
* would make the higher-priority event late, then order the
* higher-priority one first. Otherwise, just order them by
* earliestTime.
*/
if(cmp < 0){/* this one is higher priority */
if(earliestTime <= other.earliestTime)
/* this one must start first */
return -1;
if(other.earliestTime + other.duration <= earliestTime)
/* the lower-priority event would not make this one late */
return 1;
return -1;
}
/* this one is lower priority */
if(other.earliestTime <= earliestTime)
/* the other one must start first */
return 1;
if(earliestTime + duration <= other.earliestTime)
/* this event will not make the higher-priority one late */
return -1;
return 1;
}
Test dies gegen alle Annahmen, aber ich denke, es ist das, was wir suchen.
