Schneller Algorithmus für eine Zahl in mehren Bereichen?

[Schucki]

Hallo,

ich stehe vor folgendem Problem.
Ich möchte herausfinden in welche vorgegebenen Bereiche eine beliebige Zahl liegt.
Es gibt über 10.000 mögliche Bereiche und jedes mal alle abzufragen und zu vergleichen würde ich vermeiden wollen. Wie kann ich die Vergleiche auf die Bereiche einschränken die relevant sind?

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

Für jeden Lösungsansatz dankbar,
Gruß Frank

[Delphi.Narium]

Datenbank:

SQL-Code:

select Bereich from bereiche where StartWert >= DenSucheIch and EndeWert <= DenSucheIch

Grob sowas:

Delphi-Quellcode:

var
  sBereiche : String;
  iBereiche : Integer;
begin
  qry.SQL.Text := 'select Bereich from bereiche where StartWert >= :DenSucheIch and EndeWert <= :DenSucheIch';
  qry.ParamByName('DenSucheIch').AsInteger := EineZahl;
  qry.Open;
  iBereiche := qry.RecordCount;
  sBereiche := '';
  while not qry.EoF do begin
    sBereich := Format(', %s',[sBereich,qry.FieldByName('Bereich').AsString]);
    qry.Next;
  end;
  qry.Close;
  sBereich := Copy(sBereich,3,Length(sBereich));
end;

Ist's keine Datenbank, kannst Du auch 'ne Memorytable, ClientDataSet oder sowas nehmen.

Da geht's dann ggfls. statt per Select per Filter:

Delphi-Quellcode:

  MemTable.Filtered := false;
  MemTable.Filer    := Format('StartWert >= %0:d and EndeWert <= %0:d',[EineZahl]);
  MemTable.Filtered := true;
  // WhileNotEoF wie oben

Achso: Alles nur hingedaddelt, keine wirklich schon ausprobierten Routinen, Syntaxfehler also durchaus wahrscheinlich ;-)

Edit: Wie himitsu weiter unten richtig bemerkt ;-)

[TurboMagic]

Wenn die Bereche anhand ihres Minimalwertes sortiert sind, könnte man die
Anzahl der Vergleiche durch intervalschachtelung minimieren. Der Aufwand könnte
dann evtl. Log(n) sein.

Also:
Prüfen, ob die Zahl > als der Minwert des mittleren Bereiches der Liste ist.
Beispiel: 100 Bereiche: Prüfung mit dem 50. Bereich. Falls Zahl < Minwert des
50. Bereiches prüfen ob kleiner Minwert 25. Bereich, falls Zahl > prüfen ob
< Minwert des 75. Bereiches und dann jeweils den neuen "Index Bereich" halboeren
und damit prüfen.

Grüße
TurboMagic

[Andreas13]

Hallo Schucki,
für die Feststellung der Zugehörigkeit eines Elements zu einer Menge verwendet man nach meinem Kenntnisstand binäre Suchbäume. Das gehört zum kleinen Einmaleins der Algorithmentheorie. Alle Fachbücher über Algorithmen behandeln dieses Thema. Du müßtest Dich in diese Thematik einlesen.
Gruß, Andreas

[Schucki]

Vielen Dank für die grobe Richtung!
Das werde ich mir ansehen und weiter verfolgen. :-D

[himitsu]

Bei Delphi.Narium die Vergleiche sind doch falschrum, oder?
Der Startwert muß ja kleiner und nicht größer sein. Und am Ende andersrum.

Und die Bereiche sind (scheinbar überlappend,
da gibt es keine sinnvolle Sortierung für Start+Ende (außer alle Bereiche wären gleich groß, oder eben nicht überlappend)
Was gegen eine "Intervalschachtelung" spricht.
Aber man könnte das Überlappende auflösen, also dafür neue "Bereiche" generieren, wo die jeweiligen "Bereich"-Texte schon zusammenstehen (und diese Bereiche aus den originalen Bereichen entfernen/abschneiden), und schon muß man nur noch einen Eintrag in einer sortieren Liste finden.



Warum die Wertebereiche überhaupt erst runterladen (mehr Daten = langsam) und dann lokal alles durchgehn und vergleichen (langsamer als im DBMS), anstatt es direkt in der DB zu erledigen?
Eventuell mit BETWEEN anstatt der zwei Start-/Endvergleiche.

SQL-Code:

select string_agg(Bereich, ' ') -- oder nur "select Bereich" und dann im Delphi das Concat
from Bereiche 
where :SuchWert between StartWert and EndeWert -- where StartWert <= :SuchWert and :SuchWert <= EndeWert

Und natürlich den/die Index(e) auf StartWert/EndeWert nicht vergessen.

[freimatz]

Wie kommt ihr darauf, dass es um Daten in einer DB geht, wir sind hier doch nicht in "Datenbanken". ;-)
Wenn es performant gehen soll, dann wäre das wichtig zu wissen.
Das überlappende wird es schwer machen. Binäre Suche geht da nicht so ohne weiteres, könnte aber zumindest z.B. für die Untergrenze verwendet werden.

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

[Delphi.Narium]

Zitat:

Zitat von himitsu (Beitrag 1493208)

Bei Delphi.Narium die Vergleiche sind doch falschrum, oder?
Der Startwert muß ja kleiner und nicht größer sein. Und am Ende andersrum.

Hast da wohl recht.

SQL-Code:

select Bereich from bereiche where StartWert <= DenSucheIch and EndeWert >= DenSucheIch

Oder aber auch:

SQL-Code:

select Bereich from bereiche where DenSucheIch Between StartWert and EndeWert

