¿Qué es un buen algoritmo para editar un "horario" de manera más eficiente?
https://stackoverflow.com/questions/172302
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Esto es para una pequeña aplicación de programación. Necesito un algoritmo para comparar eficientemente dos "planes", buscar diferencias y actualizar solo las filas de datos que se han cambiado, así como las entradas en otra tabla que tienen esta tabla como clave externa. Esta es una gran pregunta, así que diré de inmediato que estoy buscando consejos generales o soluciones específicas .
EDITAR: Como se sugirió, he acortado significativamente la pregunta.
En una tabla, asocio recursos con un lapso de tiempo cuando se usan.
También tengo una segunda tabla (Tabla B) que usa el ID de la Tabla A como clave externa.
La entrada de la Tabla A correspondiente a la Tabla B tendrá un período de tiempo que subsume el período de tiempo de la Tabla B. No todas las entradas de la Tabla A tendrán una entrada en la Tabla B.
Proporciono una interfaz para que los usuarios editen la programación de recursos en la Tabla A. Básicamente, proporcionan un nuevo conjunto de datos para la Tabla A que debo tratar como un diff de la versión en la base de datos.
Si eliminan por completo un objeto de la Tabla A al que apunta la Tabla B, también quiero eliminar la entrada de la Tabla B.
Por lo tanto, dados los siguientes 3 conjuntos:
- Los objetos originales de la Tabla A (del DB)
- Los objetos originales de la Tabla B (del DB)
- El conjunto editado de objetos de la Tabla A (del usuario, por lo que no hay ID únicos)
Necesito un algoritmo que:
- Deje las filas en la Tabla A y la Tabla B sin tocar si no se necesitan cambios para esos objetos.
- Agregue filas a la Tabla A según sea necesario.
- Eliminar filas de la Tabla A y la Tabla B según sea necesario.
- Modifique las filas en la Tabla A y la Tabla B según sea necesario.
Solo ordenar los objetos en un arreglo donde pueda aplicar las operaciones de base de datos adecuadas es más que adecuado para una solución.
Una vez más, responda como específicamente o en general como quiera, estoy buscando un consejo, pero si alguien tiene un algoritmo completo que acabaría de darme cuenta. :)
EDITAR: en respuesta a lassvek, proporciono algunos detalles adicionales:
Los elementos de la Tabla B siempre están contenidos completamente dentro de los elementos de la Tabla A, no simplemente superpuestos.
Es importante destacar que, los elementos de la Tabla B se cuantifican, por lo que deberían estar completamente dentro o fuera. Si esto no sucede, entonces tengo un error de integridad de datos que tendré que manejar por separado.
Por ejemplo (para usar una taquigrafía):
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
Entonces quiero los siguientes comportamientos:
- Si elimino el ID 02 de la tabla A, o lo acorto a 2:00 PM - 3:00 PM, debería eliminar el ID 01 de la Tabla B.
- Si extiendo la ID de la Tabla A 01 hasta donde termina a la 1:00 PM, estas dos entradas deben combinarse en una fila , y la ID de la Tabla B ahora debe apuntar a la ID de la tabla A 01 .
- Si elimino 8:00 AM-10:00AM de la Tabla A ID 01, esa entrada se debe dividir en dos entradas: una para las 7:00 AM-8:00AM y una nueva entrada (ID 03) para las 10:00 AM -11: 00AM.
Solución
He trabajado mucho con los períodos, pero me temo que no entiendo completamente cómo funcionan juntas las tablas A y B, tal vez es la palabra subsumir lo que no entiendo.
¿Puedes dar algunos ejemplos concretos de lo que quieres que haga?
¿Quiere decir que los intervalos de tiempo registrados en la tabla A contienen enteramente intervalos de tiempo en la tabla B, como este?
|---------------- A -------------------|
|--- B ----| |--- B ---|
o se superpone con?
|---------------- A -------------------|
|--- B ----| |--- B ---|
o al contrario, los intervalos de tiempo en B contienen / se superponen con A?
Digamos que es el primero, donde los intervalos de tiempo en B están dentro / igual que el intervalo de tiempo vinculado en la tabla A.
¿Esto 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?
Aquí hay un ejemplo:
|-------------- A1 --------------| |-------- A2 --------------|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
y luego alargas A1 y acortas y mueves A2, de modo que:
|-------------- A1 ---------------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
esto significa que desea modificar los datos de esta manera:
1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead
qué tal esta modificación, A1 se alarga, pero no lo suficiente como para contener B3 por completo, y A2 se mueve / acorta de la misma manera:
|-------------- A1 -----------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
Dado que B3 ahora no está completamente dentro de A1 o A2, ¿eliminarlo?
Necesito algunos ejemplos concretos de lo que quieres hacer.
Editar Más preguntas
Ok, ¿qué pasa con:
|------------------ A -----------------------|
|------- B1 -------| |------- B2 ------|
|---| <-- I want to remove this from A
¿Qué pasa con esto?
O bien:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------| |B3| |--- B2 ---|
o:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------|
Para resumir cómo lo veo, con preguntas, hasta ahora:
- Desea poder realizar las siguientes operaciones en las A
- Acortar
- alargar
- Se combinan cuando son adyacentes, combinando dos o más en uno
- Haga agujeros en ellos eliminando un punto y, por lo tanto, dividiéndolos
- B's que aún están contenidas dentro de una A después de la actualización anterior, vuelva a vincularlas si es necesario
- B que estaban contenidas, pero ahora están completamente fuera, elimínelas
- B que estaban contenidas, pero ahora están parcialmente fuera, Editar: elimine estos, ref. integridad de datos
- Para todas las operaciones anteriores, haga el mínimo trabajo necesario para alinear los datos con las operaciones (en lugar de simplemente eliminar todo e insertar de nuevo)
Trabajaré en una implementación en C # que podría funcionar cuando llegue a casa del trabajo, regresaré con más esta noche.
Editar Aquí se muestra un algoritmo.
- Optimice la nueva lista primero (es decir, combine períodos adyacentes, etc.)
- " fusionar " esta lista con los períodos maestros en la base de datos de la siguiente manera:
- realizar un seguimiento de dónde se encuentra en ambas listas (es decir, nuevo y existente)
- si el nuevo período actual es completamente anterior al período actual existente, agréguelo y luego pase al siguiente período nuevo
- si el nuevo período actual es completamente posterior al período actual actual, elimine el período existente y todos sus períodos secundarios, luego pase al siguiente período existente
- si los dos se superponen, ajuste el período actual actual para que sea igual al nuevo período, de la siguiente manera, luego pase al siguiente período nuevo y existente
- si el nuevo período comienza antes del período existente, simplemente mueva el inicio
- si el nuevo período comienza después del período existente, verifique si hay algún período secundario en el período de diferencia, y recuérdelos, luego mueva el inicio
- haz lo mismo con el otro extremo
- con cualquier período que haya "recordado", vea si es necesario volver a vincularlo o eliminarlo
Debería crear un conjunto masivo de pruebas unitarias y asegurarse de cubrir todas las combinaciones de modificaciones.
Otros consejos
Le sugiero que desacople sus preguntas en dos preguntas separadas: El primero debería ser algo como: "¿Cómo razonar sobre la programación de recursos, cuando se representa un átomo de programación como un recurso con hora de inicio y hora de finalización?" Aquí, la sugerencia de ADept de usar álgebra de intervalos parece adecuada. Consulte La entrada de Wikipedia 'Interval Graph' y La entrada del repositorio del algoritmo SUNY sobre la programación . La segunda pregunta es una pregunta de la base de datos: "Dado un algoritmo que programa intervalos e indica si dos intervalos se superponen o si uno está contenido en otro, ¿cómo utilizo esta información para administrar una base de datos en el esquema dado?" Creo que una vez que el algoritmo de programación esté en su lugar, la pregunta de la base de datos será mucho más fácil de resolver. HTH, Yuval
Su publicación está casi en el " demasiado larga; no leído " categoría: acortarlo probablemente le dará más comentarios.
De todos modos, en el tema: puedes intentar buscar en una cosa llamada " Álgebra de intervalos "
Según tengo entendido, sus usuarios solo pueden afectar directamente la tabla A. Suponiendo que esté programando en C #, podría usar un conjunto de datos ADO.Net simple para administrar las modificaciones a la tabla A. El Adaptador de tabla sabe dejar solo las filas intactas y Manejar las filas nuevas, modificadas y eliminadas adecuadamente.
Además, debe definir una eliminación en cascada para eliminar automáticamente los objetos correspondientes en la tabla B.
El único caso que no se maneja de esta manera es si se acorta un período de tiempo en la tabla A s.t. ya no subsume el registro correspondiente en la Tabla B. Simplemente puede verificar ese caso en un procedimiento almacenado de actualización o, alternativamente, definir un activador de actualización en la tabla A.
Me parece que cualquier algoritmo para esto incluirá un paso a través de NewA, ResourceID, StartTime y EndTime, y un seguimiento de qué elementos del OldA son afectados. Luego tiene dos conjuntos de datos no coincidentes, UnmatchedNewA y UnmatchedOldA.
La forma más sencilla en que puedo pensar para proceder es básicamente comenzar de nuevo con estos: Escriba todo UnmatchedNewA en la base de datos, transfiera elementos de B de UnmatchedOldA a las nuevas claves A (recién generadas) donde sea posible, borrando cuando no. Luego borre todo UnmatchedOldA.
Si hay muchos cambios, ciertamente no es una forma eficiente de proceder. Sin embargo, en los casos en que el tamaño de los datos no es abrumador, prefiero la simplicidad a la optimización inteligente.
Es imposible saber si esta sugerencia final tiene sentido sin más antecedentes, pero en el caso de que no lo hayas pensado de esta manera:
En lugar de pasar toda la colección A de un lado a otro, ¿podría usar detectores de eventos o algo similar para actualizar el modelo de datos solo cuando se necesiten cambios? De esta forma, los objetos que se alteran podrían determinar qué operaciones de base de datos se requieren sobre la marcha.
