Qu'est-ce qu'un bon algorithme pour modifier un & planning # 8220; & # 8221; plus efficacement?
https://stackoverflow.com/questions/172302
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Ceci est pour une petite application de planification. J'ai besoin d'un algorithme pour comparer efficacement deux "programmes", rechercher des différences et mettre à jour uniquement les lignes de données qui ont été modifiées, ainsi que les entrées d'une autre table ayant cette table comme clé étrangère. C’est une grande question. Je vous dirai donc tout de suite que je recherche un conseil général ou des solutions spécifiques .
MODIFIER: Comme suggéré, j'ai considérablement raccourci la question.
Dans un tableau, j'associe des ressources sur une période de temps d'utilisation.
J'ai aussi un deuxième tableau (tableau B) qui utilise l'ID du tableau A comme clé étrangère.
L'entrée du tableau A correspondant au tableau B aura une durée qui subsume celle du tableau B. Toutes les entrées du tableau A n'auront pas nécessairement une entrée du tableau B.
Je fournis une interface permettant aux utilisateurs de modifier la planification des ressources dans le tableau A. Ils fournissent essentiellement un nouvel ensemble de données pour le tableau A que je dois traiter comme un diff à partir de la version la DB.
S'ils suppriment complètement un objet de la table A désigné par la table B, je souhaite également supprimer l'entrée de la table B.
Donc, étant donné les 3 ensembles suivants:
- Les objets d'origine de la table A (à partir de la base de données)
- Les objets d'origine de la table B (à partir de la base de données)
- Ensemble d'objets modifié de la table A (de l'utilisateur, donc pas d'identifiant unique)
J'ai besoin d'un algorithme qui va:
- Ne modifiez pas les lignes des tableaux A et B si aucune modification n'est nécessaire pour ces objets.
- Ajoutez des lignes à la table A selon vos besoins.
- Supprimez les lignes des tableaux A et B selon vos besoins.
- Modifiez les lignes des tableaux A et B selon vos besoins.
Le simple fait de trier les objets dans un arrangement dans lequel je peux appliquer les opérations de base de données appropriées est plus que suffisant pour une solution.
Encore une fois, répondez comme spécifiquement ou généralement à votre guise. Je cherche des conseils, mais si quelqu'un a un algorithme complet qui ferait toute ma journée. :)
EDIT: En réponse à lassvek, je fournis des détails supplémentaires:
Les éléments de la table B sont toujours entièrement contenus dans les éléments de la table A et ne se chevauchent pas.
Il est important de noter que les éléments de la table B sont quantifiés et doivent donc être entièrement situés à l'intérieur ou à l'extérieur. Si cela ne se produit pas, j'ai une erreur d'intégrité des données que je devrai gérer séparément.
Par exemple (pour utiliser un raccourci):
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
Je souhaite donc les comportements suivants:
- Si je supprime l'ID 02 du tableau A ou le réduit à 14h00 - 15h00, je devrais supprimer l'ID 01 du tableau B.
- Si j'étend la table A ID 01 à l'endroit où elle se termine à 13h00, ces deux entrées doivent être fusionnées dans une ligne , et la table B ID 01 doit maintenant pointer vers la table A ID 01. .
- Si je retire de la table A ID 01 entre 8h00 et 10h00, cette entrée doit être scindée en deux entrées: une pour 7h00 - 8h00 et une nouvelle entrée (ID 03) pour 10h00. -11h00.
La solution
J'ai beaucoup travaillé avec les règles, mais je crains de ne pas comprendre parfaitement comment les tableaux A et B fonctionnent ensemble. C'est peut-être le mot subsume que je ne comprends pas.
Pouvez-vous donner des exemples concrets de ce que vous voulez faire?
Voulez-vous dire que les intervalles de temps enregistrés dans le tableau A contiennent uniquement des intervalles de temps dans le tableau B, comme ceci?
|---------------- A -------------------|
|--- B ----| |--- B ---|
ou se chevauche avec?
|---------------- A -------------------|
|--- B ----| |--- B ---|
ou l’inverse, les intervalles de temps dans B contiennent / chevauchent A?
Disons que c'est le premier, où les intervalles de temps dans B sont identiques / identiques à l'intervalle de temps lié dans le tableau A.
Est-ce que cela signifie 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?
Voici un exemple:
|-------------- A1 --------------| |-------- A2 --------------|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
puis vous allongez A1, raccourcissez et déplacez A2, de sorte que:
|-------------- A1 ---------------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
Cela signifie que vous souhaitez modifier les données comme suit:
1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead
Que diriez-vous de cette modification, A1 est allongé, mais pas assez pour contenir B3 entièrement, et A2 est déplacé / raccourci de la même manière:
|-------------- A1 -----------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
Etant donné que B3 n'est plus entièrement dans A1 ou A2, supprimez-le?
J'ai besoin d'exemples concrets de ce que vous voulez faire.
Modifier d'autres questions
Ok, qu'en est-il:
|------------------ A -----------------------|
|------- B1 -------| |------- B2 ------|
|---| <-- I want to remove this from A
Qu'en est-il?
Soit:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------| |B3| |--- B2 ---|
ou:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------|
Pour résumer comment je vois les choses, avec des questions, jusqu'à présent:
- Vous voulez pouvoir effectuer les opérations suivantes sur A
- Raccourcir
- Allonger
- Combinez quand ils sont adjacents, en combinant deux ou plus en un
- Percez des trous en supprimant un point et en le divisant ainsi
- Les B qui sont toujours contenus dans un A après la mise à jour ci-dessus, reliez-les si nécessaire
- Les B qui étaient contenus, mais sont maintenant entièrement à l'extérieur, supprimez-les
- Les B qui étaient contenus, mais qui sont maintenant partiellement à l'extérieur, Modifier: supprimez-les, en référence à l'intégrité des données
- Pour toutes les opérations ci-dessus, effectuez le travail minimum nécessaire pour aligner les données sur les opérations (au lieu de tout supprimer et d'insérer à nouveau)
Je travaillerai sur une implémentation en C # qui pourrait fonctionner une fois rentré du travail. Je reviendrai plus tard ce soir.
Modifier Voici un coup de poignard pour un algorithme.
- Optimisez d'abord la nouvelle liste (c'est-à-dire, combinez des périodes adjacentes, etc.)
- " fusionner " cette liste avec les périodes principales dans la base de données de la manière suivante:
- gardez une trace de l'endroit où vous êtes dans les deux listes (c'est-à-dire nouvelle et existante)
- si la nouvelle période actuelle est entièrement antérieure à la période existante actuelle, ajoutez-la, puis passez à la nouvelle période suivante
- si la nouvelle période en cours est entièrement postérieure à la période en cours, supprimez la période existante et toutes ses périodes enfant, puis passez à la période existante suivante
- si les deux se chevauchent, ajustez la période existante en cours pour qu'elle soit égale à la nouvelle période, de la manière suivante, puis passez à la prochaine période, nouvelle et existante
- si la nouvelle période commence avant la période existante, déplacez simplement le début
- si une nouvelle période commence après une période existante, vérifiez si des périodes enfant se trouvent dans la période de différence, et mémorisez-les, puis déplacez le début
- faire la même chose avec l'autre extrémité
- avec toutes les périodes mémorisées, voyez si elles doivent être reliées ou supprimées
Vous devez créer un ensemble considérable de tests unitaires et vous assurer de couvrir toutes les combinaisons de modifications.
Autres conseils
Je vous suggère de dissocier vos questions en deux questions distinctes: La première devrait être: "Comment raisonner à propos de la planification des ressources, lors de la représentation d’un atome de planification en tant que ressource avec une heure de début et une heure de fin?" Ici, la suggestion d'Adept d'utiliser l'algèbre en intervalles semble aller de soi. Veuillez consulter l'entrée Wikipedia "Graphique à intervalles" et L'entrée du référentiel d'algorithmes SUNY sur la planification . La deuxième question est une question de base de données: "Étant donné un algorithme qui planifie des intervalles et indique si deux intervalles se chevauchent ou s'ils sont contenus dans un autre, comment utiliser ces informations pour gérer une base de données dans le schéma donné?" Je pense qu'une fois l'algorithme de planification mis en place, la question de la base de données sera beaucoup plus facile à résoudre. HTH, Yuval
Vous publiez est presque dans le "trop ??long"; n'a pas lu " catégorie - le raccourcir vous donnera probablement plus de commentaires.
Quoi qu'il en soit, sur le sujet: vous pouvez essayer de rechercher un élément appelé " Interval Algebra " <
Si je vous comprends bien, vos utilisateurs ne peuvent affecter que directement la table A. En supposant que vous programmez en C #, vous pouvez utiliser un simple ensemble de données ADO.Net pour gérer les modifications apportées à la table A. Le TableAdapter sait laisser les lignes non modifiées gérer les nouvelles lignes, modifiées et supprimées de manière appropriée.
De plus, vous devez définir une suppression en cascade afin de supprimer automatiquement les objets correspondants du tableau B.
Le seul cas qui ne soit pas traité de cette manière est si un intervalle de temps dans le tableau A est raccourci à la fois. il ne subsume plus l'enregistrement correspondant dans le tableau B. Vous pouvez simplement rechercher ce cas dans une procédure stockée de mise à jour ou définir un déclencheur de mise à jour sur la table A.
Il me semble que tout algorithme impliquerait un passage par NewA, une correspondance entre ResourceID, StartTime et EndTime, et le suivi des éléments de OldA touchés. Ensuite, vous avez deux ensembles de données non correspondantes, UnmatchedNewA et UnmatchedOldA.
La façon la plus simple de procéder est de commencer par les étapes suivantes: Écrivez tous les UnmatchedNewA dans la base de données, transférez les éléments de B de UnmatchedOldA dans les nouvelles clés A (si elles sont générées), si possible, en supprimant les autres. Ensuite, supprimez tout UnmatchedOldA.
S'il y a beaucoup de changements, ce n'est certainement pas une façon efficace de procéder. Dans les cas où la taille des données n’est pas trop lourde, je préfère la simplicité à une optimisation intelligente.
Il est impossible de savoir si cette dernière suggestion a du sens sans plus de fond, mais vous ne l'auriez pas pensé autrement:
Au lieu de faire passer la collection A dans son ensemble, pouvez-vous utiliser des écouteurs d’événements ou quelque chose de similaire pour mettre à jour le modèle de données uniquement lorsque des modifications sont nécessaires? Ainsi, les objets en cours de modification pourront déterminer quelles opérations de base de données sont requises à la volée.
