Algorithme de tri pour un problème de tri sans comparaison?
https://stackoverflow.com/questions/297035
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis actuellement confronté à un problème de tri difficile. J'ai une collection d'événements qui doivent être triés les uns par rapport aux autres (une sorte de comparaison ) et contre leur position relative dans la liste.
En termes simples, j'ai une liste d'événements qui ont chacun une priorité (entier), une durée (secondes) et une heure d'occurrence la plus ancienne à laquelle l'événement peut apparaître dans la liste. Je dois trier les événements en fonction de la priorité, mais aucun événement ne peut apparaître dans la liste avant son heure d'apparition la plus ancienne. Voici un exemple pour clarifier (espérons-le):
// 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
}
Article " b " doit venir en dernier parce qu’il n’est pas permis de démarrer avant 6,0 secondes dans la liste, il est donc différé et "c". doit aller avant " b " même si sa priorité est moindre. (J'espère que ce qui précède explique mon problème, si ce n'est pas le cas, laissez-moi savoir et je le modifierai.)
Mon idée actuelle est d'utiliser un tri par insertion pour gérer le processus de tri. Contrairement à la plupart des autres algorithmes de tri courants, le tri par insertion détermine l’ordre de la liste, un à la fois et dans l’ordre. Donc, pour chaque index, je devrais être capable de trouver le prochain événement de priorité la plus basse dont l’heure la plus ancienne sera satisfaite.
J'espère trouver des ressources sur les algorithmes de tri et les structures de données pour m'aider à concevoir une bonne solution pour ce "tri". de problème. Mon vrai problème est en réalité plus complexe que cela: tri hiérarchique, tampons variables entre les événements, contraintes temporelles multiples et non constantes, de sorte que plus il y a d'informations ou d'idées, mieux c'est. La vitesse et l'espace ne sont pas vraiment une préoccupation. La précision du tri et la maintenabilité du code sont une préoccupation.
Modifier: Clarifications (en fonction des commentaires)
- Les événements consomment toute leur durée (c'est-à-dire qu'il n'y a pas de chevauchement autorisé des événements)
- Les événements doivent se produire à ou après leur heure la plus tôt, ils ne peuvent pas se produire avant leur heure au plus tôt.
- Les événements peuvent se produire après leur date de début si des événements de priorité inférieure existent
- Les événements ne peuvent pas être interrompus
- Il existe une durée maximale correspondant à la somme de tous les événements pouvant figurer dans une liste. Ceci n'est pas montré ci-dessus. (En réalité, la durée de tous les événements sera bien supérieure à la durée maximale de la liste de temps.)
- Il ne peut y avoir de lacunes. (Il n'y a pas de trous à essayer et à remplir en arrière.)
Modifier: Répondre
Alors que David Nehme a donné la réponse que j'ai sélectionnée, je voulais souligner que sa réponse est une insertion par cœur, et plusieurs autres personnes ont fourni des réponses de type insertions. Cela confirme pour moi qu'une sorte d'insertion spécialisée est probablement la voie à suivre. Merci à tous pour vos réponses.
La solution
C’est en réalité plus qu’un problème de tri. C'est un problème de planification mono-machine avec les dates de sortie. Selon ce que vous essayez de faire, le problème peut être NP-Hard. Par exemple, si vous essayez de simuler la somme pondérée des temps d’achèvement (le poids étant inversement proportionnel à la priorité), le problème est classé comme
1|ri;pmtn|Σ wiCi
et est NP-difficile. Il existe de nombreux articles sur ce sujet, mais il se peut que ce soit le cas. plus que ce dont vous avez besoin.
Dans votre cas, vous ne souhaiterez jamais une solution avec des lacunes, il vous suffira donc simplement de simuler un événement à événements discrets (O (n log (n))). Vous devez stocker les variables release_jobs en tant que file d'attente prioritaire.
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
}
}
Un problème est que vous pouvez avoir un travail peu prioritaire avec un temps de relâchement juste avant un travail court et hautement prioritaire, mais il produira un calendrier indiquant qu'il n'y a pas de lacunes (si un calendrier ne est possible).
Autres conseils
En d’autres termes, vous souhaitez optimiser le temps d’exécution global tout en formulant deux contraintes (forte: premier point d’exécution, faible: priorité)? Il s’agit d’un problème de satisfaction de contrainte . Il existe des solutions spéciales pour ce type de problème.
Incidemment, la solution de jakber ne fonctionne pas. Même sans la durée, l'exemple suivant échoue évidemment:
event a (priority = 1, start = 5)
event b (priority = 2, start = 0)
La séquence triée serait a , b alors que le résultat souhaité est sûrement b , a .
Je pense:
- Trier les tâches par priorité
- Ajustez les tâches dans une chronologie, en prenant le premier emplacement disponible après leur heure initiale, qui a un trou suffisamment grand pour la tâche.
Convertissez la chronologie en liste de tâches et attendez (les lacunes).
Questions:
- Les lacunes sont-elles autorisées?
- Les tâches peuvent-elles être fractionnées?
- Étant donné les tâches décrites dans la question: vaut-il mieux retarder b pour terminer c ou faire d pour que b puisse commencer à l’heure?
Modifier:
Les réponses à mes questions sont les suivantes:
- Non (ish - s'il n'y a rien à courir, je suppose que nous pourrions avoir un écart)
- Non
- Toujours pas clair, mais je suppose que l'exemple suggère de lancer c et de retarder b.
Dans ce cas, l'algorithme peut être:
- Trier par priorité
- Conservez un compteur pour le "temps" actuel commençant par t = 0
- Recherchez, dans la liste triée, l'élément de priorité la plus élevée pouvant être démarré à l'instant.
- Ajoutez l'élément à l'ordre en cours et sa durée à t.
- Répétez les étapes 3 et 4 jusqu'à ce que la liste soit épuisée. Si aucune tâche ne peut être exécutée en t et qu'il reste des tâches en attente, collez une tâche de veille d'une seconde dans l'ordre d'exécution.
Cet algorithme est également O (n ^ 2).
Je pense que vous devriez trier la liste deux fois: d'abord par priorité, puis le plus tôt possible, en utilisant n'importe quel algorithme de tri stable , par exemple le tri par insertion. De cette façon, le temps augmentera et chaque fois, les choses seront triées par priorité.
Si vous ne voyez pas quelque chose que je ne vois pas, vous pouvez complètement ignorer la durée de chaque événement aux fins du tri.
Si vous avez un ensemble limité de niveaux de priorité, vous pouvez conserver un ensemble de listes triées dans le temps, 1 pour chaque niveau. Chaque fois que vous avez besoin du prochain événement, vérifiez l’en-tête de chaque liste par ordre de priorité jusqu’à ce que vous en trouviez un dont l’heure de début est passée. (Gardez une trace de l'heure de début minimum pendant votre vérification - si aucun événement n'est encore prêt, vous savez lequel attendre.)
Cela ressemble à un problème que je rencontrais l’autre jour et auquel on a répondu ici .
En supposant que vous utilisiez C # ...
Incidemment, dans le cas le plus général, il peut ne pas y avoir de solution (à moins que des écarts ne soient autorisés, comme l'a souligné Douglas). Par exemple:
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 };
Je ne suis pas tout à fait sûr de comprendre les subtilités de votre problème, mais mon instinct me dit que vous devez définir une relation entre la priorité et l'heure de début. L'exemple serait:
Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 };
Alors, continuons-nous et commençons b à heure = 0, ou attendons-nous une coche, puis commençons a parce que c'est une priorité plus élevée? Supposons qu'il y ait plus d'événements avec plus de priorités et des compromis plus longs. Je pense que vous avez besoin d’une règle du type "si l’événement suivant a une priorité X supérieure et que l’écart (entre maintenant et au plus tôt) est inférieur à Y secondes, attendez puis démarrez l’événement de priorité supérieure. sinon, démarrez l’événement de faible priorité (repoussez ainsi l’événement de priorité élevée) ".
Voici un code Python inspiré de la réponse de Douglas. Nous commençons par trier par priorité, puis nous ajustons une chronologie de manière à sélectionner-trier:
#!/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
Il semble que vous souhaitiez réellement un tri basé sur la comparaison. Votre clé de tri est {earliestTime, priority}, dans cet ordre. Puisque votre exemple est pseudo-C #, je vais vous donner une solution pseudo-C #:
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 */
}
}
Votre liste sera triée comme vos assertions l’attendent.
MODIFIER :
Ma présomption initiale était que les événements seraient retirés de la liste et transférés vers un fil de discussion séparé, de sorte que le gestionnaire de files d'attente puisse déclencher le prochain événement à temps, mais les commentaires que j'ai reçus me donnaient l'idée Une approche mono-thread, tout en permettant aux événements de priorité supérieure de se déclencher aussi près que possible de leur heure de début était plus souhaitable. Dans ce cas, la fonction CompareTo devrait changer comme suit:
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;
}
Testez ceci contre toute hypothèse, mais je pense que c'est ce que nous recherchons.
