"Zwischen x und y" Suche

[tabama]

Hallo,
ich habe keinen (bzw. nur einen aufwendigen) Plan, wie ich folgende Aufgabe umsetzen kann:

Es existieren Dokumente mit einem Feld "von" und einem Feld "Bis"
Beispiel:
Dokument   von    bis
1                 23      59
2                 70      70
3                 85      91
Hinweis: Eine Mehrfachnennung/Übereschneidung ist nicht möglich.

Die Aufgabe ist nun, bei Eingabe einer Zahl das Dokument zu finden, welches den Bereich der Zahl beinhaltet. Z.B. sollte "40" das Dokument 1 zurück liefern.

Meine Aufwendige Lösung:
Ich "scanne" die Dokumente alle durch und prüfe bei jeden Dokument, ob die eingegebne Zahl zwischen den zwei Werten liegt. Ich stelle mir nur vor, dass das bei einer größeren Datenmenge nicht gerade performant ist.

Hat jemand einen Ansatz?

[pram]

Hast du mal versucht, was passiert, wenn du die Dokumente in einer Ansicht nach "von" sortierst (Wert numerisch) und mit getDocumentByKey suchst?
ExactMatch sollte dann FALSE sein

Die Hilfe bezieht sich zwar hier auf Strings:
If you specify False (the default) or omit this parameter, a partial match succeeds. A partial match returns the first document that matches the initial characters of the key.

Ich meine mich aber zu erinnern, dass bei Zahlen das nächstbeste gefunden wird.
Über die C-Api geht es bestimmt
http://www-12.lotus.com/ldd/doc/domino_notes/8.5.3/api853ref.nsf/d1891c614adc986885256231005305d5/0021002a007900e6852564cd006e9d65?OpenDocument

Gruß
Roland

[tabama]

Hallo Roland,

hatte ich auch schon dran gedacht, aber das nächste Dokument (in meinem Beispiel die Nr. 2) wäre ja falsch. Den 40 ist ja nicht zwischen 70 und 70.

Mit dem C und API's habe ich (noch) keine Ahnung.

Dennoch Danke schon mal.

[Glombi]

Holzhammer Methode 1 ohne Dokumente anzufassen, daher performanter:

Du kannst eine Ansicht erstellen, die in der ersten Spalte nach <von> und <bis> sortiert ist.
Dann iteriert Du solange mit dem jeweils um 1 inkrementierten Startwert bis Du einen Treffer hast.
In Deinem Beispiel Startwert 40 hättest du den Treffer bei bis = 59.

Problem: Was ist, wenn der Wert nicht vorkommt? Kann ja sein, dass Du nach 92 suchst!
Das müsste man dann intelligent limitieren.


Andreas

[Glombi]

Methode 2:
call db.Search(searchstring, 0, nothing)
anwenden. Das würde ich persönlich vorziehen.

searchstring = |von <= | & startwert & |bis >= | & startwert

[Keydins]

Wie wäre es denn, bei der Anlage der 'von bis' Dokumente ein Feld (Mehrfachwerte) über eine Schleife zu befüllen, so dass alle Werte von-bis enthalten sind und dann die Ansicht mit allen von-bis Dokumenten durchsuchen und prüfen, ob in dem neuen Feld der gesuchte Wert x enthalten ist.


Gruß
Dirk

[Peter Klett]

Wie wäre es denn, bei der Anlage der 'von bis' Dokumente ein Feld (Mehrfachwerte) über eine Schleife zu befüllen, so dass alle Werte von-bis enthalten sind und dann die Ansicht mit allen von-bis Dokumenten durchsuchen und prüfen, ob in dem neuen Feld der gesuchte Wert x enthalten ist.


Gruß
Dirk

Das würde ich lassen. Was passiert bei

von = 1
bis = 1000000

?

Oder es wird nach 23,5 gesucht?

Ich würde eindeutig Glombis Variante 2 bevorzugen ...

[pram]

Alternativ:

Die Zahl von in einen Binärstring umwandeln und in der Ansicht sortieren


00010111 (=23)
01000110 (=70)
01010101 (=85)

Naive Methode: Den zu suchenden Wert ebenfalls nach binär umwandeln und dann erst ein Bit, dann zwei Bit, dann drei usw in den Lookup  (und exactmatch = false) geben, bis kein Treffer mehr erfolgt.
Erfordert bei 8 Bit (0-255) auch 8 Lookups, bei 32 Bit eben 32

Etwas komplizierter:  Intervallschachtelung
Suche nach 40 erfolgt dann wie Folgt:

00101000 (=40)

Step 1: Volle 8 bit suchen, 00101000 => kein Treffer
Step 2: Bitanzahl halbieren, 0010____ => kein Treffer
Step 3: Bitanzahl halbieren, 00______ => Treffer
Step 4: Bitanzahl halbieren aber anhängen, 001_____ => Kein Treffer

Der letzte Treffer ist dann das richtige Dokument

Wenn b die Bitlänge ist, dann sind immer n Schritte erforderlich, wobei sich n wie Folgt berechnet 2^(n-1) = b
Bei 32 Bit, wäre n=6


Weiteres Beispiel: Suche nach 73 = 01001001

Step 1: 01001001 => kein treffer
Step 2: 0100____ => Treffer
Step 3: 010010__ => kein Treffer
Step 4: 01001___ => kein Treffer

Gruß
Roland

[tabama]

Danke!

Methode 2 von Andreas funktioniert wunderbar 

Ich musste es nur ein wenig umbauen, weil der Suchstring nicht nur (wie in meinem Beispiel) aus einem Wert bestand. Es ging mir bei der Frage ja aber darum einen Ansatz zu finden. Denken will ich ja noch selbst

Die Lösung von Roland (Binär) ist ja höchst mathematisch. Solange die o.g. Lösung einigermaßen performant ist, ist diese wesentlich einfacher.

Der Ansatz von Dirk (Mehrfachwerte) hatte ich bereits mal bei einem anderem Problem ausprobiert. Da meckert Notes aber von sich aus schon rum, wenn es zu viele Werte werden.