Zitat:

Zitat von freimatz

Wie kommt ihr darauf, dass es um Daten in einer DB geht, wir sind hier doch nicht in "Datenbanken".

Die Frage lautete ja:

Zitat:

Zitat von Schucki

Ich möchte herausfinden in welche vorgegebenen Bereiche eine beliebige Zahl liegt.

Naja, dass ist genau genug, um nicht zu wissen, um was es genau geht ;-)

Es schließt eine Datenbank nicht zwingend aus ;-) Deshalb ja der Hinweis auf MemoryTable ..., ist dann keine Datenbank aber fast sowas wie eine Datenbank ;-)

Der Filter dort müsste (wegen himitsus Hinweis) dann eher so aussehen:

Delphi-Quellcode:

 
  MemTable.Filtered := false;
  MemTable.Filer := Format('StartWert <= %0:d and EndeWert >= %0:d',[EineZahl]);
  MemTable.Filtered := true;

Und der andere Vorschlag von mir könnte dann eher in diese Richtung gehen:

Delphi-Quellcode:

var
  sBereiche : String;
  iBereiche : Integer;
begin
  qry.SQL.Text := 'select Bereich from bereiche where :DenSucheIch Between StartWert and EndeWert';
  qry.ParamByName('DenSucheIch').AsInteger := EineZahl;
  qry.Open;
  iBereiche := qry.RecordCount;
  sBereiche := '';
  while not qry.EoF do begin
    sBereich := Format(', %s',[sBereich,qry.FieldByName('Bereich').AsString]);
    qry.Next;
  end;
  qry.Close;
  sBereich := Copy(sBereich,3,Length(sBereich));
end;

[Uwe Raabe]

Zitat:

Zitat von TiGü (Beitrag 1493225)

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:

Zitat von Schucki (Beitrag 1493179)

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:

Zitat von Uwe Raabe (Beitrag 1493230)

Zitat:

Zitat von TiGü (Beitrag 1493225)

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:

Zitat von Schucki (Beitrag 1493179)

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:

Zitat von Blup (Beitrag 1493242)

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:

Zitat von TigerLilly (Beitrag 1493249)

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:

Zitat von Blup (Beitrag 1493292)

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

Delphi-Quellcode:

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.

[Blup]

Zitat:

Zitat von Uwe Raabe (Beitrag 1493293)

Zitat:

Zitat von Blup (Beitrag 1493292)

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.

Deshalb halte ich auch den Vorschlag von TigerLilly für nicht so sinnvoll, wenn der Zahlenbereich sehr groß ist oder gar Kommazahlen oder Zeitstempel enthält. Bei der Abfrage ist das zwar die schnellste Lösung, aber nur wenn das Ergebnis bereits vorab ermittelt wurde. Genau das wollte der TE aber optimieren. Die Bildung einer Liste von Intervallen ist auch nicht aufwendiger und bei der Abfrage fast genauso schnell. Es wird weniger Speicher benötigt, was den Cache entlastet und so auch zur Geschwindigkeit beiträgt. Aber die "Richtige Lösung" gibt es nicht.

[TigerLilly]

Zitat:

Zitat von Blup (Beitrag 1493310)

Deshalb halte ich auch den Vorschlag von TigerLilly für nicht so sinnvoll

Dem würde ich gern widersprechen. Tabellen vorzuberechnen ist eine gebräuchliche Technik. Und was die Schnelligkeit des Ergebnisses anbelangt, wirst du nichts schnellers finden. Da der TE keine weiteren Infos gegeben hat, die dem widersprechen, würde ich meinen Vorschlag in diesem Rahmen gern als "höchst sinnvoll" raten. :-D

[jobo]

Das erzeugt 10000 Datensätze (Bereiche) in Postgres und findet eine zufällige Zahl darin. Es dauert ca 50 ms.

Code:

select r_search, int4range(r_low,r_high ) as r_range, upper(substr(md5(random()::text), 0, 6))as r_name  from (
  select r_search, r_low, (r_low+random()*r_dist_max)::int4 as r_high from (
    select r_search, p.r_min, (p.r_min+random()*r_max)::int4 as r_low, r_dist_max
      from pg_catalog.generate_series(1, 10000, 1),   -- Anzahl generierter Datensätze
           (select (random()*10000+9999)::int4 as r_min, 
                   1000000 as r_max, 
                   1000 as r_dist_max, 
                   (random()*1000000)::int as r_search 
           )p      -- Parameter
    ) x         -- aufbereitete Zufallswerte
) r          -- weiter aufbereitete Zufallswerte
 where r_search <@ int4range(r_low,r_high )

Nimmt man das Select ohne Where Clause und füllt die Daten in eine Tabelle, ist die Abfrage auf eine Zahl mindestens doppelt so schnell. Man kann das Statement unter https://dbfiddle.uk ausprobieren, wenn kein Postgres installiert ist.

Code:

create table rangetest (r_range int4range , r_name varchar(5));

Die reine Abfrage bei vorhandener Tabelle <rangetest> lautet dann:

Code:

select * from rangetest 
 where (random()*1000000)::int <@ r_range

Hier sind noch keine Indizierungen im Spiel, nur der spezielle Range Datentyp von Postgres. Ohne den, also mit einer beliebigen DB und 2 Spalten für den Range, wäre die Geschwindigkeit vermutlich ähnlich.

Mit geänderten Parametern kann man den Test variieren. Momentan sind sie grob zurecht geschoben, um sichtbare Ergebnisse zu erhalten. Die Frage ist, unter welchen Bedingungen sich ein aufwändiger Algorithmus lohnt.

[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