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

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

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

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