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 3 von 3     123
Blup

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

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

  Alt 5. Aug 2021, 17:04
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.
  Mit Zitat antworten Zitat
TigerLilly

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

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

  Alt 5. Aug 2021, 20:10
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.
  Mit Zitat antworten Zitat
jobo

Registriert seit: 29. Nov 2010
2.964 Beiträge
 
Delphi 2010 Enterprise
 
#23

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

  Alt 5. Aug 2021, 23:13
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.
Gruß, Jo
  Mit Zitat antworten Zitat
Benutzerbild von mikhal
mikhal

Registriert seit: 11. Sep 2003
Ort: Linz am Rhein
786 Beiträge
 
Delphi 10.3 Rio
 
#24

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

  Alt 6. Aug 2021, 07:17
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
Michael Kraemer
Computer erleichtern die Arbeit...
...und die Erde ist eine Scheibe!
  Mit Zitat antworten Zitat
Schucki

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

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

  Alt 14. Aug 2021, 21:40
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
Frank
  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 +1. Es ist jetzt 00:15 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