Wert aus Tabelle finden

[Bane (Gast)]

Hallo,

ich habe eine Tabelle die folgendermaßen aussieht:

1        0
2        710
5  1648
10  2358
256  5678
1024  7098
1224  7281
1424  7435
1624  7570
1824  7689
2024  7796
2224  7892
2424  7980
2624  8061
2824  8137
3024  8207
3224  8272
3424  8334
...      ...

Der linke Tabellenwert hat einen Maximalwert von 16834.
Ich habe nun einen vorgegebenen Wert von z.B. 2400, und brauche
um die passende Zahl dafür zu interpolieren den nächstgrößeren und
nächstkleineren Tabellenwert.
Kann mir jemand sagen, wie ich diese Werte mit kleinstmöglichem
Rechenaufwand bekommen kann, da durch die Benutzung eines C166
die Leistung relativ eingeschränkt ist, und diese Rechenoperation
zyklisch alle 300ms ausgeführt wird.
Die Programmierung erfolgt in C, und es können keine Fließkommaoperation
verwendet werden. Die linken Tabellenwerte können frei verändert werden,
müßen nur den Raum zwischen 0 und 16384 abdecken.

Danke schonmal für eure Hilfe

[Karl H. (kbuchegg)]

> Kann mir jemand sagen, wie ich diese Werte mit kleinstmöglichem
> Rechenaufwand bekommen kann

Da deine Tabelle nach der linken Spalte sortiert ist, kannst
du 'binäres Suchen' benutzen.

Google bringt dich mit diesem Stichwort sicher weiter.

[Karl H. (kbuchegg)]

Aber ich seh grade, dass deine Index-Spalte ja
schöne Zahlenwerte aufweist.

Du hast 6 'Bereiche'

 * 1
 * 2
 * 5
 * 10
 * 256
 * 1024 und alles darüber.

Der springende Punkt ist, dass der 6. Bereich (1024 und alles
darüber) in 200-er Schritten geht. Also kann man aus dem Wert
die Arrayposition ausrechnen.

  if( SuchWert < 2 ) {
    Kleiner = Tabelle[0];
    Groesser = Tabelle[1];

  else if( SuchWert < 5 ) {
    Kleiner = Tabelle[1];
    Groesser = Tabelle[2];
  }

  else if( SuchWert < 10 ) {
    Kleiner = Tabelle[2];
    Groesser = Tabelle[3];
  }

  else if( SuchWert < 256 ) {
    Kleiner = Tabelle[3];
    Groesser = Tabelle[4];
  }

  else if( SuchWert < 1024 ) {
    Kleiner = Tabelle[4];
    Groesser = Tabelle[5];
  }

  else {
    Index = 5 + ( SuchWert - 1024 ) / 200;
    Kleiner = Tabelle[Index];
    Groesser = Tabelle[Index+1];
  }

Geht natürlich nur, wenn sich die linke Spalte in deiner
Tabelle nicht ändert. Wenn die variabel ist -> binäres Suchen

[Kai S. (Firma: ZeuSWarE GmbH) (zeusosc)]

Hi,
Ich denke mal das die beiden assoziativ miteinander sind, d.h.
der linke ist eine art Index,..

Dann währe es in drei schritten machbar:

erstens:

packe in ein array alle werte die Kleiner als dein Referenzwert sind, 
und die die größer sind in ein seperates array,..

zweitens:
Suche den größten wert aus array1
drittens:
Suche den kleinsten wert aus array2

grüüße

[Bane (Gast)]

Nur noch als zusätzliche Info:

rechte Spalte = ln(linke Spalte)*1024

Kann daher die Werte der rechten Spalte frei variieren,  falls dies die 
Sache vereinfachen würde. Muss damit nur den Wertebereich zwischen 0 und 
16384 abdecken können.

[Karl H. (kbuchegg)]

Beim erneuten Lesen der Fragestellung
habe ich das hier gefunden

> Die linken Tabellenwerte können frei verändert werden,
> müßen nur den Raum zwischen 0 und 16384 abdecken.

Dann mach die linken Tabellenwerte in einem fixen Raster
und du kannst dir ganz einfach ausrchnen, wo denn der
nächst kleinere Wert in der Tabelle zu finden ist.
Wenn du dann noch die Schrittweite als 2-er Potenz
ansiedelt, dann brauchst das noch nicht mal eine
Division sondern der Compiler kann die Division durch
eine Schiebeoperation wegoptimieren.

[Bane (Gast)]

Ist es dann besser, das ganze auf 2 Tabelle aufzuteilen?
Eine Tabelle für die Werte von 0 - 1024, und eine zweite von 1024 - 
16384?
Da es sich ja um inen logarithmus handelt ändern sich die Werte im 
unteren Zahlenbereich noch sehr schnell, hier muss dann also auch eine 
kleinere Schrittweite gewählt werden.

[Kai S. (Firma: ZeuSWarE GmbH) (zeusosc)]

Also du möchtest irgendetwas interpolieren,..
Ausgangspunkt ist die linke spalte, die rechte ist eindeutig bestimmt 
durch:

$$y_{rechts}:=\ln{x_{links}}\cdot 1024$$

Da der Log.nat. monoton steigend ist, und die zuordnung bijektiv ist, 
folgt das du also NUR die epsilon-Umgebung eines deiner linken werte 
brauchst, (delta umgebung folgt ja, durch folgenstetigkeit, mit folge 
aus gerundeten ln werten).

Also sortiere wie oben erwähnt deine linke spalte, dann hast du den 
nächst größeren und den nächst kleineren wert,..
aus den drei berechnest du dann die rechten spaltenwerte und wenn du 
darauffolgend magst interpolierst du das ganze,..


grüüüße

[Karl H. (kbuchegg)]

Bane wrote:
> Ist es dann besser, das ganze auf 2 Tabelle aufzuteilen?
> Eine Tabelle für die Werte von 0 - 1024, und eine zweite von 1024 -
> 16384?
> Da es sich ja um inen logarithmus handelt ändern sich die Werte im
> unteren Zahlenbereich noch sehr schnell, hier muss dann also auch eine
> kleinere Schrittweite gewählt werden.

Könnte man machen.
Muss man aber nicht. Wenn man weiss dass ab 1024 eine
andere Schrittweite gewählt wurde, kann man das ja
berücksichtigen. Das 'if' ist schon erfunden.

[Bane (Gast)]

Danke Karl Heinz,

die erste methode mit den if und den elsif war die beste, welche am 
schnellsten zum Ergebnis kam......also nochmal danke!!