Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Intelligentes Runden


AXMD - Sa 29.07.06 18:26
Titel: Intelligentes Runden
Hi!

Da ich gerade am Basteln bin und wieder einmal Achsenbeschriftungen zeichnen muss, suche ich nach einer Möglichkeit, die Zahlen unter den Achsen (also die Achsenbeschriftungen) "intelligent" runden zu lassen - wobei nicht nur die Nachkommastellen berücksichtigt werden sollen. Beispiel:


Quelltext
1:
2:
3:
4:
19,9999 -> 20
100000,001 -> 100000
0,0000000000001 -> 0
2,49999975 -> 2,5


Jemand eine Idee? Bietet das .NET-Framework hier evtl. irgendetwas an?

AXMD


UGrohne - Sa 29.07.06 19:56

Nur mal zur Vorgehensweise: Du willst also auf eine bestimmte Anzahl Stellen runden? Sieht jedenfalls so aus ;)

Dann multipliziere die Zahl mit 10^(Anzahl der gewünschten Stellen), runde Sie (unter Delphi mit Round) und teile sie wieder durch die obige Zahl. Nullen am Ende werden ja bei der Ausgabe normalerweise automatisch abgeschnitten, außer man macht es entsprechend (z.B. mittels FloatToStrF in Delphi).


AXMD - Sa 29.07.06 20:04

user profile iconUGrohne hat folgendes geschrieben:
Nur mal zur Vorgehensweise: Du willst also auf eine bestimmte Anzahl Stellen runden?


Nein ;). Die Anzahl der Stellen kenne ich nicht - genau das ist ja das Problem ;)

AXMD


UGrohne - Sa 29.07.06 20:08

user profile iconAXMD hat folgendes geschrieben:

Nein ;). Die Anzahl der Stellen kenne ich nicht - genau das ist ja das Problem ;)

Dann verstehe ich noch nicht genau Dein Problem. Nenne mal einen Sonderfall, wo meine Vorgehensweise nicht funktionieren würde. Und eben, was noch berücksichtig werden soll. Das ist aus Deinen Beispielen nämlich nicht ersichtlich.


AXMD - Sa 29.07.06 20:15

user profile iconUGrohne hat folgendes geschrieben:
Nenne mal einen Sonderfall, wo meine Vorgehensweise nicht funktionieren würde. Und eben, was noch berücksichtig werden soll. Das ist aus Deinen Beispielen nämlich nicht ersichtlich.


Es kann vorkommen, dass eine Zahl um so viel von einem gerundeten Wert abweicht, dass sie gerade noch als "nicht gerundet" betrachtet wird. Sowas wie z.B. 1,5000000000001 ö.ä. - eine Achse, die so beschriftet ist, ist absolut unbrauchbar - da sollte einfach nur 1,5 stehen - eventuell auch abhängig vom aktuellen Zoom. Wenn ich mein Koordinatensystem von (X-Achse) 1,49999999999999 bis 1,500000000000003 betrachte, sollte 1,5000000000001 schon voll ausgeschrieben werden, aber nicht, wenn ich mein Koordinatensystem von -60 bis +20 betrachte und eine der Beschriftungen eben bei 1,5000000000001 wäre ;). Das wäre das "intelligente" daran ;)

AXMD


Holgerwa - Sa 29.07.06 20:20

Hallo,

nur mal ins Unreine geschrieben, könntest Du doch zuerst den Bereich Deiner Achse (max - min) feststellen und mit Hilfe der Anzahl der Beschriftungspunkte festlegen, wie viele Nachkommastellen sinnvoll sind. Danach rundest Du entsprechend.

Holger


AXMD - Sa 29.07.06 20:20

Ja, entsprechende Funktionen sind dazu schon implementiert. Die Frage ist eben nur, was "sinnvoll" ist ;)

AXMD


Holgerwa - Sa 29.07.06 20:23

Hallo,

bei einer Achsenbeschriftung ist eine sinnvolle Anzahl Nachkommastellen doch dann erreicht, wenn es keine gleichen Werte bei benachbarten Beschriftungen gibt. Ist das der Fall, dann muß die Anzahl erhöht werden.
Oder sehe ich das zu einfach?

Holger


