Schneller Algorithmus für eine Zahl in mehren Bereichen?

[TiGü]

Zitat von Uwe Raabe:

Zitat von TiGü:

Ich habe das jetzt ganz simpel mit einem TDictionary umgesetzt, so das suchen einer Zahl ein Array mit den Bereichen zurückgibt mit O(1).

Das ist aber nur unter ganz besonderen Bedingungen von Vorteil.
In dem gezeigten Code werden bei der Initialisierung 2001 Zahlen auf alle Ranges geprüft, obwohl am Ende nur 8 Testzahlen abgefragt werden.

Wir kennen ja nicht den konkreten Zahlenraum. Könnte ja auch nur 0 sowie 1000 bis 1550 beinhalten.
In meinen Testfall selber geht das auf den alten Intel Vierkerner hier so schnell, dass ich keine Verzögerung beim Start der Konsolenanwendung bemerke.

Das Initialisieren im echten Anwendungsfall macht man einmal beim Programmstart, ggf. im eigenen Thread und hat das Mapping fertig, bevor der Anwender irgendwas klicken kann, was diese Bereichsabfrage braucht.

Wenn die Zuordnung statisch ist, kann das ja auch als Konfiguration irgendwo liegen (Datenbank, INI, XML, whatever) und nur noch importiert werden.
Wir wissen - wieder mal - zu wenig darüber.

[himitsu]

OK, weil hatten hier viele drüber geredet und bei der Masse hätte man das auch vermuten können,
aber nur weil es nicht so ist, heißt es ja nicht, dass es so bleiben muß? (z.B. Embedded-DB)

Wie schon gesagt, kann man auch die Überlappungen auflösen
und damit wird das Suchen einfacher/schneller, weil sinnvollere Sortierung möglich wird und auch ein optimaler Suchalgo genutzt werden kann.
aus
1000-3000 A
2000-4000 B
wird
1000-1999 A
2000-3000 A B
3001-4000 B

Und wie jemand Anderes schon erwähnte, kommt es auch drauf an, wie oft es gemacht wird.
> einmal laden, die Daten "optimieren" und dann suchen, lohnt wohl nicht, wenn eh nur einmal gesucht wird, weil dann die Verbesserung beim Suchen vermutlich durch Laden+Optimieren wieder aufgehoben wird.

[Blup]

Die Ergebnisse sind für das Beispiel falsch.

Zitat von Schucki:

Beispiel:

...
1000-1200 Bereich A
1020-1160 Bereich B
1050-1150 Bereich C
1510-1550 Bereich D
...

Ergebnis für 8 Beispielzahlen...

900 NIL
1000 A
1030 A, B
1055 A, B, C
1100 A, C
1155 NIL
1500 NIL
1525 D

Die Richtigen Ergebnisse sind:

Code:

1000 - 1019 A
1020 - 1049 A, B
1050 - 1150 A, B, C
1151 - 1160 A, B
1161 - 1200 A
1510 - 1550 D

900 NIL
1000 A
1030 A, B
1055 A, B, C
1100 A, B, C
1155 A, B
1500 NIL
1525 D

[Blup]

Ich habe den Vorschlag von himitsu aufgegriffen und ein kleines Testprogramm erstellt.

[TiGü]

Zitat von Blup:

Die Ergebnisse sind für das Beispiel falsch.

Wurde schon im Beitrag #8 (https://www.delphipraxis.net/1493225-post8.html) erwähnt!

[TigerLilly]

Wenn es wirklich um möglichst schnelles Ermitteln geht:

Mach ein Array mit der Länge aller möglichen Zahlen
MaxZahl=10000;
ElementArray = array [1..MaxZahl] of String;

Ermittle vorab für jedes Elment (=Zahl), welche Intervalle zutreffen. das machst du nur 1x, da ist die Laufzeit egal.
Dann hast du:
...
ElementArray[900]=''
...
ElementArray[1000]='A'
...
ElementArray[1030]='AB'
...
ElementArray[1055]='ABC'
etc.

Wenn du wissen möchtest, welche Intervalle für eine Zahl zutreffen, liest du das aus dem entsprechenden Element des Arrays aus.

[Uwe Raabe]

Zitat von TigerLilly:

Ermittle vorab für jedes Elment (=Zahl), welche Intervalle zutreffen. das machst du nur 1x, da ist die Laufzeit egal.

Alternativ: Initialisiere das Array mit einem Sentinelwert (z.B. '*'). Steht bei Abfrage eines Eintrags der Sentinel drin, ermittele den richtigen Wert und trage den ein. Damit vermeidet man die Berechnung von Einträgen, die niemals gebraucht werden. (Übrigens, der Fachbegriff dafür ist Caching)

[TigerLilly]

Ja, das ist auch elegant.
Das wird mit zunehmender Anzahl zu prüfender Zahlen immer schneller.

[Blup]

Wenn selten die selben Zahlen abgefragt werden, würde der Cache immer größer werden.
Da ist dann so ziemlich die schlechteste Lösung.

[Uwe Raabe]

Zitat von Blup:

Wenn selten die selben Zahlen abgefragt werden, würde der Cache immer größer werden.
Da ist dann so ziemlich die schlechteste Lösung.

Nicht wirklich. Der Cache kann auch nicht größer werden als das anfangs initialisierte Array/Dictionary für alle möglichen Abfragewerte.

Und ob eine Lösung gut oder schlecht, die beste oder auch die schlechteste ist, hängt ganz entscheidend von den konkreten Anforderungen und Rahmenbedingungen ab. Die kennen wir aber noch nicht genau.

So könnte man auch einfach eine TStringList mit dem jeweiligen Ergebnis (z.B. "A,B,C") pro Zeile aus einer Datei laden. Damit eliminiert man die initiale Laufzeit zum Aufbau der Nachschlagetabelle während des Programmstarts und hat trotzdem einen O(1) Zugriff bei der Abfrage.