¿Algoritmo de ordenamiento para un problema de ordenamiento sin comparación?

Question

Actualmente me encuentro con un problema de clasificación difícil. Tengo una colección de eventos que deben ordenarse uno contra el otro (un comparison sort) y en contra de su posición relativa en la lista.

En los términos más simples tengo una lista de eventos que tienen una prioridad (número entero), una duración (segundos) y un tiempo de aparición más temprano que el evento puede aparecer en la lista. Necesito ordenar los eventos según la prioridad, pero ningún evento puede aparecer en la lista antes de su primera aparición. He aquí un ejemplo de (esperemos) que sea más claro:

// 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 
} 

artículo "b" tiene que ir en último lugar, ya que no se le permite comenzar hasta 6,0 segundos en la lista, por lo que se difiere y "c" recibe ir antes que "b" a pesar de que su prioridad es menor. (Espero que lo anterior explique mi problema, si no me lo diga y lo editaré.)

Mi idea actual es utilizar un insertion sort para administrar el proceso de clasificación. A diferencia de muchos de los otros algoritmos de clasificación comunes, el ordenamiento de inserción decide el orden de la lista de a uno por vez y en orden. Por lo tanto, para cada índice, debería poder encontrar el siguiente evento de prioridad más baja, cuya primera hora de ocurrencia será satisfecha.

Espero encontrar recursos sobre la clasificación de algoritmos y estructuras de datos para ayudarme a diseñar una buena solución para este "tipo" de problema. Mi problema real es en realidad más complejo que esto: clasificación jerárquica, búferes de variables entre eventos, restricciones de tiempo no constantes múltiples, de modo que cuanta más información o ideas, mejor. La velocidad y el espacio no son realmente una preocupación. La precisión en la clasificación y la mantenibilidad del código son una preocupación.

Editar: Aclaraciones (basados ​​en los comentarios)

• Eventos consumen toda su duración (es decir que no hay superposición de eventos permitidos)
• Eventos mosto ocurren en o después de su earliestTime, no pueden ocurrir antes de su hora más temprana.
• Los eventos pueden ocurrir más tarde que su earliestTime si existen eventos de menor prioridad
• Los eventos no se pueden interrumpir
• Hay una duración máxima la suma de todos los eventos que pueden caber en una lista. Esto no se muestra arriba. (En realidad, la duración de todos los eventos será mucho mayor que la duración máxima de la lista de tiempos).
• No puede haber espacios vacíos. (No hay agujeros para tratar de relleno posterior.)

Editar: respuesta

Mientras David Nehme dio la respuesta que he seleccionado, quería señalar que su respuesta es un tipo de inserción en el corazón , y varias otras personas proporcionaron inserciones tipo de respuestas de tipo. Esto confirma para mí que un tipo de inserción especializada es probablemente el camino a seguir. Gracias a todos por sus respuestas.

Answer 1

Esto es en realidad más que un problema de clasificación. Es un problema de programación de una sola máquina con fechas de lanzamiento. Dependiendo de lo que intente hacer, el problema podría ser NP-Hard. Por ejemplo, si usted está tratando de mimimize la suma ponderada de los tiempos de finalización (el peso es inversamente proporcional a la prioridad), el problema es categorized como

1|ri;pmtn|Σ wiCi 

y es NP-duro. Hay numerosos papers sobre este tema, pero podría ser más de lo que necesita.

En su caso, nunca desea una solución con huecos, por lo que lo que podría necesitar es una simple simulación de eventos discretos (O (n log (n))). Necesitas almacenar releas_jobs como una cola de prioridad.

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 
    } 
} 

Uno de los problemas es que es posible que tenga un trabajo de baja prioridad, con un tiempo de liberación justo antes de un breve trabajo, de alta prioridad, pero va a producir un horario con la propiedad de que no hay huecos (si una el horario sin lagunas es posible).

Answer 2

Creo que debería ordenar la lista dos veces: primero por prioridad y luego por primera vez, usando cualquier algoritmo de ordenamiento estable, por ejemplo, ordenar por inserción. De esta forma, el tiempo aumentará y cada vez las cosas se ordenarán por prioridad.

A menos que vea algo que yo no puedo, puede ignorar por completo la duración de cada evento para el fin del tipo.

http://en.wikipedia.org/wiki/Category:Stable_sorts

Answer 3

En otras palabras, desea optimizar el tiempo de funcionamiento global, mientras que la formulación de dos restricciones (fuertes: punto más próximo de la ejecución, débil: prioridad)? Esto se llama constraint satisfaction problem. Hay solucionadores especiales para este tipo de problema.

Por cierto, la solución de jakber no funciona. Incluso sin la duración, el siguiente ejemplo, obviamente, falla:

event a (priority = 1, start = 5) 
event b (priority = 2, start = 0) 

La secuencia ordenada sería a, b, mientras que el resultado deseado es sin duda b, a.

Answer 4

Parece que realmente quiere una clasificación basada en la comparación. Su clave de clasificación es {earliestTime, priority}, en ese orden. Debido a que su ejemplo es pseudo-C#, te voy a dar una solución # 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 */ 
    } 
} 

Ahora su lista de clasificación al igual que su esperarán afirma.

EDITAR:

Mi presunción inicial era que los eventos serían recogidos fuera de la lista y entregados fuera de un hilo separado, de modo que el gestor de colas podría disparar el próximo evento a tiempo, pero a partir de los comentarios que recibido, tuve la idea de que tal vez un enfoque que era de un solo subproceso, y todavía permitía que los eventos de prioridad más alta dispararan lo más cerca posible de su hora de inicio era más deseable. En ese caso, la función CompareTo debe cambiar de la siguiente manera:

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; 
} 

Prueba esto en contra de cualquier suposición, pero creo que es lo que estamos buscando.

Answer 5

Si tiene un conjunto limitado de niveles de prioridad, puede mantener un conjunto de listas ordenadas por tiempo, 1 para cada nivel. Siempre que necesite el próximo evento, verifique el encabezado de cada lista en orden de prioridad hasta que encuentre uno cuyo tiempo de inicio haya pasado.(Mantenga un registro de la hora mínima de inicio mientras realiza la verificación; en caso de que todavía no haya ningún evento listo, sabe cuál esperar)

Answer 6

Suena como un problema que estaba teniendo el otro día, que fue respondido here.
Suponiendo que está usando C# ...

Answer 7

creo:

1. ordenar las tareas por prioridad
2. tareas encajar en una línea de tiempo, teniendo la primera ranura disponible después de su earliestTime, que tiene un agujero lo suficientemente grande para la tarea.

Convierta la línea de tiempo en una lista de tareas, y espera (para las lagunas).

Preguntas:

1. Se permiten lagunas?
2. ¿Se pueden dividir las tareas?
3. Dadas las tareas como en la pregunta: ¿es mejor retrasar b para completar c, o hacer d para que b pueda comenzar a tiempo?

Editar:

Os las respuestas a mis preguntas son:

1. No (ish - si no hay nada para funcionar supongo que podríamos tener un hueco)
2. Sin
3. Aún no está claro, pero supongo que el ejemplo sugiere ejecutar c y demora b.

En este caso, el algoritmo podría ser:

1. Ordenar por prioridad
2. Mantener un contador para la corriente 'tiempo' a partir de t = 0
3. Buscar aunque la lista ordenada, por el elemento de mayor prioridad que se puede iniciar en t.
4. Agregue el artículo a la orden de ejecución y añada su duración a t.
5. Repite 3 & 4 hasta que se haya agotado la lista. Si no hay tareas ejecutables en t, y hay tareas pendientes, agregue una tarea de suspensión de 1 segundo en el orden de ejecución.

Este algoritmo también es O (n^2).

Answer 8

Dicho sea de paso, en el caso más general, puede que no haya solución (a menos que se permitan huecos, como señaló Douglas). Por ejemplo:

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 }; 

Answer 9

No estoy completamente seguro de que entender las complejidades de su problema, pero mi instinto me dice que es necesario definir una relación entre la prioridad y la hora de inicio.El ejemplo sería:

Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 }; 
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 }; 

Por lo tanto, podemos seguir adelante y comenzar b en el tiempo = 0, o debemos esperar a que una garrapata y luego empezamos a porque es más alta prioridad? Supongamos que hay más eventos con más prioridades y compensaciones a más largo plazo. Creo que necesita una regla del tipo "si el siguiente evento tiene una prioridad X mayor y la brecha (entre ahora y el tiempo más temprano) es inferior a Y segundos, espere y luego comience el evento de mayor prioridad. De lo contrario, comience la baja prioridad evento (por lo tanto, rechazando la prioridad alta) ".

Answer 10

Aquí hay un código de Python en la línea de la respuesta de Douglas. Primero clasificamos por prioridad, luego ajustamos una línea de tiempo en una forma de selección de tipo:

#!/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