AXMD - Sa 29.07.06 20:26

Ich bräuchte mehr die Anzahl Nachkommastellen, auf die gerundet werden muss, wobei zusätzlich (wie oben erwähnt) nicht nur die Nachkommastellen berücksichtigt werden sollen.

AXMD


Jetstream - Sa 29.07.06 20:29

Also willst du die Anzahl der gerundeten Stellen von der Größe des ausgewählten Intervalls abhängig machen.

Ich versuch mal Pseudo-Code:

Delphi-Quelltext
1:
2:
3:
4:
function myRound(zahl,intervall:Real):Real;
begin
  result := intervall * round( 10 * zahl / intervall ) / 10;
end;


Probiers mal aus, müsste jeweils auf eine Nachkommastelle weiter Runden als dein Intervall groß ist.

myRound(5.00000001, 10) = 5
myRound(234567, 100000) = 230000
myRound(0.00023, 0.001) = 0.0002

Wenn du mehr Nachkommastellen haben willst, musst du Nullen an die beiden Zehnen dranhängen.


AXMD - Sa 29.07.06 20:30

Werd ich mir mal ansehn, danke :)

AXMD


Holgerwa - Sa 29.07.06 20:33

Hallo,

wenn Du z.B. von 1.49 bis 1.51 beschriften mußt, und 10 Beschriftungen möchtest, dann würde ich so vorgehen:
Abstand = 1.51 - 1.49 = 0.02
Angefangen mit z.B. 2 Nachkommastellen, bekommst Du:
1. Punkt = 1.49
2. Punkt = 1.49 + 0.002 = 1.492, gerundet auf 2 NK also wieder 1.49
Daraus schließt Du, daß 2 NK zu wenig sind.
Nächster Schritt: 3 NK
1. Punkt = 1.490
2. Punkt = 1.490 + 0.002 = 1.492 -> funktioniert.

So hatte ich das gedacht, ein "herantasten" an die minimal notwendige NK Anzahl.

Holger


BenBE - Sa 29.07.06 23:05

Ich denk mal, er meint sowas:

0,123456789 --> Nicht runden
0,12345678901 --> Runden auf 0,123456789
2,499975 --> 2,5
2,49994 --> 2,49994

Also in dem Sinne eine Art "intelligenz", dass die Funktion automatisch erkennt, wann eine Rundung des Wertes sinnvoll ist.

1200 Byte --> 1,2kB
1024 Byte --> nicht 1,024 Byte, sondern 1KB ...

Aber ich denk, wir sollten hier mal noch ein par Informationen zum Genauen Verwendungshintergrund anfordern ;-)


AXMD - Sa 29.07.06 23:13

Wie bereits gesagt: Achsenbeschriftung (Dezimalwerte). Es sieht einfach unschön aus, wenn man da zu lesen bekommt: "1.00000001 2.00000001 3.00000002" nur weil durch irgendwelche Rechenoperationen hinten nicht mehr alle Kommastellen ganz exakt sind. Ich wünsche mir eine Achsenbeschriftung wie "1 2 3", aber zB auch eine Achsenbeschriftung wie "1.42258 1.84906 ..." - die Kommastellen sollten so weit angezeigt werden, wie sie "sinnvoll" sind. Noch ein Beispiel: 1.4225800001 sollte wie im vorigen Beispiel einfach als 1.42258 angezeigt werden. Ich hoffe, ihr versteht, was ich meine ^^

AXMD


delfiphan - So 30.07.06 00:20

Damit man "schöne" Achsenbeschriftungen bekommt würde ich nur Zahlen aus der 10er, 2er bzw. 5er Reihe akzeptieren (in meinem Plotter ist das jedenfalls so):

Beispiele:
2er: -1.0 -0.8, -0.6, -0.4, -0.2, 0, 0.2, 0.4, 0.6, 0.8 1.0
5er: -1, -0.5, 0, 0.5, 1.0
5er: -1.005, -1.000, -9.995, -9.990
10er: -3, -2, -1, 0, 1, 2, 3

Hier der entsprechende Source:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
var
 min, max, idealinterval, fittedinterval_10, fittedinterval_5, fittedinterval_2, x, fittedinterval: Extended;
 idealcount, fittedcount_10, fittedcount_5, fittedcount_2, fittedcount: Integer;
