Schneller Algorithmus für eine Zahl in mehren Bereichen?

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

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.

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