Algorithmus zum Auffinden von Datumsbereichen innerhalb von Dokumenten

[ghostmw]

Guten Morgen zusammen,

ich bin gestern auf eine Aufgabe gestossen, die mir Kopfzerbrechen macht.

Ich habe Notesdokumente, die ein Startdatum mit Uhrzeit (Feld StartDateTime) und eine Enddatum haben (Feld EndDateTime) und einen Resourcennamen (Fahrzeug oder Raum), also wenn man so will ein kleines Buchungssystem.

Es wird aber NICHT die Resourcen-Datenbank benutzt, sondern was eigenes.

So nun zur eigentlichen Herausforderung:

Wie bekomme ich es performant hin, zu suchen, welche Fahrzeuge bzw. welcher Raum ist für den Zeitraum von xx.xx.xxxx xx:xx:xx Uhr bis yy.yy.yyyy yy:yy:yy Uhr verfügbar?

Ich gehe von einer Datenbank mit 25.000 (später auch mehr) solcher Buchungsdokumente aus, verteilt auf beliebig viele verschiedene Zeiträume.

Ich habe mal gegoogelt und verschiedene allgemeinere Suchalgorithmen (binäre Suche und interpolationssuche) gestossen, die aber beide nur feste Ziele suchen (also auf Gleichheit prüfen), aber keine Zeiträume suchen.

Letzteren Algorithmus habe ich dann entsprechend angepasst, so dass ich den Anfangspunkt und Endpunkt innerhalb einer entsprechend sortieren Notesview finde.

Das klappt aber nur solange die Buchungsdokumente immer am selben Tag anfangen und aufhören. Mehrtägige Dinge klappen damit leider nicht.

Ich pack mal den Algorithmus rein ... aber bitte nicht verwirren lassen.

Funktion BinSearchLeft

Function binSearchLeft ( vecCollection As NotesViewEntryCollection, varBorder As Variant ) As Long
   Dim varTemp As Variant
   Dim lngLeft As Long
   Dim lngRight As Long
   Dim lngMiddle As Long
   Dim veEntry As NotesViewEntry
   Dim varLeftValue As Variant
   Dim varMiddleValue As Variant
   Dim varRightValue As Variant
   Dim dblDiff As Double, dblDiff2 As Double
   
   binSearchLeft = -1
   If vecCollection Is Nothing Then
      Exit Function
   Else
      If vecCollection.Count = 0 Then Exit Function
   End If
   
   lngLeft = 1
   lngRight = vecCollection.Count
   
   Set veEntry = vecCollection.getFirstEntry
   
   varTemp = veEntry.ColumnValues(2)
   If Isarray ( varTemp ) Then varTemp = varTemp (0)
   
   varLeftValue = Cdat ( varTemp )
   Set veEntry = vecCollection.GetLastEntry
   
   varTemp = veEntry.ColumnValues(2)
   If Isarray ( varTemp ) Then varTemp = varTemp (0)
   varRightValue =Cdat ( varTemp )
   
   dblDiff = ( varBorder - varLeftValue)
   dblDiff2 = ( varRightValue - varLeftValue )
   
   lngMiddle = lngLeft + Clng ( dblDiff * ( lngRight - lngLeft ) / dblDiff2 )
   If lngMiddle < lngLeft Then
      binSearchLeft = lngLeft
      Exit Function
   End If
   
   If lngMiddle > lngRight Then
      binSearchLeft = lngRight
      Exit Function
   End If
   
   Set veEntry = vecCollection.GetNthEntry ( lngMiddle )   
   varTemp = veEntry.ColumnValues(2)
   If Isarray ( varTemp ) Then varTemp = varTemp (0)
   
   varMiddleValue = Cdat ( varTemp )
   
   While ( varMiddleValue < varBorder And lngRight > lngLeft )
      If ( varBorder < varMiddleValue ) Then
         lngRight = lngMiddle - 1
      Else
         lngLeft = lngMiddle + 1
      End If
      lngMiddle = lngLeft + ( ( varBorder - varLeftValue) * ( lngRight - lngLeft ) / ( varRightValue - varLeftValue ) )
      Set veEntry = vecCollection.GetNthEntry ( lngMiddle )   
      
      varTemp = veEntry.ColumnValues(2)
      If Isarray ( varTemp ) Then varTemp = varTemp (0)
      
      varMiddleValue = Cdat ( varTemp )
   Wend
   
   If varMiddleValue >= varBorder Then
      binSearchLeft = lngMiddle + 1
   End If
End Function

Funktion BinSearchRight

Function binSearchRight ( vecCollection As NotesViewEntryCollection, varBorder As Variant ) As Long
   Dim varTemp As Variant
   Dim lngLeft As Long
   Dim lngRight As Long
   Dim lngMiddle As Long
   Dim veEntry As NotesViewEntry
   Dim varLeftValue As Variant
   Dim varMiddleValue As Variant
   Dim varRightValue As Variant
   Dim dblDiff As Double, dblDiff2 As Double
   
   binSearchRight = -1
   If vecCollection Is Nothing Then
      Exit Function
   Else
      If vecCollection.Count = 0 Then Exit Function
   End If
   
   lngLeft = 1
   lngRight = vecCollection.Count
   
   Set veEntry = vecCollection.getFirstEntry
   varTemp = veEntry.ColumnValues(2)
   If Isarray ( varTemp ) Then varTemp = varTemp (0)
   varLeftValue = Cdat ( varTemp )
   
   Set veEntry = vecCollection.getLastEntry
   varTemp = veEntry.ColumnValues(2)
   If Isarray ( varTemp ) Then varTemp = varTemp (0)
   varRightValue =Cdat ( varTemp )
   
   dblDiff = ( varBorder - varLeftValue)
   dblDiff2 = ( varRightValue - varLeftValue )
   
   lngMiddle = lngLeft + Clng ( dblDiff * ( lngRight - lngLeft ) / dblDiff2 )
   If lngMiddle < lngLeft Then
      binSearchRight = lngLeft
      Exit Function
   End If
   
   If lngMiddle > lngRight Then
      binSearchRight = lngRight
      Exit Function
   End If
   
   Set veEntry = vecCollection.GetNthEntry ( lngMiddle )   
   varTemp = veEntry.ColumnValues(2)
   If Isarray ( varTemp ) Then varTemp = varTemp (0)
   
   varMiddleValue = Cdat ( varTemp )
   
   While ( varMiddleValue <> varBorder And lngRight > lngLeft )
      If ( varBorder < varMiddleValue ) Then
         lngRight = lngMiddle - 1
      Else
         lngLeft = lngMiddle + 1
      End If
      lngMiddle = lngLeft + ( ( varBorder - varLeftValue) * ( lngRight - lngLeft ) / ( varRightValue - varLeftValue ) )
      Set veEntry = vecCollection.GetNthEntry ( lngMiddle )   
      
      varTemp = veEntry.ColumnValues(2)
      If Isarray ( varTemp ) Then varTemp = varTemp (0)
      
      varMiddleValue = Cdat ( varTemp )
   Wend
   
   If varMiddleValue >= varBorder Then
      binSearchRight = lngMiddle -1
   End If
End Function

Der Aufruf ist dann folgender:

Sub Initialize
   Dim session As New NotesSession
   Dim dbCurrent As NotesDatabase
   Dim viwLookUp As NotesView
   Dim vecTemp As NotesViewEntryCollection
   Dim veTemp As NotesViewEntry
   Dim nvNav As NotesRichTextNavigator
   Dim lngLeft As Long
   Dim lngRight As Long
   
   Set dbCurrent = session.CurrentDatabase
   Set viwLookUp = dbCurrent.GetView ( "LookUpView" )
   Call viwLookUp.Refresh
   viwLookUp.AutoUpdate = False
   
   Set vecTemp = viwLookUp.GetAllEntriesByKey( Split ( "Standort:KFZ-Typ" , ":" ), True )
   
   lngLeft = binSearchLeft ( vecTemp, Cdat ( "6.6.2011 8:00:00" ) )
   lngRight = binSearchRight ( vecTemp, Cdat ( "9.6.2011 20:00:00" ) )
   
   Msgbox "Links = " + Cstr ( lngLeft ) + " und Rechts = " + Cstr ( lngRight )
   
   If lngLeft > 0 Then
      Set veTemp = vecTemp.GetNthEntry ( lngLeft )
      Print "Left = " + Cstr ( veTemp.ColumnValues(4) )
   End If
   
   If lngRight > 0 Then
      Set veTemp = vecTemp.GetNthEntry ( lngRight )
      Print "Right = " + Cstr ( veTemp.ColumnValues(4) )
   End If
   
End Sub

Die LookUp-View beinhaltet folgende Spalten:

1. Standort (Feldinhalt sortiert)
2. Fahrzeugtyp (Feldinhaltsortiert)
3. Datumsbereich (Formel *1 => sortiert)
4. KFZ-Kennzeichen (Feldinhalt)

*1: Formel für die Spalte Datumsbereich

range := "[" + @Text ( StartDateTime )  + " - " + @Text (  EndDateTime )  + "]" ;
values := @TextToTime ( @Explode (@Eval ( range ) ) );

val1 := @TimeMerge ( values[1] ; StartDateTime );
val2 := @If ( @Elements ( values ) > 1 ;  @TimeMerge ( values [ @Elements ( values ) ] ; EndDateTime ); @TimeMerge ( values[1] ; EndDateTime ) );
val3 := @If ( @Elements ( values ) > 2 ; @Subset ( @Subset ( values;  @Elements ( values ) - 1 ); 2 - @Elements ( values ) );  "" );

