Aus wievielen Ziffern besteht meine Ganzzahl??

[bingo72]

Hallo!!

Ich frag mich gerade, wie man am elegantesten die Anzahl der Stellen einer Ganzzahl ermittelt??
Ich hätt halt sonst gefühlsmässig den Integer in einen String umgewandelt und mit Length die Anzahl bestimmt??!!

Ist das so ok oder gibts was besseres??

LG
Thomas

[sirius]

Du kannst auch in einer Schliefe solange "div 10" machen, bis deine Zahl 0 ist. Und natürlich die Anzahl der divs zählen.

[bingo72]

Ok...danke!!

[Kroko1999]

Delphi-Quellcode:

ZiffernCount := 1+Int(Abs(ln(Ganzzahl))/ln(10));

[Edit]Formel verbessert
[Edit1] +1 hinzugefügt

[PaddyL]

Length(IntToStr(X)) dürfte auch gehen. Wie elegant bzw. schnell sowas ist weiß ich allerdings nicht.

[tr909]

Zitat:

Zitat von Kroko1999

Delphi-Quellcode:

ZiffernCount := Int(ln(Ganzzahl)/ln(10));

n1ce, aber wenn dann noch ZiffernCount := Int(ln(Ganzzahl)/ln(10))+ 1;

[s-off]

Zitat:

Zitat von PaddyL

Length(IntToStr(X)) dürfte auch gehen. Wie elegant bzw. schnell sowas ist weiß ich allerdings nicht.

Wer lesen kann... :mrgreen:

Auch ich würde diesen Weg gehen.

[Daniel Schuhmann]

Zitat:

Zitat von s-off

Auch ich würde diesen Weg gehen

Die div 10-Lösung dürfte effizienter sein.

[s-off]

Tatsächlich,
habe mal ein paar Messungen mit folgendem Code durchgeführt:

Delphi-Quellcode:

Function TForm1.DivMethod(_Value: Integer): Integer;
Begin
   Result := 0;

   While _Value > 0 Do Begin
      _Value := _Value Div 10;
      Inc(Result);
   End;
End;

Function TForm1.StrMethod(_Value: Integer): Integer;
Begin
   Result := Length(IntToStr(_Value));
End;

wobei ich jeweils eine zehnstellige Zahl übergeben habe.

Bei einmaligem Aufruf der beiden Funktionen ergab sich im Durchschnitt (bei 10 Testläufen) ein auf die Laufzeit bezogener Faktor von 10,29 zu Gunsten der DivMethod-Funktion.

Für den einmaligen Gebrauch ist diese also tatsächlich deutlich schneller.

Anschliessend habe ich die Funktionen 100000 mal aufrufen lassen. Hier sinkt der Faktor allerdings auf minimale 1,10 ab.

Nun meine Frage: Wie kommt das? Werden da irgendwelche Werte 'zwischengespeichert' und wiederverwendet, so dass auf Dauer gesehen die StrMethod-Methode vielleicht sogar schneller werden würde als die DivMethod-Methode?

[sirius]

Hast du von den Zeitwerten den Durchschnitt gebildet, hast du das Minimum genommen, wie hast du Zeit gemessen. Da kann dir einiges in die Quere kommen. Auch Krokos Variante dürfte fix sein (er sollte nur die abs(Ganzzahl) bilden)

[Reinhard Kern]

Theoretisch müsste es schneller gehen, die Zahl nacheinander mit (Konstanten!) 10, 100, 1000... zu vergleichen, das ergibt auch so viele Berechnungen wie Stellen, aber in jeder Stufe nur eine Subtraktion statt einer Division. Am besten in Assembler als lineare Folge von Compare und Jump-Befehlen.

also

Delphi-Quellcode:

        .RADIX 10
        CMP     EAX,10
        JNB     Next1
        RET     1
Next1:  CMP     EAX,100
        JNB     Next2
        RET     2
Next2:

usw.

Gruss Reinhard

[s-off]

Zitat:

Zitat von sirius

Hast du von den Zeitwerten den Durchschnitt gebildet, hast du das Minimum genommen, wie hast du Zeit gemessen. Da kann dir einiges in die Quere kommen. Auch Krokos Variante dürfte fix sein (er sollte nur die abs(Ganzzahl) bilden)

Die Zeiten habe ich mit ProDelphi gemessen. Dieses berechnet Durchschnittswerte etc. automatisch.

Edit: @Reinhard Kern
Daran habe ich auch zuerst gedacht. Dadurch wäre ich aber nicht mehr dynamisch, da ich sämtliche Werte vorgeben muss, was zwar endlich, aus meiner Sicht aber dennoch unschön ist.

[Reinhard Kern]

Zitat:

Zitat von s-off

Edit: @Reinhard Kern
Daran habe ich auch zuerst gedacht. Dadurch wäre ich aber nicht mehr dynamisch, da ich sämtliche Werte vorgeben muss, was zwar endlich, aus meiner Sicht aber dennoch unschön ist.

Hallo, das ist meistens so: schnell ist nicht elegant. Mein Vorschlag ist eben gerade deshalb schnell, weil er Konstanten benutzt (also die Stufen vorher berechnet sind) und weil er die Schleife aufrollt - eine übliche Technik zur Geschwindigkeitserhöhung. Das Gegenteil sind rekursive Lösungen - elegant formuliert, aber langsam und mit indiskutabler Stack-Belastung.

