Heiner KückerDatenstruktur für Datum-/Zeit-abhängige Programme |
|
|
Home Java-Seite Alaska-XBase++-Seite Projekte Philosophien Techniken Konzepte Artikelsystematik Semantisches_Netz Flexible_Columns Weiterentwicklung_Java Fehlerquellen Längencodierung Encoding Programming_by_Contract TimelineStructure Datenstruktur für Kalender oder Terminplaner Sudoku Kontakt / Impressum Links SiteMap Letzte Aktualisierung: 07.05.2005 |
Konzept Optimierung Time-Expression ----------------------------------- Im Newsgroup-Thread de.comp.lang.java Vorschlag Datenstruktur (Kalender) habe ich schon mal über eine Datenstruktur für einen Kalender/Terminplaner nachgedacht. Die Verwendung der Expression-Engine scheint mir die flexibelste Form der Hinterlegung der Termine und Perioden zu sein. Mit der Expression-Engine können Termine oder Zeiträume beliebig auf Jahre, Monate , Tage, Minuten, Sekunden oder Millisekunden-Genauigkeit (Raster) definiert werden. Besonders angenehm sind dabei die zur Verfügung stehenden Literale für Uhrzeit, Datum und Datum-Uhrzeit-Kombination (noch nicht auf Web-Page gestellt). Andere Datenstrukturen mit Merkern für Wochtentage sowie Anfangs- und Endzeiten können nur für eine geringe Anzahl von Terminarten angepasst werden. Mit der Expression-Engine sind exotische Termine wie jeder erste Donnerstag in einem Schaltjahr und so weiter möglich. Zum Vorausplanen der Termine/Perioden oder zur Darstellung in einem Balkendiagramm/Kalender gäbe es die simple/triviale Möglichkeit alle Termine in einer feinen Iteration durchzurechnen. Bei entsprechend vielen und komplexen Expressions, einer feinen Auflösung und einem grossen zu betrachtenden Zeitraum kann es zu einem erheblichen Rechenaufwand kommen. Also muss man die Berechnung von Zeiträumen oder Terminen auf Basis der Expression-Engine optimieren. Dafür biete ich folgende Lösung an: Zur Vereinfachung der Struktur betrachte ich im Zeitraum nur die Zustände 0 und 1 (false und true). Prinzipiell sind Zustände mit einem grösseren Wertebereich bis unendlich (unendlich fein unterteilt) (analoge Werte) denkbar. Das könnten Füllstände für Tanks, Lagerbestände, altersabhängige Zuschläge usw. sein. Ziel ist eine Datenstruktur, welche die Ereignisse/Zustände innerhalb der Zeiträume folgendermassen darstellt: 1 +-----------------+ | | | | 0 -------+ +---------------------+------------- T1 T2 T3 01.04.2005 30.04.2005 01.06.2005 Zeitpunkt | Ereigniss | Bemerkung ----------+-------------+------------------------ Start | 0 | Initialer Zustand T1 | 0 -> 1 | Beginn eines Zeitraumes T2 | 1 -> 0 | Ende eines Zeitraumes T3 | 0 -> 1 -> 0 | Termin / Ereigniss Ende | 0 | End-Zustand Es gibt also eine Tabelle/Liste mit Zeitpunkten und Ereignissen. Obiger Zeitraum liesse sich als ein solcher Ausdruck darstellen (angenommen ein Datumsliteral in der Sprache und Operatoren && (und) sowie || (oder)): ( date >= 01.04.2005 && date <= 30.04.2005 ) || date == 01.06.2005 Der Ausdruck wird nun in elementare Bestandteile zerlegt. Dies wird durch die interne Struktur der Expression-Engine begünstigt. Ein atomarer Teilausdruck enthält nur noch ein einziges Ereigniss. Weiter ist es wichtig, einen begrenzten Zeitbereich zwischen Start und Ende zu betrachten, sonst funktioniert der Algorithmus nicht. date >= 01.04.2005 ------------------ 1 +----------------------------------------------------- | 0 -------+ T1 T2 T3 01.04.2005 30.04.2005 01.06.2005 Zeitpunkt | Ereigniss | Bemerkung ----------+-------------+------------------------ Start | 0 | Initialer Zustand T1 | 0 -> 1 | Beginn eines Zeitraumes Ende | 1 | End-Zustand date <= 30.04.2005 ------------------ 1 -------------------------+ | 0 +----------------------------------- T1 T2 T3 01.04.2005 30.04.2005 01.06.2005 Zeitpunkt | Ereigniss | Bemerkung ----------+-------------+------------------------ Start | 1 | Initialer Zustand T2 | 1 -> 0 | Ende eines Zeitraumes Ende | 0 | End-Zustand date == 01.06.2005 ------------------ 1 | | 0 -----------------------------------------------+------------- T1 T2 T3 01.04.2005 30.04.2005 01.06.2005 Zeitpunkt | Ereigniss | Bemerkung ----------+-------------+------------------------ Start | 0 | Initialer Zustand T3 | 0 -> 1 -> 0 | Termin / Ereigniss Ende | 0 | End-Zustand Die so gewonnenen elementaren Tabellen mit Zeitpunkten/Ereignissen müssen nun entsprechend der Verknüpfung der Teilausdrücke mit UND, ODER, EXCLUSIV-ODER sowie NICHT zu komplexeren Ereignislisten verknüpft (gemergt) werden. date >= 01.04.2005 && date <= 30.04.2005 ------------------------------------------------ 1 +-----------------+ | | 0 -------+ +----------------------------------- T1 T2 T3 01.04.2005 30.04.2005 01.06.2005 Zeitpunkt | Ereigniss | Bemerkung ----------+-------------+------------------------ Start | 0 | Initialer Zustand T1 | 0 -> 1 | Beginn eines Zeitraumes T2 | 1 -> 0 | Ende eines Zeitraumes Ende | 0 | End-Zustand ( date >= 01.04.2005 && date <= 30.04.2005 ) || date == 01.06.2005 -------------------------------------------------------------------------- 1 +-----------------+ | | | | 0 -------+ +---------------------+------------- T1 T2 T3 01.04.2005 30.04.2005 01.06.2005 Zeitpunkt | Ereigniss | Bemerkung ----------+-------------+------------------------ Start | 0 | Initialer Zustand T1 | 0 -> 1 | Beginn eines Zeitraumes T2 | 1 -> 0 | Ende eines Zeitraumes T3 | 0 -> 1 -> 0 | Termin / Ereigniss Ende | 0 | End-Zustand Pseudocode NICHT-Verknüpfung (Negation) einer Ereignis-Tabelle -------------------------------------------------------------- nicht fertig Pseudocode UND-Verknüpfung zweier Ereignis-Tabellen --------------------------------------------------- Die Ereignisse aus beiden Tabellen werden in eine neue nach Zeitpunkt sortierte Tabelle einsortiert, wobei jedes Ereigniss eine Information darüber, ob das jeweilige Ereignis zum linken oder zum rechten Ausdrucks-Operand (zur linken oder rechten Tabelle) gehört, mitführt: -Vermerken zu jedem Ereigniss, ob linker oder rechter Operand -Zusammenfügen der Ereignisse aus beiden Operanden in eine Tabelle -Sortieren der Tabelle nach Datum/Zeit -Startmerker für Anfangs-Zustand links und rechts setzen -Schleife über die Tabelle -Merker für links unf rechts mitschreiben -wenn links und rechts 1 (true), dann Ereigniss mit postStat == 1 in Ergebnis-Tabelle übernehmen -wenn nicht links und rechts 1 (true), dann Ereigniss mit postStat == 0 in Ergebnis-Tabelle übernehmen -Ende Schleife -Zurückgeben Ergebnis-Tabelle Pseudocode ODER-Verknüpfung zweier Ereignis-Tabellen ---------------------------------------------------- nicht fertig Pseudocode ENTWEDER-ODER-Verknüpfung zweier Ereignis-Tabellen ------------------------------------------------------------- nicht fertig Weiteres -------- Es muss neben den oben beschriebenen Ereignissarten noch weitere geben: Zeitpunkt | Ereigniss | Bemerkung | Ausdruck ----------+-------------+-------------------------+------------------------------------ Start | 0 | Initialer Zustand 0 | date > oder >= xx.xx.xxDateLiteral Start | 1 | Initialer Zustand 1 | date < oder <= xx.xx.xxDateLiteral Tx | 0 -> 1 | Beginn eines Zeitraumes | date > oder >= xx.xx.xxDateLiteral Tx | 1 -> 0 | Ende eines Zeitraumes | date < oder <= xx.xx.xxDateLiteral Tx | 0 -> 1 -> 0 | Termin / Ereigniss | date == xx.xx.xxDateLiteral Tx | 1 -> 0 -> 1 | Termin / Ereigniss | date != xx.xx.xxDateLiteral Ende | 0 | End-Zustand 0 | date < oder <= xx.xx.xxDateLiteral Ende | 1 | End-Zustand 1 | date > oder >= xx.xx.xxDateLiteral Sonderfall UND-Verknüpfung zweier Timelines ------------------------------------------- 1--------+ | 0 +----------- 1 +----------- | 0--------+ ergibt 1 0-------------------- Sonderfall ODER-Verknüpfung zweier Timelines -------------------------------------------- 1--------+ | 0 +----------- 1 +----------- | 0--------+ ergibt 1-------------------- 0Für die logischen Verknüpfungen von Timeline-Tabellen (UND, ODER, EXCLUSIV-ODER) nach obigem Datenmodell habe ich ein Beispielprogramm in Java geschrieben. Die baumförmige Analyse einer Expression bis auf elementare zeitliche/temporale Bedingungen ist noch nicht fertig. Download der Quelldateien TimeLineOperations.zip
Achtung: Erweiterungen und Fixes stelle ich ohne Historie
und ohne Ankündigung hier bereit. Lizenzbedingungen:
Die Programme, Quelltexte und Dokumentationen können ohne
irgendwelche Bedingungen kostenlos verwendet werden. |