O que é um bom algoritmo para editar um “cronograma” de forma mais eficiente?

https://stackoverflow.com/questions/172302

05-07-2019
|

Pergunta

Este é um aplicativo de agendamento pequena. Eu preciso de um algoritmo para comparar de forma eficiente duas "agendas", encontrar diferenças e atualizar somente as linhas de dados que foram alterados, bem como entradas em outra tabela com esta tabela como uma chave estrangeira. Esta é uma grande questão, então eu vou dizer de imediato que eu estou procurando qualquer aconselhamento Geral ou soluções específicas .

EDIT:. Como sugerido, eu ter encurtado significativamente a questão

Em uma mesa, eu associar recursos com um espaço de tempo quando eles são usados.

I também tem uma segunda tabela (Tabela B), que utiliza o ID do quadro A, como uma chave estrangeira.

A entrada a partir da Tabela A que corresponde ao Quadro B irá ter um período de tempo que subsumes o espaço de tempo a partir da Tabela B. Nem todas as entradas na Tabela A terá uma entrada na Tabela B.

Eu estou fornecendo uma interface para os usuários a editar o agendamento de recursos no quadro A. Eles basicamente fornecer um novo conjunto de dados para a Tabela A que eu preciso tratar como um diff a partir da versão em o DB.

Se eles remover completamente um objeto a partir da Tabela A, que é apontado pela Tabela B, eu quero remover a entrada da Tabela B também.

Assim, dadas as seguintes 3 séries:

Os objetos originais da Tabela A (do DB)

Os objectos originais da Tabela B (a partir do banco de dados)

O conjunto editada dos objectos da Tabela Um (a partir do utilizador, de modo nenhum IDs únicas)

Eu preciso de um algoritmo que:

linhas licença em Tabela A e Tabela B intocadas se nenhumas alterações são necessárias para esses objetos.

Adicionar linhas a Tabela A, conforme necessário.

Remova as linhas da Tabela A e Tabela B, conforme necessário.

linhas Modificar na Tabela A e Tabela B, conforme necessário.

Apenas classificar os objetos em um arranjo onde eu possa aplicar as operações de banco de dados apropriados é mais do que adequado para uma solução.

Mais uma vez, por favor resposta como especialmente ou em geral como você gosta, Eu estou procurando conselhos, mas se alguém tem um algoritmo completo que seria apenas fazer o meu dia. :)

EDIT: Em resposta a lassvek, eu estou fornecendo alguns detalhes adicionais:

itens da Tabela B estão sempre contidas inteiramente dentro de itens Tabela A, e não apenas se sobrepõem.

Importante, itens da Tabela B são quantificados para que eles devem cair ou inteiramente dentro ou completamente fora. Se isso não acontecer, então eu tenho um erro de integridade de dados que eu vou ter que lidar separadamente.

Por exemplo (para usar uma forma abreviada):

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

Então, eu quero os seguintes comportamentos:

Se eu remover ID 02 da tabela A, ou reduzi-lo às 2:00 PM -. 3:00 PM, eu deveria remover ID 01 da Tabela B

Se eu estender Tabela A ID 01 a onde termina às 1:00 PM, estas duas entradas devem ser fundidos em uma linha , e Tabela B ID 01 deve agora apontar para a tabela A ID 01 .

Se eu remover 8h00-10:00 da Tabela A ID 01, que a entrada deve ser dividido em duas entradas: uma para 07h00-08h00, e uma nova entrada (ID 03) para 10:00 -11:. 00:00

Foi útil?

Solução

Eu tenho trabalhado extensivamente com períodos, mas eu tenho medo que eu não entendo completamente como a tabela A e B de trabalho juntos, talvez seja a palavra subsume que eu não entendo.

Você pode dar alguns exemplos concretos do que você quer fazer?

Você quer dizer que TimeSpans gravados na tabela A contém inteiramente intervalos de tempo na tabela B, assim?

|---------------- A -------------------| |--- B ----| |--- B ---|

ou sobreposições com?

|---------------- A -------------------| |--- B ----| |--- B ---|

ou o caminho oposto, TimeSpans em B contém / sobreposições com A?

Vamos dizer que é o primeiro, onde intervalos de tempo em B estão dentro / o mesmo que o período de tempo ligado no quadro A.

Isso significa que:

* 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?

Aqui está um exemplo:

|-------------- A1 --------------| |-------- A2 --------------| |---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|

e então você alongar A1 e encurtar e mover A2, de modo que:

|-------------- A1 ---------------------------------| |--- A2 --| |---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|

Isso significa que você deseja modificar os dados como este:

1. Lengthen (update) A1 2. Shorten and move (update) A2 3. Re-link (update) B3 from A2 to A1 instead

como sobre esta modificação, A1 é alongada, mas não o suficiente para conter B3 inteiramente, e A2 é movido / encurtado da mesma maneira:

|-------------- A1 -----------------------------| |--- A2 --| |---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|

Desde B3 agora não é inteiramente dentro de A1 ou A2, removê-lo?

Eu preciso de alguns exemplos concretos do que você quer fazer.

Editar Mais perguntas

Ok, o que acontece:

|------------------ A -----------------------| |------- B1 -------| |------- B2 ------| |---| <-- I want to remove this from A

O que sobre isso?

