Algoritmo di ordinamento per un problema di ordinamento non basato sul confronto?

Question

Attualmente sto affrontando un problema di ordinamento difficile. Ho una raccolta di eventi che devono essere ordinati l'uno contro l'altro (un ordinamento comparativo ) e contro la loro posizione relativa nell'elenco.

In parole povere ho un elenco di eventi che hanno ciascuno una priorità (numero intero), una durata (secondi) e un tempo di occorrenza prima che l'evento possa apparire nell'elenco. Devo ordinare gli eventi in base alla priorità, ma nessun evento può apparire nell'elenco prima del suo primo evento. Ecco un esempio per (si spera) di renderlo più chiaro:

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

Articolo " b " deve arrivare per ultimo perché non è consentito avviare fino a 6,0 secondi nell'elenco, quindi è differito e "quotato" arriva prima di " b " anche se la sua priorità è inferiore. (Spero che quanto sopra spieghi il mio problema, se non fammi sapere e lo modificherò.)

La mia idea attuale è quella di utilizzare un ordinamento per inserzione per gestire il processo di ordinamento. A differenza di molti altri algoritmi di ordinamento comuni, l'ordinamento per inserzione decide l'ordine dell'elenco uno alla volta e in ordine. Quindi per ogni indice dovrei essere in grado di trovare il prossimo evento con priorità più bassa il cui tempo di occorrenza più breve sarà soddisfatto.

Spero di trovare risorse sugli algoritmi di ordinamento e sulle strutture di dati per aiutarmi a progettare una buona soluzione per questo "ordinamento" di problema. Il mio vero problema è in realtà più complesso di questo: ordinamento gerarchico, buffer variabili tra eventi, più vincoli temporali non costanti, quindi più informazioni o idee sono, meglio è. La velocità e lo spazio non sono davvero una preoccupazione. La precisione nell'ordinamento e nella manutenibilità del codice sono una preoccupazione.

Modifica: chiarimenti (in base ai commenti)