Gruss Reinhard

[alzaimar]

[OT]

Zitat:

Zitat von Reinhard Kern

Das Gegenteil sind rekursive Lösungen - elegant formuliert, aber langsam und mit indiskutabler Stack-Belastung.

Ein Vorurteil aus der SWT-Antike. In der Tat sind rekursive Lösungen nur unwesentlich langsamer als ihr iteratives Pendant. Und eine sinnvolle rekursive Lösung (z.B. Quicksort oder Backtracking) belasten den Stack nur minimal: Die paar Bytes, die jedesmal auf den Stack geschoben werden, machen den Kohl nicht fett)
[/OT]

[s-off]

Danke für die Erläuterungen!

[3_of_8]

Um das ganze mal rein in Delphi zu formulieren:

Delphi-Quellcode:

function GetDecimalFigures(AValue: Integer): Integer;
const POWERSOFTEN: array[0..9] of Integer =
  (1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
  100000000, 1000000000);
var lo, hi, mid: Integer;
begin
  lo:=0;
  hi:=high(POWERSOFTEN);
  Result:=0;
  AValue:=abs(AValue);

  while Result=0 do
  begin
    mid:=lo+(hi-lo) div 2;
    if POWERSOFTEN[mid]<AValue then
      lo:=mid+1
    else if POWERSOFTEN[mid]>AValue then
      hi:=mid-1
    else begin
      Result:=mid+1;
    end;
    if lo>=hi then Result:=hi+1;
  end;
end;

Das ganze benutzt - wie vorher vorgeschlagen - ein Konstantenarray, dazu binäre Suche.

[grenzgaenger]

Zitat:

Zitat von Kroko1999

Delphi-Quellcode:

ZiffernCount := Int(Abs(ln(Ganzzahl))/ln(10));

[Edit]Formel verbessert

du weisst schon, dass du da immer verschiedene lösungen bekommst... ;-)

log 300 / log 10 --> 2.478 --> int 2
log 500 / log 10 --> 2.699 --> int 3

wie viele stellen hat denn nun die 3 stellige zahl? 2 oder 3... oder nach dem kollegen 3 oder 4??? :gruebel: :gruebel:

[grenzgaenger]

Zitat:

Zitat von 3_of_8

Um das ganze mal rein in Delphi zu formulieren:

Delphi-Quellcode:

function GetDecimalFigures(AValue: Integer): Integer;
const POWERSOFTEN: array[0..9] of Integer =
  (1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
  100000000, 1000000000);
var lo, hi, mid: Integer;
begin
  lo:=0;
  hi:=high(POWERSOFTEN);
  Result:=0;
  AValue:=abs(AValue);

  while Result=0 do
  begin
    mid:=lo+(hi-lo) div 2;
    if POWERSOFTEN[mid]<AValue then
      lo:=mid+1
    else if POWERSOFTEN[mid]>AValue then
      hi:=mid-1
    else begin
      Result:=mid+1;
    end;
    if lo>=hi then Result:=hi+1;
  end;
end;

Das ganze benutzt - wie vorher vorgeschlagen - ein Konstantenarray, dazu binäre Suche.

das ganze geht doch auch etwas eleganter ... :-)

Delphi-Quellcode:

function GetIntLength(const Zahl: integer; Count: integer): integer;
var
 tmp: integer;
begin
 tmp := zahl div 10;
 if tmp>0 then
  result := GetIntLength(tmp, count + 1)
 else 
  result := count + 1;
end;

[3_of_8]

Das ist vielleicht eleganter, aber auch langsamer, da es ein divs benutzt. ;)

[grenzgaenger]

hast recht, bei 100000 aufrufen einer 10 stelligen zahl stellt sich das wie folgt dar...

Zitat:

Rekursiv: 5569 Ticks
Interativ: 5387 Ticks

also, schon extrem langsamer ... :zwinker:

[3_of_8]

Ich rede hier nicht davon, ob es extrem langsamer ist, es geht um Optimierungen allgemein. Außerdem ist auf solche Messungen kein Verlass, sie hängen stark von den Software- und Hardwareumständen ab.

[grenzgaenger]

im rahmen der optimierung und der pflegbarkeit, würd ich jedoch den rekursiven algo. vorziehen... (a) ist er nicht grad langsamer und (b) sehr viel übersichtlicher und daher (c) leichter zu pflegen und (d) zu verstehen. j4m2c

[Kroko1999]

Zitat:

Zitat von grenzgaenger

...
du weisst schon, dass du da immer verschiedene lösungen bekommst... ;-)

log 300 / log 10 --> 2.478 --> int 2
log 500 / log 10 --> 2.699 --> int 3

wie viele stellen hat denn nun die 3 stellige zahl? 2 oder 3... oder nach dem kollegen 3 oder 4??? :gruebel: :gruebel:

Hast Du es mal ausprobiert :?: Deine Aussage ist falsch, ich habe gerade ausprobiert, es fehlt ein +1 aber ansonsten rundet Int immer ab :!: :feuerchen: