Was ist ein guter Algorithmus einen „Zeitplan“ am effizientesten für die Bearbeitung?
https://stackoverflow.com/questions/172302
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Dies ist für eine kleine Planungs App. Ich brauche einen Algorithmus, um effizient zwei „Zeitplan“ zu vergleichen, Unterschiede finden und aktualisierte nur die Datenzeilen, die, sowie für Fremdeinträge in einer anderen Tabelle geändert wurden, als Fremdschlüssel in dieser Tabelle haben. Dies ist eine große Frage, also werde ich sagen, sofort ich suche entweder allgemeine Beratung oder spezifische Lösungen .
EDIT:. Wie bereits angedeutet, ich habe die Frage deutlich verkürzt
In einer Tabelle, verbinde ich Ressourcen mit einer Spannweite von Zeit, wenn sie verwendet werden.
Ich habe auch eine zweite Tabelle (Tabelle B), die die ID von Tabelle A als Fremdschlüssel verwendet.
Der Eintrag aus Tabelle A Tabelle B entspricht, wird eine Zeitspanne aufweisen, die subsumiert die Zeitspanne von Tabelle B nicht alle Einträge in der Tabelle A wird ein Eintrag in der Tabelle B haben
Ich bin eine Schnittstelle für Benutzer, die Ressource Zeitplan in der Tabelle A bearbeiten Sie bieten grundsätzlich einen neuen Satz von Daten für die Tabelle A, die ich als eine Behandlung benötigen diff aus der Fassung die DB.
Wenn sie ein Objekt vollständig aus Tabelle A entfernen, die durch Tabelle B gezeigt wird, möchte ich auch den Eintrag aus Tabelle B entfernen.
So, da die folgenden drei Sätze:
- Die Originalobjekte aus Tabelle A (aus der DB)
- Die Originalobjekte aus Tabelle B (aus der DB)
- Die bearbeitete Menge von Objekten aus der Tabelle A (vom Benutzer, so dass keine eindeutige IDs)
Ich brauche einen Algorithmus das wird:
- Lassen Sie Zeilen in Tabelle A und Tabelle B unberührt, wenn keine Änderungen für diese Objekte benötigt werden.
- Fügen Sie Zeilen der Tabelle A nach Bedarf.
- Entfernen von Zeilen aus Tabelle A und Tabelle B nach Bedarf.
- Ändern Zeilen in Tabelle A und Tabelle B nach Bedarf.
Sortieren Sie die Objekte in eine Anordnung, wo ich die entsprechenden Datenbankoperationen anwenden kann, ist mehr als ausreichend für eine Lösung.
Auch hier bitte beantworten wie insbesondere oder im Allgemeinen , wie Sie möchten, ich bin der Suche nach Beratung, aber wenn jemand hat einen vollständigen Algorithmus, der gerade meinen Tag machen würde. :)
EDIT: Als Antwort auf lassvek, ich bin einige zusätzliche Details bereitstellt:
Tabelle B Elemente sind immer ganz in Tabelle A enthaltenen Elemente nicht nur überlappen.
Wichtig ist, Tabelle B Artikel sind quantisiert, so dass sie entweder vollständig innerhalb oder vollständig außerhalb fallen sollte. Wenn dies nicht der Fall, dann habe ich eine Datenintegrität Fehler, ich muss separat behandeln werden.
Zum Beispiel (ein Kurz verwenden):
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
So mag ich das folgende Verhalten:
- Wenn ich ID 02 aus Tabelle A entfernen oder kürzen, um 14.00 Uhr -. 03.00, soll ich ID 01 aus der Tabelle B entfernen
- Wenn ich verlängern Tabelle A-ID 01, wo es um 1:00 Uhr endet, diese beiden Einträge sollten zusammen in einer Zeile zusammengefügt werden und Tabelle B-ID 01 nun auf Tabelle sollte eine ID 01 Punkt .
- Wenn ich von 8.00 bis 10.00 Uhr entfernen aus Tabelle A-ID 01, sollte dieser den Eintritt in die zwei Einträge aufgeteilt werden: Eine für 7.00 Uhr bis 08.00 Uhr, und einen neuen Eintrag (ID 03) für 10.00 Uhr -11:. 00.00
Lösung
Ich habe ausführlich mit Perioden gearbeitet, aber ich fürchte, ich verstehe nicht ganz, wie Tabelle A und B zusammen arbeiten, vielleicht ist es das Wort subsume , dass ich nicht verstehe.
Können Sie einige konkrete Beispiele für das, was Sie getan werden?
Sie meinen, dass Zeitspanne in Tabelle A aufgezeichnet enthalten Zeitspanne ganz in Tabelle B, wie das?
|---------------- A -------------------|
|--- B ----| |--- B ---|
oder Überlappungen mit?
|---------------- A -------------------|
|--- B ----| |--- B ---|
oder die entgegengesetzte Art und Weise, in Zeitspanne B enthalten / mit A überlappt?
Lassen Sie uns sagen, es ist das erste, wo Zeitspannen in B sind innen / die gleiche wie die verknüpften Zeitspanne in Tabelle A.
Bedeutet dies, dass:
* 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?
Hier ist ein Beispiel:
|-------------- A1 --------------| |-------- A2 --------------|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
und dann verlängern Sie A1 und A2 verkürzen und bewegen, so dass:
|-------------- A1 ---------------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
Dies bedeutet, dass Sie die Daten so ändern mögen:
1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead
, wie etwa diese Modifikation A1 verlängert wird, aber nicht genug B3 vollständig enthalten, und A2 bewegt / verkürzt die gleiche Art und Weise:
|-------------- A1 -----------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
Da B3 ist jetzt nicht vollständig innerhalb entweder A1 oder A2, es entfernen?
Ich brauche einige konkrete Beispiele dafür, was Sie getan werden sollen.
Bearbeiten Mehr Fragen
Ok, was ist:
|------------------ A -----------------------|
|------- B1 -------| |------- B2 ------|
|---| <-- I want to remove this from A
Was ist das?
Entweder:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------| |B3| |--- B2 ---|
oder:
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------|
Um es zusammenzufassen, wie ich es sehe, mit Fragen, so weit:
- Sie möchten die folgenden Operationen auf einem der Lage sein, zu tun
- Shorten
- Lengthen
- kombinieren, wenn sie benachbart sind, die Kombination von zwei oder mehr in eine
- lochen sie durch eine Periode zu entfernen und so spalten sie
- B, die innerhalb einer A nach dem obigen Update noch enthalten sind, erneut verknüpfen, wenn nötig
- B, die enthalten waren, sind aber jetzt völlig außerhalb, löschen
- B, die enthalten waren, sind aber jetzt teilweise außerhalb, Bearbeiten: Löschen Sie diese, ref Datenintegrität
- Für alle obigen Operationen tun, um die am wenigsten Mindest Arbeit notwendig, um die Daten in Einklang zu bringen mit den Operationen (statt nur alles Ziehen und Stecken neu)
Ich werde in C # auf eine Implementierung arbeiten, die funktionieren können, wenn ich von der Arbeit nach Hause komme, werde ich mit mehr später am Abend zurückkommen.
Bearbeiten Hier ist ein Stich an einem Algorithmus.
- Optimieren Sie die neue Liste zuerst (dh. Benachbarten Perioden kombinieren, usw.)
- „merge“ diese Liste mit den Master-Perioden in der Datenbank auf folgende Weise:
- zu verfolgen, wo in beiden Listen (dh. Neue und bestehende) Sie sind
- , wenn die aktuelle neue Periode vollständig vor der aktuellen bestehenden Periode ist, fügen Sie es dann in die nächsten neuen Periode bewegen
- , wenn die aktuelle neue Periode ganz nach der aktuellen bestehenden Periode ist, entfernen Sie die vorhandene Zeit und all untergeordneten Perioden, dann zur nächsten vorhandenen Zeit bewegen
- , wenn die beide überlappen, die aktuelle bestehende Periode einstellen gleich die neue Periode sein, in der folgenden Art und Weise, dann gehen Sie zur nächsten neuen und bestehenden Periode
- , wenn neue Periode beginnt, bevor Zeitraum bestehenden, einfach den Start verschieben
- , wenn neue Periode beginnt nach Zeit bestehenden, prüfen Sie, ob alle untergeordneten Perioden in der Differenz-Zeit sind, und sie erinnern, dann bewegen Sie den Start
- das gleiche mit dem anderen Ende
- mit beliebigen Perioden Sie „erinnern“, ob sie neu gebunden werden muss oder gelöscht
Sie sollten eine massive Menge von Unit-Tests erstellen und stellen Sie sicher, dass Sie alle Kombinationen von Modifikationen abdecken.
Andere Tipps
Ich schlage vor, Sie Ihre Fragen in zwei separate diejenigen entkoppeln: Der erste sollte so etwas wie: „Wie kann ich Grund, sich über die Ressourcenplanung, wenn Sie einen Zeitplan Atom als Ressource mit Startzeit und Endzeit darstellen?“ Hier Adept Vorschlag Intervall Algebra zu verwenden scheint angemessen. Bitte finden Sie unter der Wikipedia-Eintrag 'Interval Graph' und Der Eintrag SUNY Algorithmus Repository auf Scheduling . Die zweite Frage ist eine Datenbank Frage: „Da ein Algorithmus, der Zeitpläne Intervalle und zeigen an, ob zwei Intervalle überlappen oder eine in einem anderen enthalten ist, wie ich diese Informationen verwenden eine Datenbank im angegebenen Schema zu verwalten?“ Ich glaube, dass, sobald der Scheduling-Algorithmus an seinem Platz ist, wird die Datenbank Frage viel einfacher zu lösen. HTH, Yuval
Sie schreiben ist fast in der „zu lange, nur knapp sein Ziel lesen“. Kategorie - Verkürzung es werden Sie wahrscheinlich mehr Feedback geben
Wie auch immer, zum Thema: können Sie versuchen, in ein Ding schau namens „Intervall Algebra“
Wie ich Sie verstehen, können die Benutzer nur direkt Tabelle A. beeinflussen Angenommen, Sie in C # programmieren, können Sie eine einfache ADO.Net DataSet verwenden Modifikationen Tabelle A verwalten Der Table weiß unangetastet Zeilen in Ruhe zu lassen und zu Griff neuen, geänderten und gelöschten Zeilen entsprechend.
Zusätzlich sollten Sie definieren eine Kaskadierung löschen, um automatisch zu entfernen Objekte in Tabelle B entspricht
Der einzige Fall, der nicht auf diese Weise behandelt wird, wenn eine Zeitspanne in Tabelle A verkürzt S. T. es nicht mehr den entsprechenden Datensatz in Tabelle B subsumieren. Sie könnten einfach in einem Update gespeicherte Prozedur für diesen Fall prüfen oder alternativ einen Update-Trigger auf Tabelle A definiert werden.
Es scheint mir, wie jeder Algorithmus für diese einen Pass durch NeuA beinhalten wird, passende ResourceID, Startzeit und EndTime und die Verfolgung von denen Elemente von Olda getroffen zu werden. Dann haben Sie zwei Sätze von nicht passenden Daten, UnmatchedNewA und UnmatchedOldA.
Der einfachste Weg, ich vorgehen denken kann, ist im Grunde mit diesen anfangen: Notieren Sie sich alle UnmatchedNewA an die DB, übertragen Elemente von B aus UnmatchedOldA in New Ein Schlüssel (nur generiert), wo möglich, zu löschen, wenn sie nicht. Dann wischen Sie alle UnmatchedOldA.
Wenn es eine Menge Änderungen sind, ist dies sicherlich kein effizienter Weg, um fortzufahren. In Fällen, in denen die Größe der Daten nicht überwältigend, aber ich ziehe Einfachheit clevere Optimierung.
Es ist unmöglich zu wissen, ob dieser letzte Vorschlag ohne weitere Hintergrund macht keinen Sinn, aber für den unwahrscheinlichen Fall, dass Sie nicht daran gedacht so:
Anstatt die gesamte Eine Sammlung hin und her vorbei, können Sie Ereignis-Listener oder etwas ähnliches aktualisieren das Datenmodell verwenden nur dort, wo Veränderungen notwendig sind? Auf diese Weise wird die Objekte verändert wären in der Lage sein, zu bestimmen, welche DB-Operationen im laufenden Betrieb erforderlich sind.