• Gli eventi consumano l'intera durata (ovvero non è consentita la sovrapposizione di eventi)
• Gli eventi devono accadere al più presto o dopo il loro primo, non possono verificarsi prima del loro primo tempo.
• Gli eventi possono verificarsi più tardi del loro primo tempo se esistono eventi con priorità inferiore
• Gli eventi non possono essere interrotti
• Esiste una durata massima della somma di tutti gli eventi che possono rientrare in un elenco. Questo non è mostrato sopra. (In realtà la durata di tutti gli eventi sarà di gran lunga maggiore della durata massima dell'elenco temporale.)
• Non possono esserci spazi vuoti. (Non ci sono buchi da provare e riempire indietro.)

Modifica: Rispondi

Mentre David Nehme ha dato la risposta che ho selezionato, volevo sottolineare che la sua risposta è una sorta di inserimento nel cuore, e molte altre persone hanno fornito risposte di tipo di inserzione. Ciò conferma per me che un ordinamento di inserzione specializzato è probabilmente la strada da percorrere. Grazie a tutti voi per le vostre risposte.

Answer 1

Questo è in realtà più di un problema di ordinamento. È un problema di pianificazione a macchina singola con date di rilascio. A seconda di ciò che si sta tentando di fare, il problema potrebbe essere NP-Hard. Ad esempio, se si sta tentando di imitare la somma ponderata dei tempi di completamento (il peso è inversamente proporzionale alla priorità), il problema è classificato come

1|ri;pmtn|Σ wiCi 

ed è NP-difficile. Ci sono numerosi articoli su questo argomento, ma potrebbe essere più di quello che ti serve.

Nel tuo caso, non vorrai mai una soluzione con lacune, quindi quello che potresti dover fare è una semplice simulazione di eventi discreti (O (n log (n))). Devi archiviare release_jobs come una coda prioritaria.

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 problema è che potresti avere un lavoro a bassa priorità con un tempo di rilascio appena prima di un lavoro breve e ad alta priorità, ma produrrà una pianificazione con la proprietà che non ci sono lacune (se una pianificazione senza lacune è possibile).

Answer 2

In altre parole, si desidera ottimizzare il tempo di esecuzione complessivo mentre si formulano due vincoli (forte: primo punto di esecuzione, debole: priorità)? Questo si chiama problema di soddisfazione dei vincoli . Esistono risolutori speciali per questo tipo di problema.

Per inciso, la soluzione di jakber non funziona. Anche senza la durata, il seguente esempio ovviamente fallisce:

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

La sequenza ordinata sarebbe a , b mentre il risultato desiderato è sicuramente b , a .

Answer 3

Penso:

1. Ordina le attività per priorità
2. Adatta le attività a una linea temporale, prendendo il primo slot disponibile dopo il loro primo tempo, che ha un buco abbastanza grande per l'attività.

Converti la linea temporale in un elenco di attività e attende (per le lacune).

Domande:

1. Sono ammessi spazi vuoti?
2. Le attività possono essere suddivise?
3. Considerati i compiti come nella domanda: è meglio ritardare b per completare c, oppure fare in modo che b possa iniziare in tempo?

Modifica:

Le risposte alle mie domande sono:

1. No (ish - se non c'è nulla da eseguire immagino che potremmo avere un vuoto)
2. No
3. Ancora non chiaro, ma immagino che l'esempio suggerisca di eseguire ce ritardare b.

In questo caso l'algoritmo potrebbe essere:

1. Ordina per priorità
2. Mantieni un contatore per il 'tempo' corrente a partire da t = 0
3. Cerca nell'elenco ordinato, per l'elemento con la priorità più alta che può essere avviato da t.
4. Aggiungi l'articolo all'ordine di esecuzione e aggiungi la sua durata a t.
5. Ripeti 3 & 4 fino a quando l'elenco è esaurito. Se non ci sono attività eseguibili at e ci sono attività in sospeso, attacca un'attività di sospensione di 1 secondo nell'ordine di esecuzione.

Questo algoritmo è anche O (n ^ 2).

Answer 4

Penso che dovresti ordinare l'elenco due volte: prima per priorità e poi prima, usando qualsiasi algoritmo di ordinamento stabile , per esempio l'ordinamento per inserzione. In questo modo il tempo aumenterà e per ogni volta le cose saranno ordinate per priorità.

A meno che tu non veda qualcosa che io non posso, puoi ignorare completamente la durata di ciascun evento ai fini del genere.

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

Answer 5

Se si dispone di un set limitato di livelli di priorità, è possibile mantenere un set di elenchi ordinati per tempo, 1 per ciascun livello. Ogni volta che hai bisogno del prossimo evento, controlla la testa di ciascun elenco in ordine di priorità fino a quando non ne trovi uno il cui orario di inizio è trascorso. (Tieni traccia dell'orario minimo di inizio mentre controlli - nel caso in cui nessun evento sia ancora pronto, sai quale aspettare)

Answer 6

Sembra un problema che stavo avendo l'altro giorno, a cui è stata data una risposta qui .
Supponendo che tu stia utilizzando C # ...

Answer 7

Per inciso, nel caso più generale potrebbe non esserci soluzione (a meno che non siano consentite lacune, come ha sottolineato Douglas). Ad esempio:

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 8

Non sono del tutto sicuro di comprendere la complessità del tuo problema, ma il mio istinto mi dice che devi definire una relazione tra priorità e ora di inizio. L'esempio sarebbe:

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

Quindi, andiamo avanti e avviamo b alle ore = 0, oppure aspettiamo un segno di spunta e quindi avviamo a perché ha la priorità più alta? Supponiamo che ci siano stati più eventi con più priorità e compromessi più lunghi. Penso che tu abbia bisogno di una regola in linea con "se il prossimo evento ha una priorità X maggiore e il divario (tra ora e il primo tempo) è inferiore a Y secondi, attendi e quindi avvia l'evento a priorità più elevata. altrimenti avvia l'evento a bassa priorità (respingendo così quello ad alta priorità) " ;.

Answer 9

Ecco un po 'di codice Python sulla falsariga della risposta di Douglas. Prima ordiniamo per priorità, quindi inseriamo una sequenza temporale in un modo di selezione-selezione:

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

Answer 10

Sembra che tu voglia davvero un ordinamento basato sul confronto. La chiave di ordinamento è {prima, priorità}, in questo ordine. Poiché il tuo esempio è pseudo-C #, ti darò una soluzione 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 */
   }
}

Ora il tuo elenco verrà ordinato esattamente come si aspettano le tue affermazioni.

Modifica :

La mia presunzione iniziale era che gli eventi sarebbero stati eliminati dall'elenco e passati a un thread separato, in modo che il gestore code potesse lanciare il prossimo evento in tempo, ma dai commenti che ho ricevuto, ho avuto l'idea che forse un era più auspicabile un approccio a thread singolo, che consentiva comunque agli eventi con priorità più elevata di avvicinarsi il più possibile all'ora di inizio. In tal caso, la funzione CompareTo dovrebbe cambiare come segue:

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

Prova questo contro qualsiasi ipotesi, ma penso che sia quello che stiamo cercando.