Ou:

|------------------ A1 ----| |---- A2 -----| |------- B1 -------| |B3| |--- B2 ---|

ou

|------------------ A1 ----| |---- A2 -----| |------- B1 -------|

Para resumir como eu vê-lo, com perguntas, até agora:

Você quer ser capaz de fazer as seguintes operações em uma de

Shorten

Alongar

Combine quando eles são adjacentes, combinando dois ou mais em um

Faça furos no-los, removendo um período e, assim, dividindo-

O B que ainda estão contidos dentro de um A após a atualização acima, relink se necessário

O B que foram contidas, mas agora estão totalmente fora, excluí-los

O B que foram contidas, mas agora estão parcialmente fora, Editar: excluir esses, a integridade dos dados ref

Para todas as operações acima, fazer o mínimo de trabalho mínimo necessário para trazer os dados em linha com as operações (em vez de apenas remover tudo e inserção de novo)

Eu vou trabalhar em uma implementação em C # que o trabalho força quando eu chegar em casa do trabalho, eu vou voltar com esta noite mais tarde.

Editar Aqui está uma facada em um algoritmo.

Optimizar a nova lista primeiro (ou seja. Combinar períodos adjacentes, etc.)

"Merge" desta lista com os períodos mestre no banco de dados da seguinte maneira:

acompanhar onde em ambas as listas (ie. Novos e existentes) você

se o novo período atual é totalmente antes do período existente atual, adicioná-lo, em seguida, passar para o próximo período de novo

se o novo período atual é inteiramente após o período existente atual, remova o período existente e todos os seus períodos de criança, em seguida, passar para o próximo período existente

Se os dois se sobrepõem, ajuste o período existente atual para ser igual ao novo período, da seguinte maneira, em seguida, passar para o próximo período de novos e existentes

Se novos período começa antes do período existente, basta mover o início

se novo período começa após o período existente, verificar se todos os períodos de criança são na diferença-período, e recordá-los, em seguida, mover o início

fazer o mesmo com a outra extremidade

com quaisquer períodos você "lembrado", ver se eles precisam ser relinked ou suprimido

Você deve criar um conjunto enorme de testes de unidade e certifique-se de cobrir todas as combinações de modificações.

Outras dicas

Eu sugiro que você dissociar suas perguntas em dois separados: O primeiro deve ser algo como: "Como fazer razão que eu sobre agendamento de recursos, ao representar um átomo de programação como um recurso com o tempo de início e fim" Aqui, a sugestão do adepto de usar álgebra intervalo parece apropriado. Por favor, veja a entrada A Wikipedia 'Interval Graph' e A entrada repositório algoritmo SUNY na programação . A segunda questão é uma questão de banco de dados: "Dado um algoritmo que intervalos horários e indicar se dois intervalos se sobrepõem ou se está contido em outro, como posso usar essas informações para gerenciar um banco de dados no esquema dado?" Eu acredito que uma vez que o algoritmo de programação está no lugar, a questão do banco de dados será muito mais fácil de resolver. HTH, Yuval

Você post é quase no "demasiado longo; não leu". Categoria - encurtando ele provavelmente vai lhe dar mais feedback

De qualquer forma, sobre o tema: você pode tentar olhando para uma coisa chamada "Intervalo Algebra"

Como eu entendo que você, seus usuários podem afetar somente diretamente a tabela A. Assumindo que você está programando em C #, você pode usar uma simples ADO.Net DataSet para gerenciar modificações para a tabela A. A TableAdapter sabe deixar linhas intocadas sozinho e lidar com as linhas novas, modificados e excluídos de forma adequada.

Além disso, você deve definir uma exclusão em cascata, a fim de remover automaticamente objetos na tabela B. correspondente

O único caso que não é tratado dessa maneira é se um período de tempo na tabela A é encurtado S. T. não subsumir o registro correspondente na Tabela B mais. Você poderia simplesmente verificar para esse caso em um procedimento de actualização armazenado ou alternativamente definir um update-disparo na tabela Um.

Parece-me como qualquer algoritmo para isso será envolvem uma passagem através Newa, combinando ResourceID, StartTime e EndTime, e manter o controle de quais elementos de Olda obter sucesso. Então você tem dois conjuntos de dados não correspondentes, UnmatchedNewA e UnmatchedOldA.

A maneira mais simples que posso pensar para avançar é começar basicamente acabar com estes: Escreve todas UnmatchedNewA ao DB, elementos de transferência de B de UnmatchedOldA em chaves New A (apenas gerado) sempre que possível, a eliminação quando não. Em seguida, acabar com toda a UnmatchedOldA.

Se houver um monte de mudanças, este não é certamente uma maneira eficiente para prosseguir. Nos casos em que o tamanho dos dados não é esmagadora, no entanto, eu prefiro simplicidade para otimização inteligente.

É impossível saber se esta última sugestão faz qualquer sentido, sem mais fundo, mas na chance que você não pense da seguinte maneira:

Em vez de passar toda a volta Uma coleção e para trás, você poderia usar ouvintes de eventos ou algo similar para atualizar o modelo de dados apenas quando mudanças são necessárias? Desta forma, os objetos que estão sendo alterados seria capaz de determinar quais as operações de banco de dados são necessários em tempo real.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow