Schneller Algorithmus für eine Zahl in mehren Bereichen?

[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).
Verwende hier die Array-Verknüpfungssyntax ab XE7, müsste man für Delphi 2010 noch zurück stricken mit SetLength-Rumgehampel.

Deine Beispielzahlen passen übrigens nicht.

Delphi-Quellcode:

900 NIL
1000 A
1030 A, B
1055 A, B, C
1100 A, C // < --- passt auch in B mit 1020-1160
1155 NIL // < --- passt auch in A (1000-1200) und B (1020-1160) mit 
1500 NIL
1525 D

Delphi-Quellcode:

program Project6;

{$APPTYPE CONSOLE}
{$R *.res}

uses
    System.SysUtils,
    System.Math,
    System.Generics.Collections;

type
    TRange = record
        StartValue: Integer;
        EndValue: Integer;
        RangeName: string;
    end;

    TRanges = TArray<TRange>;

const
    RangeA: TRange = (StartValue: 1000; EndValue: 1200; RangeName: 'A');
    RangeB: TRange = (StartValue: 1020; EndValue: 1160; RangeName: 'B');
    RangeC: TRange = (StartValue: 1050; EndValue: 1150; RangeName: 'C');
    RangeD: TRange = (StartValue: 1510; EndValue: 1550; RangeName: 'D');

    FirstNumber = 0;
    LastNumber = 2000;

    TestNumbers: array[0..7] of Integer = (900, 1000, 1030, 1055, 1100, 1155, 1500, 1525);

procedure Main;
var
    NumberToRangeMap: TDictionary<Integer, TRanges>;
    CurrentRange: TRange;
    CurrentRanges: TRanges;
    I: Integer;
    AllRanges: TRanges;
    JustAText: string;
    LastChar: Integer;
begin
    // Initialisieren, macht man eimal
    AllRanges := [RangeA, RangeB, RangeC, RangeD];
    NumberToRangeMap := TDictionary<Integer, TRanges>.Create;
    try
        for I := FirstNumber to LastNumber do
        begin
            for CurrentRange in AllRanges do
            begin
                if InRange(I, CurrentRange.StartValue, CurrentRange.EndValue) then
                begin
                    NumberToRangeMap.TryGetValue(I, CurrentRanges);
                    CurrentRanges := CurrentRanges + [CurrentRange];
                    NumberToRangeMap.AddOrSetValue(I, CurrentRanges);
                end;
            end;
        end;

        // Nummern Testen mit O(1)
        for I in TestNumbers do
        begin
            if NumberToRangeMap.TryGetValue(I, CurrentRanges) then
            begin
                JustAText := '';
                for CurrentRange in CurrentRanges do
                begin
                    JustAText := JustAText + CurrentRange.RangeName + ', ';
                end;

                LastChar := Length(JustAText) - 1;
                if JustAText[LastChar] = ',' then
                    JustAText[LastChar] := ' ';

                Writeln(I, ' ', JustAText);
            end else
            begin
                Writeln(I, ' NIL');
            end;
        end;
    finally
        NumberToRangeMap.Free;
    end;
end;

begin
    try
        Main;
    except
        on E: Exception do
            Writeln(E.ClassName, ': ', E.Message);
    end;
    Readln;
end.

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

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

[mikhal]

Ich werfe da mal den folgenden Beitrag in die Runde: https://bitemporal.net/generate-bitemporal-intervals/.
Bitte auch den beiden Links folgen, auf die im Text verwiesen wird.

Grüße
Mikhal

[Schucki]

Vielen Dank an alle, die sich diesem Thema angenommen haben.
Ich habe mir die Daten noch einmal genauer angesehen und habe den Weg mit einer Vorindexierung der Daten gewählt und in denen suche ich mit diesem "halben Tabellen Algo". Das geht wirklich flott und kein Vergleich zu früher, wo immer die ganze Datei durchgelaufen wurde.

Danke nochmal, das hat mir alles sehr geholfen!
Gruß Frank