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 2 von 3     12 3   
TiGü

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

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

  Alt 4. Aug 2021, 12:19
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.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

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

Registriert seit: 7. Aug 2008
Ort: Brandenburg
1.325 Beiträge
 
Delphi 10.4 Sydney
 
#13

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

  Alt 4. Aug 2021, 14:52
Die Ergebnisse sind für das Beispiel falsch.
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
  Mit Zitat antworten Zitat
Blup

Registriert seit: 7. Aug 2008
Ort: Brandenburg
1.325 Beiträge
 
Delphi 10.4 Sydney
 
#14

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

  Alt 4. Aug 2021, 15:29
Ich habe den Vorschlag von himitsu aufgegriffen und ein kleines Testprogramm erstellt.
Angehängte Dateien
Dateityp: zip TestBereiche.zip (407,1 KB, 4x aufgerufen)
  Mit Zitat antworten Zitat
TiGü

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

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

  Alt 4. Aug 2021, 15:38
Die Ergebnisse sind für das Beispiel falsch.
Wurde schon im Beitrag #8 (https://www.delphipraxis.net/1493225-post8.html) erwähnt!
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
900 Beiträge
 
Delphi 10.3 Rio
 
#16

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

  Alt 4. Aug 2021, 16:14
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.
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

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

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

  Alt 4. Aug 2021, 17:20
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)
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
900 Beiträge
 
Delphi 10.3 Rio
 
#18

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

  Alt 4. Aug 2021, 20:01
Ja, das ist auch elegant.
Das wird mit zunehmender Anzahl zu prüfender Zahlen immer schneller.
  Mit Zitat antworten Zitat
Blup

Registriert seit: 7. Aug 2008
Ort: Brandenburg
1.325 Beiträge
 
Delphi 10.4 Sydney
 
#19

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

  Alt 5. Aug 2021, 14:33
Wenn selten die selben Zahlen abgefragt werden, würde der Cache immer größer werden.
Da ist dann so ziemlich die schlechteste Lösung.
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

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

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

  Alt 5. Aug 2021, 15:14
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 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.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
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 +2. Es ist jetzt 21:28 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