Che cos'è un buon algoritmo per la modifica di una pianificazione di & # 8220; & # 8221; nel modo più efficiente?
https://stackoverflow.com/questions/172302
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Questo è per una piccola app di pianificazione. Ho bisogno di un algoritmo per confrontare in modo efficiente due "pianificazioni", trovare le differenze e aggiornare solo le righe di dati che sono state modificate, nonché le voci in un'altra tabella con questa tabella come chiave esterna. Questa è una grande domanda, quindi dirò subito che sto cercando consigli generali o soluzioni specifiche .
MODIFICA: Come suggerito, ho ridotto significativamente la domanda.
In una tabella, associo le risorse a un arco di tempo quando vengono utilizzate.
Ho anche una seconda tabella (Tabella B) che utilizza l'ID della tabella A come chiave esterna.
La voce dalla tabella A corrispondente alla tabella B avrà un arco di tempo che sottrae l'intervallo di tempo dalla tabella B. Non tutte le voci nella tabella A avranno una voce nella tabella B.
Sto fornendo un'interfaccia per gli utenti per modificare la pianificazione delle risorse nella Tabella A. In pratica forniscono un nuovo set di dati per la Tabella A che devo trattare come diff dalla versione in il DB.
Se rimuovono completamente un oggetto dalla tabella A a cui punta la tabella B, desidero rimuovere anche la voce dalla tabella B.
Quindi, dati i seguenti 3 set:
- Gli oggetti originali dalla tabella A (dal DB)
- Gli oggetti originali dalla tabella B (dal DB)
- Il set di oggetti modificato dalla tabella A (da parte dell'utente, quindi nessun ID univoco)
Ho bisogno di un algoritmo che:
- Lascia intatte le righe nella Tabella A e nella Tabella B se non sono necessarie modifiche per tali oggetti.
- Aggiungi le righe alla Tabella A secondo necessità.
- Rimuovi le righe dalla Tabella A e dalla Tabella B. secondo necessità.
- Modifica le righe nella Tabella A e nella Tabella B. secondo necessità.
Il semplice ordinamento degli oggetti in una disposizione in cui posso applicare le operazioni di database appropriate è più che adeguato per una soluzione.
Ancora una volta, rispondi come specificatamente o in generale come preferisci, sto cercando consigli ma se qualcuno ha un algoritmo completo che mi farebbe la mia giornata. :)
MODIFICA: In risposta a Lassvek, sto fornendo alcuni dettagli aggiuntivi:
Gli oggetti della tabella B sono sempre contenuti interamente negli articoli della tabella A, non semplicemente sovrapposti.
Soprattutto, gli oggetti della Tabella B sono quantizzati, quindi dovrebbero rientrare interamente o totalmente all'esterno. Se ciò non accade, ho un errore di integrità dei dati che dovrò gestire separatamente.
Ad esempio (per usare una scorciatoia):
Table A ID Resource Start End 01 Resource A 10/6 7:00AM 10/6 11:00AM 02 Resource A 10/6 1:00PM 10/6 3:00PM Table B ID Table_A_ID Start End 01 02 10/6 1:00PM 10/6 2:00PM
Quindi voglio i seguenti comportamenti:
- Se rimuovo l'ID 02 dalla tabella A o lo accorco alle 14:00 - 15:00, dovrei rimuovere l'ID 01 dalla tabella B.
- Se estendo l'ID tabella 01 a dove termina alle 13:00, queste due voci dovrebbero essere unite in una riga e l'ID tabella B 01 ora dovrebbe puntare alla tabella A ID 01 .
- Se rimuovo 8: 00-10: 00 dalla tabella A ID 01, quella voce dovrebbe essere divisa in due voci: una per le 7:00 alle 8:00 e una nuova voce (ID 03) per le 10:00 -11:. 00:00
Soluzione
Ho lavorato molto con i punti, ma temo di non capire del tutto in che modo le tabelle A e B lavorano insieme, forse è la parola subsume che non capisco.
Puoi fare alcuni esempi concreti di ciò che vuoi fare?
Vuoi dire che i periodi di tempo registrati nella tabella A contengono interamente periodi di tempo nella tabella B, in questo modo?
|---------------- A -------------------|
|--- B ----| |--- B ---|
o si sovrappone a?
|---------------- A -------------------|
|--- B ----| |--- B ---|
o viceversa, i periodi di tempo in B contengono / si sovrappongono con A?
Diciamo che è il primo, in cui i periodi di tempo in B sono dentro / lo stesso del periodo collegato nella tabella A.
Significa che:
* A removed A-timespan removes all the linked timespans from B
* An added A-timespan, what about this?
* A shortened A-timespan removes all the linked timespans from B that now falls outside A
* A lenghtened A-timespan, will this include all matching B-timespans now inside?
Ecco un esempio:
|-------------- A1 --------------| |-------- A2 --------------|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
e poi si allunga A1, si accorcia e si sposta A2, in modo che:
|-------------- A1 ---------------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
questo significa che vuoi modificare i dati in questo modo:
1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead
che ne dici di questa modifica, A1 è allungato, ma non abbastanza per contenere completamente B3, e A2 viene spostato / accorciato allo stesso modo:
|-------------- A1 -----------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
Dato che B3 non è ora completamente compreso in A1 o A2, rimuoverlo?
Ho bisogno di alcuni esempi concreti di ciò che vuoi fare.
Modifica Altre domande
Ok, che dire di:
|------------------ A -----------------------|
|------- B1 -------| |------- B2 ------|
|---| <-- I want to remove this from A
Che dire di questo?
In entrambi:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------| |B3| |--- B2 ---|
o
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------|
Per riassumere come lo vedo, con domande, finora:
- Vuoi essere in grado di fare le seguenti operazioni su A
- Shorten
- Allunga
- Combina quando sono adiacenti, combinando due o più in uno
- Praticare dei fori rimuovendo un punto e quindi dividendolo
- Le B che sono ancora contenute in una A dopo l'aggiornamento sopra, ricollegano se necessario
- B che erano contenute, ma che ora sono completamente esterne, eliminale
- B che erano contenute, ma che ora sono parzialmente esterne, Modifica: eliminale, fai riferimento all'integrità dei dati
- Per tutte le operazioni di cui sopra, fai il minimo lavoro necessario per allineare i dati con le operazioni (invece di rimuovere tutto e inserire di nuovo)
Lavorerò su un'implementazione in C # che potrebbe funzionare quando torno a casa dal lavoro, tornerò con più tardi stasera.
Modifica Ecco una pugnalata ad un algoritmo.
- Ottimizza prima il nuovo elenco (es. combina periodi adiacenti, ecc.)
- " unire " questo elenco con i periodi master nel database nel modo seguente:
- tieni traccia di dove ti trovi in ??entrambe le liste (es. nuove ed esistenti)
- se il nuovo periodo corrente è completamente precedente al periodo corrente, aggiungilo, quindi passa al nuovo periodo successivo
- se il nuovo periodo corrente è interamente successivo al periodo esistente, rimuovi il periodo esistente e tutti i relativi periodi figlio, quindi passa al successivo periodo esistente
- se i due si sovrappongono, regolare l'attuale periodo esistente in modo che sia uguale al nuovo periodo, nel modo seguente, quindi passare al periodo nuovo ed esistente successivo
- se il nuovo periodo inizia prima del periodo esistente, sposta semplicemente l'inizio
- se il nuovo periodo inizia dopo il periodo esistente, controlla se ci sono periodi figlio nel periodo di differenza e ricordali, quindi sposta l'inizio
- fai lo stesso con l'altra estremità
- con tutti i periodi che hai "ricordato", verifica se è necessario ricollegarli o eliminarli
Dovresti creare una serie enorme di test unitari e assicurarti di coprire tutte le combinazioni di modifiche.
Altri suggerimenti
Ti suggerisco di separare le tue domande in due distinte: Il primo dovrebbe essere qualcosa del tipo: " Come ragionare sulla pianificazione delle risorse, quando rappresento un atomo di pianificazione come risorsa con ora di inizio e ora di fine? & Quot; Qui, il suggerimento di ADept di usare l'algebra ad intervallo sembra appropriato. Si prega di consultare La voce di Wikipedia "Interval Graph" e La voce del repository dell'algoritmo SUNY sulla pianificazione . La seconda domanda è una domanda del database: "Dato un algoritmo che pianifica gli intervalli e indica se due intervalli si sovrappongono o uno è contenuto in un altro, come posso usare queste informazioni per gestire un database nello schema dato?" Credo che una volta che l'algoritmo di pianificazione sarà operativo, la questione del database sarà molto più semplice da risolvere. HTH, Yuval
Il tuo post è quasi nel " troppo lungo; non ha letto " categoria - accorciandolo probabilmente ti darà più feedback.
Ad ogni modo, sull'argomento: puoi provare a esaminare una cosa chiamata " Interval Algebra "
A quanto ho capito, i tuoi utenti possono solo influenzare direttamente la tabella A. Supponendo che tu stia programmando in C #, puoi usare un semplice DataSet ADO.Net per gestire le modifiche alla tabella A. TableAdapter sa di lasciare da solo le righe non toccate e di gestire le righe nuove, modificate ed eliminate in modo appropriato.
Inoltre, è necessario definire un'eliminazione a cascata per rimuovere automaticamente gli oggetti corrispondenti nella tabella B.
L'unico caso che non viene gestito in questo modo è se un periodo di tempo nella tabella A è abbreviato s.t. non include più il record corrispondente nella tabella B. È possibile semplicemente verificare tale caso in una procedura memorizzata di aggiornamento o in alternativa definire un trigger di aggiornamento nella tabella A.
Mi sembra che qualsiasi algoritmo per questo comporterà un passaggio attraverso NewA, abbinando ResourceID, StartTime ed EndTime e tenendo traccia di quali elementi di OldA vengono colpiti. Quindi hai due serie di dati non corrispondenti, UnmatchedNewA e UnmatchedOldA.
Il modo più semplice che mi viene in mente di procedere è fondamentalmente ricominciare con questi: Scrivi tutto su UnmatchedNewA nel DB, trasferisci gli elementi di B da UnmatchedOldA alle chiavi A nuove (appena generate) ove possibile, eliminando quando no. Quindi cancella tutti UnmatchedOldA.
Se ci sono molte modifiche, questo non è certamente un modo efficiente di procedere. Nei casi in cui la dimensione dei dati non è schiacciante, preferisco la semplicità all'ottimizzazione intelligente.
È impossibile sapere se questo suggerimento finale abbia un senso senza più retroscena, ma con la possibilità che tu non ci abbia pensato in questo modo:
Invece di passare avanti e indietro l'intera raccolta A, potresti utilizzare listener di eventi o qualcosa di simile per aggiornare il modello di dati solo dove sono necessarie modifiche? In questo modo, gli oggetti modificati sarebbero in grado di determinare quali operazioni DB sono richieste al volo.
