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=