Schneller Algorithmus für eine Zahl in mehren Bereichen?

[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.

Zitat von Schucki:

Es gibt über 10.000 mögliche Bereiche

Über die Bandbreite der Bereiche und die Menge der Testzahlen gibt es leider keine Aussagen. Insofern kann man das so nicht beurteilen.

Natürlich lässt sich die Initialisierung noch deutlich beschleunigen, aber erst wenn die gesamte Abfragezeit diese Initialisierungszeit überschreitet, kann sich dieses Verfahren überhaupt erst lohnen.

Ein ähnlicher Ansatz wäre auch, nur die jeweiligen Bereichswechsel in eine Liste zu schreiben und dann binär suchen. Eine solche Liste sähe dann in etwa so aus:

Delphi-Quellcode:

0=
1000=A
1020=A,B
1050=A,B,C
1151=A,B
1161=A
1200=
1510=D
1551=