AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Schneller Algorithmus für eine Zahl in mehren Bereichen?

Schneller Algorithmus für eine Zahl in mehren Bereichen?

Ein Thema von Schucki · begonnen am 3. Aug 2021 · letzter Beitrag vom 14. Aug 2021
Antwort Antwort
Seite 1 von 3  1 23   
Schucki

Registriert seit: 17. Jul 2004
146 Beiträge
 
Delphi 2010 Architect
 
#1

Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 3. Aug 2021, 17:26
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
Frank
  Mit Zitat antworten Zitat
Delphi.Narium

Registriert seit: 27. Nov 2017
1.918 Beiträge
 
Delphi 7 Professional
 
#2

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 3. Aug 2021, 17:54
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

Geändert von Delphi.Narium ( 4. Aug 2021 um 10:57 Uhr) Grund: Schreibfehler ...
  Mit Zitat antworten Zitat
TurboMagic

Registriert seit: 28. Feb 2016
Ort: Nordost Baden-Württemberg
1.708 Beiträge
 
Delphi 10.3 Rio
 
#3

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 3. Aug 2021, 20:32
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
  Mit Zitat antworten Zitat
Andreas13

Registriert seit: 14. Okt 2006
Ort: Nürnberg
440 Beiträge
 
Delphi XE5 Professional
 
#4

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 3. Aug 2021, 20:36
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
Wenn man seinem Nächsten einen steilen Berg hinaufhilft, kommt man selbst dem Gipfel näher.
John C. Cornelius

Geändert von Andreas13 ( 3. Aug 2021 um 21:26 Uhr)
  Mit Zitat antworten Zitat
Schucki

Registriert seit: 17. Jul 2004
146 Beiträge
 
Delphi 2010 Architect
 
#5

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 3. Aug 2021, 23:43
Vielen Dank für die grobe Richtung!
Das werde ich mir ansehen und weiter verfolgen.
Frank
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
38.731 Beiträge
 
Delphi 10.4 Sydney
 
#6

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 4. Aug 2021, 00:17
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.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014

Geändert von himitsu ( 4. Aug 2021 um 00:35 Uhr)
  Mit Zitat antworten Zitat
freimatz

Registriert seit: 20. Mai 2010
1.032 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#7

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 4. Aug 2021, 08:45
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.
  Mit Zitat antworten Zitat
TiGü

Registriert seit: 6. Apr 2011
Ort: Berlin
2.835 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#8

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 4. Aug 2021, 10:01
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.

Geändert von TiGü ( 4. Aug 2021 um 10:05 Uhr)
  Mit Zitat antworten Zitat
Delphi.Narium

Registriert seit: 27. Nov 2017
1.918 Beiträge
 
Delphi 7 Professional
 
#9

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 4. Aug 2021, 10:55
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.
select Bereich from bereiche where StartWert <= DenSucheIch and EndeWert >= DenSucheIch

Oder aber auch:
select Bereich from bereiche where DenSucheIch Between StartWert and EndeWert
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 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;
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
8.819 Beiträge
 
Delphi 10.4 Sydney
 
#10

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 4. Aug 2021, 11:54
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.

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=
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 04:00 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf