Logica necessaria per risolvere un problema relativo alla posizione degli oggetti

Question

Logica necessaria per risolvere un problema relativo alla posizione degli oggetti

#1 da (0 voti)

3

Ho sollevato una domanda su dba.stackexchange.com ma siccome il cuore della mia domanda è in effetti fare con la logica, ho sollevato una rappresentazione più generale del mio problema qui. Penso che sia il posto giusto, scuse se non.

Ho un numero di oggetti che vengono letti e scritti in una sequenza impostata. Ho anche quattro posizioni in cui posso memorizzare questi oggetti. Questi oggetti sono di dimensioni variabili, ma per motivi di semplicità li ho valutati da 1 a 3 con 3 come il più grande. La posizione degli oggetti è fissa ad es. gli oggetti non possono essere spostati tra una sequenza e l'altra

Ho una tabella che dettaglia la sequenza del processo. Ha tre colonne: Sequenza, Sorgente, Destinazione. I processi possono essere eseguiti parallelamente e pertanto la sequenza non è un identificatore univoco, tuttavia, se necessario, è possibile considerarlo come esistente.

In un mondo ideale nessun oggetto dovrebbe essere collocato in un modo che risulterebbe in nessun oggetto richiesto per un passo di sequenza essendo collocato con un altro. Naturalmente questo è altamente improbabile e invece sto cercando una soluzione migliore rispetto a quella perfetta.

Ho quindi considerato che le potenziali posizioni potrebbero essere classificate come segue.

Tutti gli oggetti per una sequenza localizzata separatamente.
Oggetti di origine e destinazione per la sequenza localizzata separatamente.
Oggetti posizionati ovunque

Dato che ogni oggetto ha una dimensione ho anche pensato di moltiplicare la posizione per la dimensione e quindi dare un punteggio alle posizioni. In base a questo, ho trovato la soluzione migliore esaminando il punteggio totale.

Qualcuno ha qualche suggerimento o forse ha affrontato un problema simile in passato?

Qualsiasi input di aiuto è molto apprezzato.

data-structures algorithms business-logic

posta Ally Reilly 17.05.2012 - 21:28

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms business-logic

Autenticazione basata su token e basata su sessione nel back-end Considerazioni sull'architettura per un nuovo programma di scatola nera

score 0 · Accepted Answer

Quindi, non sono ancora sicuro di avere abbastanza vincoli per forzare una particolare soluzione, ma ecco la mia ipotesi migliore. Dal commento di follow-up sul post DBA, penso che il tuo reale vincolo stia cercando di minimizzare l'IO per ogni particolare passaggio dell'operazione e massimizzare il throughput IO complessivo.

Partendo, presumo che abbiamo solo oggetto (tabella) A sul volume 1.
I passi futuri genereranno:
A = > B su vol 2
A + B = > C sul volume 3
A + C = > D su vol 4

È banale assegnare gli oggetti A - > D ai volumi 1 - > 4, e non avranno mai bisogno di muoversi. Sospetto che tu abbia un numero di set come questo, quindi è la scala a complicare le cose.

Poiché utilizzi la dimensione dell'oggetto come punteggio, ti consiglio di assegnare a ciascun volume un punteggio massimo che possa gestire contemporaneamente. La dimensione dell'oggetto sarà accoppiata al tempo di IO. Per il bene della mia soluzione, A & B = 1, C = 2, D = 3.

Assegna i set con la mappatura semplice fino a quando non premi un volume completamente legato all'IO. Il 4 ° volume che gestisce Ds andrà al massimo prima, con il volume dei C che si avvicina molto alle spalle. A quel punto, rielaborare l'ordine dei volumi sugli oggetti. Per questi oggetti "fill-in", Ds andrà al volume 1 o 2, Bs e amp; Cs finirà per andare all'altra di vols 1 o 2, e letture da A sarà su vol 3. Non ho aggiunto i numeri, quindi la mia allocazione sui fill-in potrebbe essere off.

A questo punto, hai praticamente superato la capacità di quante più unità possibile. Se avessi più volumi, potresti estendere il modello in modo che tu possa lavorare sui casi Nth, N-1, N-2. Questo è più di un esercizio accademico per il tuo caso, credo.

Suppongo che tu abbia più da spostare di quanto tu abbia disponibile la larghezza di banda IO, altrimenti non sono sicuro del motivo per cui ti preoccupi di questa sorta di allocazione round-robin.