Miglioramento dell'algoritmo di campionamento

Question

Miglioramento dell'algoritmo di campionamento

#1 da (6 voti)

2

Sto avendo un po 'di problemi a progettare una nuova funzione al momento. Fa parte di un sistema di gestione delle risorse. Mi stavo chiedendo se qualcuno ha esperienza nel fare qualcosa di simile.

Proverò a spiegare:

Risorsa : una persona, un luogo o una cosa

Modello di disponibilità (AT) : consente di definire un modello di disponibilità standard per un tipo di risorsa. ad esempio: lun-ven 9-5.

Disponibilità aggiuntiva delle risorse (AA) : consente di definire la disponibilità una tantum per una risorsa. ad esempio: il lavoro straordinario di Bob 10-3 il sabato.

Esclusioni dalla disponibilità delle risorse (AE) : consente di definire quando una risorsa non è disponibile. ad esempio: la camera 4 viene pulita tra 4-5 di venerdì.

È abbastanza semplice verificare se una risorsa è disponibile o meno in un momento specifico: Disponibilità = (AT (rID, tempo) || AA (rID, tempo)) & & ! AE (rID, tempo).

Ma devo essere in grado di interrogare la disponibilità di una risorsa per un periodo di tempo. vale a dire: "La stanza 4 è disponibile alle 9:00 per 2 ore giovedì?".

Finora, ho creato un algoritmo che "campiona" la disponibilità a intervalli specifici nel periodo di tempo. Tuttavia, ciò significa che la disponibilità restituita è in ritardo rispetto alla disponibilità effettiva e alcune informazioni potrebbero essere perse.

Ad esempio: se campiono la disponibilità ogni 15 minuti tra 9 e 11, mancherebbe un'esclusione tra 9:05 e 9:10.

Potrei usare un periodo di campionamento molto piccolo (es: 1 minuto) ma potrebbe non essere performante e nel complesso è ancora un brutto approccio brute-force.

Esistono schemi o algoritmi standard per questo tipo di problema?

performance design-patterns algorithms optimization architectural-patterns

posta Kev 14.01.2016 - 16:35

fonte

1 risposta

Leggi altre domande sui tag performance design-patterns algorithms optimization architectural-patterns

Come migliorare le prestazioni per la serializzazione e deserializzazione di un grafico a oggetti di grandi dimensioni? Che cos'è GLFW in relazione a OpenGL

score 6 · Accepted Answer

Innanzitutto, riduci il problema a un test di disponibilità "al giorno". Tutti i tuoi esempi utilizzano intervalli per un solo giorno, ma se vuoi anche supportare un intervallo come "Lunedi 10:00 a Mercoledì 14:00", suddividilo in tre test per "Lunedì 10:00 alle 23:59" , "Giovedì 00:00 alle 23:59" e "Mercoledì dalle 00:00 alle 10:00".

Per ogni giorno, memorizzare una rappresentazione a intervalli delle ore disponibili sotto forma di un elenco di intervalli. Inizialmente, l'elenco contiene solo un intervallo, diciamo [9:00 , 17:00] per ogni giorno e ogni volta che una parte della giornata viene bloccata per un intervallo diverso, (ad esempio, la stanza viene bloccata dalle 10:00 alle 11:25), calcola il nuovo elenco risultante di intervalli (qui [9:00,10:00] , [11:25, 17:00] ). La disponibilità aggiuntiva porta a intervalli aggiuntivi per alcune date e il "controllo di disponibilità" non è altro che un test sovrapposto di un nuovo intervallo con tutti gli intervalli di "tempo disponibile" di un giorno specifico.

Quindi in termini di set, tutto ciò che serve è un'operazione di "sottrazione" su intervalli, un'operazione "unione" e un test di sovrapposizione.

L'implementazione del test di sovrapposizione per due intervalli non è difficile, non richiede alcun "campionamento", basta confrontare i valori minimo e massimo di ogni intervallo. Vedi qui per un esempio. Anche creare unioni di intervallo o "sottrarre" intervalli non è troppo complicato, vedere qui , si noti che la "differenza di set" di due intervalli produce due nuovi intervalli, un nuovo intervallo o zero intervalli. Al secondo link, troverai anche un riferimento a un pacchetto intervallo in Python. Immagino che ci siano componenti simili o snippet di codice disponibili per ciascun linguaggio di programmazione principale, se non vuoi implementarlo da solo.