@If ( @Elements ( val2) > 0 & @Elements ( val3 ) > 0 ; val1 : val3 : val2 ; @Elements ( val2) > 0 ; val1 : val2 ; val1 )

Daraus folgt dann eine Datumsliste mit folgenden Angaben:
- Startdatum mit Uhrzeit
- Daten zwischen Startdatum und Enddatum als Mehrfach-Datumsliste ohne Datum
- Enddatum mit Uhrzeit

z.B. [1.1.2011 8:00:00] : [2.1.2011] : [3.1.2011] : [4.1.2011] : [5.1.2011] : [6.1.2011] : [7.1.2011] : [8.1.2011] : [9.1.2011] : [10.1.2011 20:00:00]
oder [1.1.2011 8:00:00] : [1.1.2011 19:00:00]

Damit kann ich alles was eintägige Reservierungen ist, ermitteln, nur die mehrtägigen Einträge fallen durchs Raster der "Fahndung".

Ich weiß, es ist viel zum Lesen, aber kennt jemand einen Weg, der eine performante Suche verspricht.

Das Abklappern der Ansicht komplett von A bis Z dauert zu lange, bei Suche eines eintägigen Datumsbereichs ca. 7 sek, bei einem mehrtägigen Datumsbereichs ca. 30 sek.
Auch ein DB-Search für die Ermittlung dauert ungefähr genau solange, ein Ermitteln der Notesdokumente bzw. Notesviewentries für einen bestimmten / mehrere Tag braucht auch solange.
Es muss doch etwas performanteres geben, oder nicht ?

Deswegen bin ich den Weg mit der Interpolationssuche gegangen, vielleicht muss ich auch nur die Suchansicht umbauen.

Danke für die Hilfe.

[Tode]

Nun, ich denke aus Gründen der Performance hat IBM die busytime aufgebaut... Denn Du findest ja bei einer Suche immer die NICHT verfügbaren Räume und musst diese dann quasi "abziehen"... Eine Suche nach "Verfügbar" wäre nur mit "Freie- Zeit- Dokumente" realisierbar.

Trotzdem man ein Ansatz, wie ich Ihn verwenden würde:

Die Such- Ansicht enthält alle Reservierungen, Kategorisiert nach Datum. Das Datum berechnet sich aus einer Formel, die so aussieht (entnommen aus Deinem Beispiel oben):

Code

range := "[" + @Text ( StartDateTime )  + " - " + @Text (  EndDateTime )  + "]" ;
values := @TextToTime ( @Explode ( range ) );
values

natürlich optimalerweise im Dokument berechnet, wegen Performance der Ansicht...
In der zweiten Spalte wäre dann der ResourcenName + "~" + @Text( @DocumentUniqueID).

Nun machst Du mit den Datumswerten aus Deinem aktuellen Dokument (gebildet über die gleiche Formel) 1-n Lookups, deren Ergebnisse Du kummulierst.
Wenn Du vorher eine Liste der möglichen Ressourcen zusammengestellt hast, dann hast Du nachher zwei Listen:

1. Resourcen, die auf jeden Fall frei sind: Das sind die, die in der Resourcenliste vorkommen, aber nicht im Lookup
Sehr gut...

2. Resourcen, die möglicherweise belegt sind...
Über die Unids (das sollten jetzt nicht mehr so viele sein) durchläufst Du die Dokumente und prüfst ob

StartDateTime < MyStartDateTime < EndDateTime ODER StartDateTime < MyEndDateTime < EndDateTime ODER (MyStartDateTime < StartDateTime UND MyEndDateTime > EndDateTime )

Ich würde das ganze als Liste einer Klasse mit Resourcenname als Schlüssel aufbauen:

myResourceListe( "Resource1" ).UNIDs = UNID1 : UNID2 : UNID3

Dann kannst Du das Bearbeiten einer UNID- Liste abbrechen, sobald eines der Dokumente in der gewünschten Zeit liegt (weil dann ist die Resource ja nicht verfügbar).

Rein Theoretisch geht das sogar alles in Formelsprache und müsste recht performant sein (@GetDocField( UNID ; "StartDateTime" ), aber eventuell musst Du doch auf Script zurückgreifen.

[ghostmw]

Hi Tode,

klingt schon mal gut ... ich habe nur ein wenig Bauchschmerzen, was das Berechnen des Zeitraums mit der Formel anbelangt.

Weil ... Kunden sind unberechenbar, die buchen z.B. ein Auto für 1 Jahr, damit man es nicht buchen kann.

Macht dann 365 Einträge in dem Feld für die Ansicht, könnte das ein 16k bzw. 32k Problem geben.

Werde das mal ausprobieren, wenn ich wieder Zeit finde.

Danke Tode für den Tip...