Hallo zusammen Ich habe einen Wert x und möchte daraus den Index in einer Datentabelle berechnen. Zwischen dem Wert x und dem Arrayindex besteht allerdings kein linearer Zusammenhang (siehe Bild). Das positive ist aber, dass die Kurvenform keine grosse Rolle spielt. Es besteht höchstenfalls die Notwendigkeit, dass die Indizesse am Anfang rascher wechseln als jene bei grösseren x-Werten. Die Berechnung läuft in einer Schleife, der vorheriger Wert Index_n liesse sich problemlos zwischenspeichern. Aktuelle Lösungen: - Diese Kurve gleicht z.B. einer Wurzelfunktion oder einer e-Funktion. Letztere liesse sich durch eine Näherung abbilden. Man könnte vielleicht auch mir einer zweiten Tabelle arbeiten:) - Man könnte auch eine grössere Tabelle verwenden (Problem, grosser Speicherbedarf) Interessieren würde mich wie ihr so eine Berechnung durchführen würdet. Beste Grüsse Geri ..letzlich geht es mir darum, an Anfang die Empfindlichkeit zu erhöhen.
Ein guter Kompromiss zwischen Rechenlast und Speicherverbrauch wäre eine Tabelle mit wenigen Stützstellen und eine lineare Interpolation dazwischen.
@ Gerhard Burger (geri) >Ich habe einen Wert x und möchte daraus den Index in einer Datentabelle >berechnen. Mann könnte die Tabelle erweitern und jweiels den zugehörigen Wert X abspeichern. Sind dann halt 512x4 Bytes mehr. Hmm. Daraus kann man dann per Teile undhersche schnell den zugehörigen Einrag finden. Wozu soll das denn gut sein und wie oft muss die Funktion berechnet werden? MFg Falk
Der f = log2(x) laesst sich auch recht einfach annaehern: 1. Hoechstes gesetztes Bit in x bestimmen 2. Ergebnis f = 2^a * #Bitnummer (a so waehlen, dass du den gewuenschten Wertebereich bekommst) 3. Je nach geforderter Genauigkeit kannst du jetzt schon linear approximieren: Die niedrigeren Stellen in f werden mit den naechstniedrigeren Bits aus x aufgefuellt.
Hallo Rolf Vielen Dank für Deinen Tipp! Diese Lösung habe ich auch schon in Erwägung gezogen. Entschuldige bitte, dass sie oben nicht genannt wurde. Danach ergäbe sich ja der Index dann ja aus (für die im Beispiel genannte Grafik) Xn= x * 512/300000 mit y= k * x + d k = (Yn+1 - Yn-1) / (Xn +1 - Xn-1); d = (Yn-1 * xn+1 - Yn+1 * Xn-1) / (Xn+1 - Xn-1); Index = k * Xn + d; Dieses Verfahren habe ich ausgeschlossen weil mir der Rechenaufwand etwas gross erscheint. ... aber vielleicht würdest du die Berechnung viel effizieter gestalten wie ich ... Die Schleife muss bei diesem Beispiel 300.000 mal durchlaufen werden Beste Grüsse Geri
Hallo Jan Auch eine sehr interessnte Lösung, vielen Dank! Wenn ich Deine Überlegungen richtig interpretiere, würde die Indexberechnung dann in etwas so aussehen? Schritt 1: Höchstes Bit in x bestimmen: Mask = 0x80000000; Approx = 0xFFFFFFFF; for (i=31; i>=0; i--) { if (x & Mask) != 0) break; Mask = Mask >> 1; Approx = Approx >> 1; // für Schritt 3 } in i steht nun der Index Schritt 2: Index f berechnen f = Faktor * i; // Faktor = 2 ^a ?? Schtritt 3: Erhöhung der Genauigkei durch lineare Approximation f = f | Approx; // ??? Habe ich das so bitte richtig verstanden? Wieso sollte der Bereich in 2^a passen? Ergibt sich daduch noch eine deutliche Vereinfachung? Beste Grüsse Geri
Die Multiplikation mit 2^a solltest du machen, sonst wird es schwieriger die lineare Approximation zu machen (bei 2^a weisst du immer genau, welche Bits betroffen sind, bei anderen Multiplikationen nicht) Der Wertebereich muesste dann 2^a * log2(Bitanzahl) sein. Ob das mit dem ODER am Ende stimmt, musst du noch schauen. Die oberen ceil(log2(Bitanzahl)) Bits im Ergebnis duerfen jedenfalls nicht geaendert werden bzw nur die unteren a Bits duerfen geaendert werden. Vielleicht sieht man es so: k = Nummer des hoechsten gesetzten Bits in x x(s): Das Bit s aus x Dann sind die einzelnen Stellen des Ergebnisses k (x(k-1) x(k-2) ... x(k-1-a)) Wenn dir das lineare noch nicht reicht, wiederholst du den Vorgang mit den restlichen Bits. a muss dann natuerlich nochmal anders gewaehlt werden.
Hallo Falk Vielen Dank für Deinen interessanten Tipp. Habe ihn erst jetzt gesehen:) 512 Byte * 4 sind etwas viel, man könnte aber vielleicht die Tabelle auf 128 Werte reduzieren. Dementsprechende auch die Indexwerte. Die Anforderungen an die Genauigkeit der Kurve sind nicht hoch. "Deine Tabelle mit den x-Werten und den zugehörenden-Tabelle" liesse sich vielleicht auch reduzieren, wenn man den Wert x um 16 bit schiebt, dann wären es für x nur mehr 512*2 Byte. Wie würde dann aber bitte die Berechnung des Index erfolgen. Müsste man in einer Schleife nach dem passenden x suchen? Successive Approximation? Die Schleife läuft wird für jedes x ein mal ausgeführt. Bei diesem Beispiel 300.000 mal. Beste Grüsse Geri
@ Gerhard Burger (geri) >"Deine Tabelle mit den x-Werten und den zugehörenden-Tabelle" liesse >sich vielleicht auch reduzieren, wenn man den Wert x um 16 bit schiebt, >dann wären es für x nur mehr 512*2 Byte. Das geht nicht, weil die Kurve ziemlich nichtlinear ist. Man kann eher noch auf 24 Bit/Wert ausweichen, aber dann wird die Datenverwaltung ein wenig aufwendiger (Struct). MfG Falk
> Wie würde dann aber bitte die Berechnung des Index erfolgen. Müsste man > in einer Schleife nach dem passenden x suchen? Successive Approximation? DAC wurde schon genannt. Hier in Gestalt der binären Suche. Die Tabelle könnte dann bspw. für x < 1000 deutlich mehr Stützstellen enthalten als für x >= 1000. Genauso gut könnte man auch mehrere Tabellen nehmen, bei denen man dann nur noch die entsprechenden High, Low oder Mid-Bytes in der Tabelle speichern müsste. Z.B. Tab1 0 <= x <= 255, Tab2 256 <= x <= 65535 etc. (falls die Genauigkeit dann noch reicht)
Hallo zuammen Euch allen nochmals vielen Dank für die sehr interessanten Lösungen! @Falk: Ich habe Deine Lösung so interpretiert, dass man Wertepaare x und den dazugehörenden Index speichert. Die x-Werte werden nicht linear, aber aufsteigend sortiert abgelegt. Ich denke, die Indexberechnung müsste man dann halt durch einen Vergleich des aktuellen x-Wertes mit dem aktuellen x-Wert des Arrays vergleichen und falls kleiner den Index erhöhen. Also, eine Mischung aus Deiner Tabelle, wenigen Stützstellen nach Rolf Magnus, dann käme man sogar mit erträglichen Speicherbedarf. Beste Grüsse Geri
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.