c# - funzionamento - quick sort




Algoritmo di ordinamento per un problema di ordinamento non basato sul confronto? (7)

Questo è in realtà più di un problema di ordinamento. È un problema di pianificazione a macchina singola con date di rilascio. A seconda di cosa stai cercando di fare, il problema potrebbe essere NP-Hard. Ad esempio, se stai cercando 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 vuoi mai una soluzione con lacune, quindi quello che potresti dover semplicemente fare è una semplice simulazione di eventi discreti (O (n log (n))). È necessario memorizzare released_jobs come 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 poco prima di un lavoro breve e ad alta priorità, ma produrrà una pianificazione con la proprietà che non ci sono interruzioni (se è possibile una pianificazione senza spazi vuoti) .

Attualmente mi trovo di fronte a un difficile problema di classificazione. Ho una raccolta di eventi che devono essere ordinati l'uno contro l'altro (un ordinamento di confronto ) e contro la loro posizione relativa nell'elenco.

Nei termini più semplici, ho una lista di eventi che hanno ciascuno una priorità (numero intero), una durata (secondi) e una prima volta in cui l'evento può apparire nella lista. Ho bisogno di ordinare gli eventi in base alla priorità, ma nessun evento può comparire nella lista prima della sua prima occorrenza. Ecco un esempio per (si spera) 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
}

L'oggetto "b" deve venire per ultimo perché non è permesso iniziare fino a 6,0 secondi nella lista, quindi è differito e "c" deve andare prima di "b" anche se la sua priorità è inferiore. (Spero che quanto sopra spieghi il mio problema, se non me lo fa sapere e lo modifico.)

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

Spero di trovare risorse su come ordinare algoritmi e strutture dati per aiutarmi a progettare una buona soluzione per questo "tipo" di problemi. 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 è una preoccupazione.

Modifica: chiarimenti (in base ai commenti)

  • Gli eventi consumano la loro intera durata (cioè non c'è alcuna sovrapposizione di eventi consentiti)
  • Gli eventi devono verificarsi al loro o dopo il loro tempo, 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 la somma di tutti gli eventi che possono rientrare in una lista. Questo non è mostrato sopra. (In realtà la durata di tutti gli eventi sarà di gran lunga superiore alla durata massima della lista temporale).
  • Non ci possono essere spazi vuoti. (Non ci sono buchi da provare e tornare a riempire.)

Modifica: risposta

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


Credo:

  1. Ordina le attività in base alla priorità
  2. Adatta le attività in una linea del tempo, prendendo il primo spazio disponibile dopo il loro primo tempo, che ha un buco abbastanza grande per l'attività.

Convertire la linea temporale in un elenco di attività e attende (per gli spazi vuoti).

Domande:

  1. Sono permessi gli spazi?
  2. Le attività possono essere divise?
  3. Dati i compiti come nella domanda: è meglio ritardare b per completare c, o fare d in modo che b possa iniziare in tempo?

Modificare:

Os le risposte alle mie domande sono:

  1. No (ish - se non c'è niente da correre, suppongo che potremmo avere un gap)
  2. No
  3. Ancora non è chiaro, ma suppongo che l'esempio suggerisca run c e delay b.

In questo caso l'algoritmo potrebbe essere:

  1. Ordina per priorità
  2. Mantieni un contatore per il "tempo" corrente che inizia con t = 0
  3. Cerca attraverso l'elenco ordinato, per l'elemento con la priorità più alta che può essere avviato in t.
  4. Aggiungi l'articolo all'ordine corrente e aggiungi la sua durata a t.
  5. Ripeti 3 e 4 finché la lista non è esaurita. Se non ci sono attività eseguibili at, e ci sono attività rimanenti in attesa, attenersi a un'attività di sonno di 1 secondo nell'ordine di esecuzione.

Questo algoritmo è anche O (n ^ 2).


Per inciso, nel caso più generale potrebbe non esserci soluzione (a meno che non siano consentiti spazi vuoti, come ha sottolineato Douglas). Per 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 };

Se disponi di un numero limitato di livelli di priorità, puoi mantenere una serie di elenchi ordinati nel tempo, 1 per ogni livello. Ogni volta che hai bisogno del prossimo evento, controlla la testa di ogni lista in ordine di priorità fino a quando ne trovi uno il cui tempo di avvio è passato. (Tieni traccia dell'ora di inizio minima mentre controlli - nel caso in cui nessun evento sia già pronto, sai quale aspettare)


Sembra un problema che ho avuto l'altro giorno, a cui ho risposto qui .
Supponendo che stai usando C # ...


In altre parole, si desidera ottimizzare il tempo di esecuzione complessivo durante la formulazione di due vincoli (forte: primo punto di esecuzione, debole: priorità)? Questo è chiamato un problema di soddisfazione dei vincoli . Esistono risolutori speciali per questo tipo di problema.

Per inciso, la soluzione di jakber non funziona. Anche senza 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 .


Ecco un codice Python sulla falsariga della risposta di Douglas. Per prima cosa ordiniamo per priorità, quindi adattiamo una timeline in modo selezione-ordinamento:

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




mathematical-optimization