Schneller Algorithmus für eine Zahl in mehren Bereichen?

[Blup]

Zitat von Uwe Raabe:

Zitat von Blup:

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.

[TigerLilly]

Zitat von Blup:

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.

[jobo]

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.

[mikhal]

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

[Schucki]

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