begin
  min:=random*100-50// bereichsminimum
  max:=min+random*random*100// bereichsmaximum
  idealcount:=10// erwünschte anzahl ticks

  idealinterval:=(max-min)/idealcount;
  x := ln(idealinterval)/ln(10);
  // runde so, dass wir am nähesten an die ideale anzahl ticks kommen
  if floor(x) < -ln(2/1.1*idealcount/(max-min))/ln(10{sic} then
   fittedinterval_10:=power(10,ceil(x)) // aufrunden
  else
   fittedinterval_10:=power(10,floor(x)); // abrunden
  fittedcount_10:=trunc((max-min)/fittedinterval_10);

  // wir haben nun die beste Lösung mit 10er-Abständen
  fittedinterval := fittedinterval_10;
  fittedcount := fittedcount_10;

  // jetzt noch die besten 2-er bzw. 5-er berechnen
  if fittedcount_10<idealcount then
  begin
   fittedinterval_5 := fittedinterval_10/2;
   fittedinterval_2 := fittedinterval_10/5;
  end else
  begin
   fittedinterval_5 := fittedinterval_10*5;
   fittedinterval_2 := fittedinterval_10*2;
  end;
  fittedcount_2 := trunc((max-min)/fittedinterval_2);
  fittedcount_5 := trunc((max-min)/fittedinterval_5);

  // die Beste Lösung aus 10er, 5er und 2er aussuchen
  if abs(fittedcount_2-idealcount)<abs(fittedcount-idealcount) then
  begin
   fittedcount := fittedcount_2;
   fittedinterval := fittedinterval_2;
  end;
  if abs(fittedcount_5-idealcount)<abs(fittedcount-idealcount) then
  begin
   fittedcount := fittedcount_5;
   fittedinterval := fittedinterval_5;
  end;

  // ausgeben
  memo1.lines.add(format('[%s,%s] => ticks:[%s,%s] +%s (%d)',[floattostr(min),floattostr(max),floattostr(ceil(min/fittedinterval)*fittedinterval),floattostr(floor(max/fittedinterval)*fittedinterval),floattostr(fittedinterval),fittedcount]));
end;



Beispiele
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
min,max            ticks von,bis        tick intervall  anzahl tickintervalle
[-50.00,-47.30] => ticks:[-49.8,-47.4]  0.20            13 
[-29.74,-11.41] => ticks:[-28,-12]      2.00             9 
[-18.13,-12.11] => ticks:[-18,-12.5]    0.50            12 
[-7.43,-3.54]   => ticks:[-7,-4]        0.50             7 
[-42.94,-37.92] => ticks:[-42.5,-38]    0.50            10 
[-20.67,13.08]  => ticks:[-20,10]       5.00             6 
[27.47,50.35]   => ticks:[28,50]        2.00            11 
[34.42,56.43]   => ticks:[36,56]        2.00            11 
[-33.74,-18.38] => ticks:[-32,-20]      2.00             7 
[-25.33,-2.30]  => ticks:[-24,-4]       2.00            11 
[-1.82,11.22]   => ticks:[-1,11]        1.00            13 
[-21.27,54.19]  => ticks:[-20,50]       10.00            7 
[-0.75,72.71]   => ticks:[0,70]         10.00            7


Edit: Kommentare im Code


AXMD - So 30.07.06 00:40

@delphifan: sieht sehr gut aus - an eine variable Tickanzahl habe ich noch gar nicht gedacht. Ich werde mir das mal ansehn - momentan ist die Anzahl der Ticks vordefiniert (konstant) - hast du dafür zufällig auch eine Lösung?

AXMD


delfiphan - So 30.07.06 02:03

Das Problem mit Ticks an willkürlichen float-Positionen ist, dass du keine genaue Angaben machen kannst. Sobald du nämlich rundest ist die Beschriftung genau genommen am falschen Ort. Beim oberen Algorithmus hast du das Rundeproblem nicht, denn in der Beschriftung kommen nur "schöne" Zahlen vor.

Noch eine kurze Beschreibung zu oben:
Man kann beim Algorithmus oben die gewünschte Anzahl Ticks vorschlagen (Edit: Eigentlich sind es Anzahl Intervalle zwischen den Ticks, nicht Anzahl Ticks). Der Algorithmus findet dann die Lösung, bei der die Beschriftung aus schönen Zahlen bestehen und die Anzahl Ticks möglichst der gewünschten Anzahl entspricht.

Hier noch meine Überlegungen, wenn du die Anzahl der Ticks fest vorgeben willst:

Das Intervall von einem Tick zum anderen beträgt:
interval = (max-min)/intervalcount

Der Zehnerlogarithmus daraus gibt dir an, wieviel Stellen sich von einem Tick zum anderen ändern. Ist bspw. interval = 0.01, so beträgt log10(interval) = -2. Das heisst die Zahl ändert sich bis 2 Stellen nach dem Komma. Du könntest in dem Fall also bis auf 2 Stellen runden. Anderes Beispiel: Ist interval = 0.03, erhält man log10(0.03) = -1.5. Sinnvollerweise rundet man immer ab und erhält -2. Das heisst auch hier würde man auf 2 Stellen runden.

Allgemein wäre es deswegen meiner Meinung nach sinnvoll, auf -floor(log10(interval))=-floor(ln(interval)/ln(10)) Stellen zu runden.

Als Code:

Delphi-Quelltext
1:
2:
x=power(10,floor(log(interval)/log(10)))
gerundetezahl = round(zahl/x)*x


Mit diesem Algorithmus wird aber "23" in gewissen Fällen nach "20" abgerundet (könnte man mit einer if-Abfrage verhindern: Nur runden, wenn x<1). Wie du diese Fälle genau haben willst hast du uns nicht verraten.


AXMD - So 30.07.06 10:05

user profile icondelfiphan hat folgendes geschrieben:
Mit diesem Algorithmus wird aber "23" in gewissen Fällen nach "20" abgerundet (könnte man mit einer if-Abfrage verhindern: Nur runden, wenn x<1). Wie du diese Fälle genau haben willst hast du uns nicht verraten.


Bei diesen Fällen bin ich mir selbst noch nicht 100% sicher. Wenn ich mir das recht überlege, ist eine variable Tickanzahl vielleicht besser. Wie machen das denn die "großen" wie Matlab, Mathematica...?

AXMD


alzaimar - So 30.07.06 12:54

Ich weiss nicht, wie das 'die Großen' machen, ist mir auch egal, dann ich mache es immer so:
1. Interval normalisieren
2. Aus einer Liste vordefinierter Tics den Besten raussuchen.
3. Normalisiertes Interval den Tics entsprechend anpassen
4. Interval zurückrechnen

Hier der hingerotzte Code:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
Procedure GetAxis(aMin, aMax: Extended; aTics: Integer;
  Var aNewMin, aNewMax, aNewTics: Extended);
Const
  Tics: Array[0..8Of Extended =
  (0.010.020.0250.050.10.20.250.51);
Var
  nMult, nMin, nMax, nDiff, nTics: Extended;
  i, n, j, m: Integer;

Begin
  Assert(aMax > aMin, ' Lower bound > upper bound');
  nMin := aMin;
  nMax := aMax;
  If nMax < 0 Then
    nMult := -1
  Else
    nMult := 1;
  While abs(nMax / nMult) < 1 Do
    nMult := nMult / 10;
  While abs(nMax / nMult) > 1 Do
    nMult := nMult * 10;

  nMin := nMin / nMult;
  nMax := nMax / nMult;
  nDiff := nMax - nMin;

  m := 9999;
  For i := low(Tics) To High(Tics) Do Begin
    n := Trunc(nDiff / tics[i]);
    If abs(n - aTics) < m Then Begin
      m := abs(n - aTics);
      j := i;
    End
  End;
  nTics := Tics[j];
  aNewMin := (Trunc(nMin / nTics) * nTics) * nMult;
  aNewMax := (Trunc(0.9999 + nMax / nTics) * nTics) * nMult;
  aNewTics := nTics * nMult;
End;

aMin und aMax sind die Min/Max-Were, aTics die gewünschte Anzahl von Tics. Rückgabe sind die angepassten Min/Max-Werte sowie der Ticabstand.

Beispiel: GetAxis (2.311.26, NewMin, NewMax, NewTics)
Liefert NewMin=2.0, NewMax = 12 und NewTics = 2.0

Edit:
Der Teil:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
...
  If nMax < 0 Then
    nMult := -1
  Else
    nMult := 1;
  While abs(nMax / nMult) < 1 Do
    nMult := nMult / 10;
  While abs(nMax / nMult) > 1 Do
    nMult := nMult * 10;

  nMin := nMin / nMult;
  nMax := nMax / nMult;
...

lässt sich bestimmt durch Log-Berechnungen einfacher gestalten ..


delfiphan - So 30.07.06 13:46

Mathematica hab ich grad nicht zur Hand. Matlab macht auch nur 10er, 5er und 2er-Schritte (*10^a). Von dort hab ich ursprünglich die Idee übernommen.

Dort wird (bei der Standardeinstellung) der eingegebene Bereich noch soweit vergrössert, bis die obere/untere/rechte/linke Kante genau auf einem Tick liegt. Das gefällt mir jedoch persönlich weniger... (Das heisst wenn man bspw. den Sinus von 0 bis 2pi plottet geht der Plot nicht von 0 bis 2*pi (6.28...) sondern bis 7)


alzaimar - So 30.07.06 17:24

Hi delfiphan,

die Anpassung der Achsenschranken sollte natürlich optional sein, denn manchmal ist es sinnvoll (z.B. Messwerte sinnvoll darstellen um Clipping zu vermeiden), und manchmal eben nicht.


zongo-joe - Di 01.08.06 13:32

Ihr schwebt da ja schon in höheren Sphären...
vielleicht eine kleine Anregung aus dem Brute-Force-Bereich ?

Ich würde nach "000" und "999" suchen, zB pos("000", floattostr(zahl)) und davon die Anzahl der Nachkommastellen abhängig machen, der Rest ergibt sich dann von selbst; ist zwar nicht sehr elegant, aber flott und einfach.


alzaimar - Di 01.08.06 13:49

user profile iconzongo-joe hat folgendes geschrieben:
... ist zwar nicht sehr elegant, aber flott und einfach.

und ungenau und unsauber.

Man kann doch nicht einfach Zahlen so runden, das sie hübsch aussehen. In der Wissenschaft und der Mathematik ist die gewünschte Genauigkeit sehr wohl bekannt. Mein Beispiel zeigt nur, wie man Achsenbeschriftungen automatisch erstellen kann. Eine Formatierung der Nachkommastellen erfolgt nicht, denn man hat bei Floating-Point Zahlen eigentlich immer das Problem, das irgendwo "krumme" Zahlen auftreten (0.1000000001321, statt 0.1). Da der gute Programmierer aber immer weiß, in welcher Welt (zahlentechnisch) er sich gerade befindet, kann er dann auch sehr elegant über eine kleine Rundung diesen Quark abschnippeln. Nebenbei kommen diese Rundungsfehler infolge der binären Darstellung ohnehin nur im Bereich von (grob geschätzt) 10^-6 - 10^-12 (Single, bzw. Extended) vor. Da der ernsthafte Programmierer keine Singles verwendet, reicht eine präventive Anzeige von 8 Dezimalstellen aus, obwohl man sich da, z.B. bei Meterangaben durchaus zum Ött macht.

Beim Runden gilt IMMER: Mit Augenmaß und Sachverstand.


delfiphan - Mi 02.08.06 14:29

user profile iconzongo-joe hat folgendes geschrieben:
vielleicht eine kleine Anregung aus dem Brute-Force-Bereich ?
Wieso brute-force wenn es durch eine kleine Rechnung geht?

user profile iconzongo-joe hat folgendes geschrieben:
Ich würde nach "000" und "999" suchen, zB pos("000", floattostr(zahl)) und davon die Anzahl der Nachkommastellen abhängig machen, der Rest ergibt sich dann von selbst; ist zwar nicht sehr elegant, aber flott und einfach.
Stell dir vor die Skala ginge von 0.999 bis 1. In dem Fall möchte ich nämlich z.B. 0.999, 0.9991, 0.9992, ..., 0.9999, 1 als Beschriftung sehen. Da funktioniert der Ansatz mit pos schon mal nicht.