# Länge eines Integers ermitteln?



## Guest (28. Apr 2008)

Hallo Leute,

ich würde gerne *schnell* die Länge eines Integers ermitteln.

Die naive Variante, die jedoch *zu langsam* ist wäre diese:

```
public int getlength(int zahl){
   String s = String.valueOf(zahl);
   return s.length();
}

Da ich das seeeeehr häufig machen muss hätt ichs gern schneller. Nur wie?
```


----------



## maki (28. Apr 2008)

Nun ja,

wenn der int < 10 und > -10 ist, ist er einstellig
wenn er < 100 und > 10 ist, ist er zweistellig

usw.


----------



## Gast (28. Apr 2008)

Naja, 
das wäre schon eine Möglichkeit, stimmt.

Falls der Wert in einem Bereich zwischen 1 und 1000000 liegt, ist das mit If Abfragen dann immer noch schneller?


----------



## maki (28. Apr 2008)

Klar, es werden keine temporären Strings erzeugt.

Ich nehme an, dass du nicht nur vermutest dass deine Lösung zu langsam ist, sondern nachgemessen hast und nicht nur wild rumrätst und spekulierst, oder?


----------



## SlaterB (28. Apr 2008)

wenn du noch extrem optimieren willst, dann gehe bei den Vergleichen systematisch vor:
teste erst auf größer 10.000, dann je nach Fall größer 100 oder 100.000 usw., möglichst immer die Mitte,
anderseits gibts vielleicht hauptsächlich Zahlen in einem bestimmten Bereich?
dann diesen zuerst testen

viel Sinn macht das aber nicht  , schneller als String sind 10 Vergleiche auf jeden Fall


----------



## raptor (28. Apr 2008)

Keine Ahnung, wie es mit der Geschwindigkeit aussieht, aber wie wäre es denn mit Rekursion?


```
public static int countDigits(int number) {
	number = Math.abs(number);
	
	int count = 0;
	
	if(number<10) {
		count++;
	}
	else {
		count += countDigits(number/10) + 1;
	}
	
	return count;
}
```


----------



## Gast (28. Apr 2008)

@maki: Ne ich hab meine toString() Lösung gemessen und gesehen, dass hier die Geschwindigkeitsbremse liegt und hab nach einer besseren Lösung gesucht.

Die 10 If-Abfragen halten sich gerade gar nicht so schlecht, aber die Rekrursion von Raptor werd ich auch gleich mal testen. 

Danke euch!


----------



## Guest (28. Apr 2008)

```
int c = 1;
        
        while((k /= 10) != 0) {
            c++;
        }
```
k deine zahl und c dann die 'laenge' der zahl


----------



## gizmo (28. Apr 2008)

```
public class Test {
    /**
     * @param args
     */
    public static void main(String[] args) {
        int z = 123451;

        double d = Math.log(z)/Math.log(10);

        int i = (int) d + 1;

        System.out.println(i);
    }
}
```


----------



## Grasstampfer (28. Apr 2008)

or even simpler

```
int i = (int)Math.log10( z ) + 1;
```


----------



## gizmo (28. Apr 2008)

Hmm... In meinem Java gibts noch kein log10 :-(.


----------



## raptor (28. Apr 2008)

Interessant was es für Lösungen gibt, wenn man sich der Mathematik bedient. Nur dazu muss man sie genau kennen.

Warum und wie funktioniert das mit dem Logarhythms?


----------



## gizmo (28. Apr 2008)

Die Länge von x entspricht in folgender Gleichung y:

x = 10^(y-1)

Wenn man die Gleichung nach y auflöst hat man:

y-1 = log(10, x)

So ungefähr... (int) wird zum abrunden gebraucht.

Edit: Meine natürlich y = log(10, x) + 1


----------



## Grasstampfer (28. Apr 2008)

gizmo hat gesagt.:
			
		

> Hmm... In meinem Java gibts noch kein log10 :-(.


gibts ab 1.5


----------



## Marco13 (28. Apr 2008)

gizmo hat gesagt.:
			
		

> ```
> public class Test {
> ...
> double d = Math.log(z)/Math.log(10);
> ...



 :applaus: 
(Ich find's gut, wenn leute nur dann antworten, wenn sie auch eine gute (oder in diesem Fall "DIE" richtige) Antwort wissen. Mach ich auch nicht _immer_, aber bemühe mich zumindest darum...)


----------



## Gast (28. Apr 2008)

Ist das mit dem Logarithmus nicht ein bisschen riskant - aufgrund der Ungenauigkeit in der Gleitkommaarithmetik?


----------



## SlaterB (28. Apr 2008)

interessant ist letztlich ja auch, wie dieser Vierkampf ausgeht 


```
public class Test
{
    static int k = 3000000;

    public static void main(String[] args)
        throws Exception
    {
        Worker w1 = new Worker()
            {
                public int calc(int i)
                {
                    String s = String.valueOf(i);
                    return s.length();
                }
            };
        Worker w2 = new Worker()
            {
                public int calc(int i)
                {
                    return (int)Math.log10(i) + 1;
                }
            };
        Worker w3 = new Worker()
            {
                public int calc(int i)
                {
                    if (i < 10)
                    {
                        return 1;
                    }
                    else if (i < 100)
                    {
                        return 2;
                    }
                    else if (i < 1000)
                    {
                        return 3;
                    }
                    else if (i < 10000)
                    {
                        return 4;
                    }
                    else if (i < 100000)
                    {
                        return 5;
                    }
                    else if (i < 1000000)
                    {
                        return 6;
                    }
                    return 7;
                }
            };
        Worker w4 = new Worker()
            {
                public int calc(int i)
                {
                    int c = 1;
                    while ((i /= 10) != 0)
                    {
                        c++;
                    }
                    return c;
                }
            };
        test(w1);
        test(w2);
        test(w3);
        test(w4);
        test(w1);
        test(w2);
        test(w3);
        test(w4);
    }

    public static void test(final Worker worker)
    {
        long time = System.currentTimeMillis();
        long sum = 0;
        for (int i = 0; i < k; i++)
        {
            sum += worker.calc(7);
            sum += worker.calc(77);
            sum += worker.calc(777);
            sum += worker.calc(7777);
            sum += worker.calc(777777);
            sum += worker.calc(1000000);
        }
        System.out.println("sum: " + sum + ", time: " + (System.currentTimeMillis() - time));
    }
}


interface Worker
{
    public int calc(int i);
}

---------

Ausgabe bei mir:

sum: 69000000, time: 2484
sum: 69000000, time: 3531
sum: 69000000, time: 328
sum: 69000000, time: 1860
sum: 69000000, time: 2656
sum: 69000000, time: 3609
sum: 69000000, time: 281
sum: 69000000, time: 1766
```

Fazit: if/else nicht zu schlagen, 
Rekursion muss viel rechnen, String überraschend schnell, wird da gecacht?
log gar am langsamsten mit höchsten Rechenaufwand


----------



## gizmo (28. Apr 2008)

Ich würde mich wohl zwischen der Lösung mit dem String und der iterativen Lösung entscheiden. Der Weg über den String ist der lesbarste. Die Iterative Lösung ist dafür noch etwas schneller.

Die Lösung über den Logarithmus bringt keinen Mehrwert gegenüber den anderen Lösungen und die Lösung mit if/else ist hoffentlich nicht ernst gemeint.


----------



## SlaterB (28. Apr 2008)

wieso nicht ernst gemeint? halte ich für die einzig in Frage kommende Lösung wenn die Parameter es erlauben

edit:
hier noch so eine Diskussion, da wird auch String preferiert 
http://www.informatik-forum.at/showthread.php?t=30590


----------



## Marco13 (28. Apr 2008)

Traue keiner Statistik.... :wink: Integers gehen immerhin bis ca. +-2^31. Selbst wenn man die if-Version entsprechend aufbohrt ist sie noch mit Abstand am schnellsten - und wenn man in der eigentlichen Testschleife die Zahlen mal bis 1111111111 gehen läßt, sieht man, dass die log-Lösung noch die zweitschnellste ist.

Womit man sagen könnte, dass man im Allgemeinen wohl

```
public int calc(int i)
                {
                    return (int)Math.log10(i) + 1;
                }
```
schreiben kann, und wenn es Zeitkritisch ist "notgedrungen" auf sowas wie 

```
public int calc(int i)
                {
                    if (i < 10)
                    {
                        return 1;
                    }
                    else if (i < 100)
                    {
                        return 2;
                    }
                    else if (i < 1000)
                    {
                        return 3;
                    }
                    else if (i < 10000)
                    {
                        return 4;
                    }
                    else if (i < 100000)
                    {
                        return 5;
                    }
                    else if (i < 1000000)
                    {
                        return 6;
                    }
                    else if (i < 10000000)
                    {
                        return 7;
                    }
                    else if (i < 100000000)
                    {
                        return 8;
                    }
                    else if (i < 1000000000)
                    {
                        return 9;
                    }
                    return 10;
                }
```
ausweichen sollte....


----------



## SlaterB (28. Apr 2008)

hmm, bei mir ändert sich bei den Zeitverhältnissen nichts wesentliches, warum auch,
vielleicht hast du bessere log-Hardware 
aber auf die Details kommts nun wirklich nicht mehr an


----------



## gizmo (28. Apr 2008)

Würdest du wenn du Chef wärst deinen Mitarbeitern erlauben solchen Code zu schreiben? Ich würde es nicht (Ich bin aber auch kein Chef ;-)).

Stell dir vor, der Code landet in der Methode calculateIntLength. Irgendwann würde garantiert jemand versehentlich, die Methode mit einem Parameter aufrufen, welcher sich nicht im Range befindet. Es ist also aus meiner Sicht instabiler Code.


----------



## SlaterB (28. Apr 2008)

eine berechtigte Kritik, die man, wenn relevant, durch Abdeckung aller int-Bereiche begegnen könnte,
wenn man von -10 bis +10 arbeitet dann lohnt sich sogar auch die eingangs genannte baumartige if-Verschachtelung:
erste auf +- prüfen, dann 10^5, dann 10^3 oder 10^8 usw.

Instabilität läßt sich also vollständig ausbauen ohne echte Zeitverluste,
müsste man beim String wegen des Minus-Zeichens übrigens auch noch machen, je nachdem ob es mitgezählt werden soll,
bei den anderen beiden auch


----------



## gizmo (28. Apr 2008)

Ich schlage vor:
	
	
	
	





```
public int calc(int z)
                {
                    int c = 0;
                    for(int i = 1; z >= i; i *= 10, c++);
                    return c;
                }
```
Fast scho schnell wir if/else, macht auch etwa dasselbe, aber nicht so wüst. Multiplizieren scheint schneller zu sein als dividieren, oder wieso ist die andere iterative Lösung langsamer?


----------



## Marco13 (28. Apr 2008)

@SlaterB: Wenn man k mal auf Integer.MAX_VALUE*/2* setzt, das if Entsprechend erweitert, und die Schleife

```
for (int i = 0; i < k; i+=100)
        {
            sum += worker.calc(k);
        }
```
laufen lässt, kommt (bei mir :roll: ) das hier raus
sum: 107374190, time: 2766
sum: 107374190, time: 984
sum: 107374190, time: 203
sum: 107374190, time: 2704

@gizmo: Wie gesagt, wenn's zeitkritisch ist, und man damit ein langsames Programm doppelt so schnell machen kann... (nun, ich kann mir nicht vorstellen, wo die Längenbestimmung für ints zeitkritisch sein sollte, aber ... naja :roll: )

Die Frage nach den gültigen Eingabewerten ist aber nicht ganz unwichtig. Bei long (statt int) würde es die log-Lösung nämlich bei sehr großen Werten irgendwann raushauen....


----------



## gizmo (28. Apr 2008)

@Slater: Was ist, wenn du plötzlich long überprüfen willst? Wieder if/else hinzufügen? Das gibt sehr viel duplizierten Code, was die Wartbarkeit enorm verschlechtert. Wenn du Code x mal ausführen willst, schreibst du ihn auch nicht x mal hin. Genau das wurde aber gemacht.

Ich behaupte ausserdem, dass Code, der so enorm Zeitkritisch ist, dass solche Optimierungen notwendig sind, nicht in Java geschrieben wird.


----------



## SlaterB (28. Apr 2008)

@Marco13

ah, geänderte Zahlen, 
ja das macht einen Unterschied, bei den kleinen Ziffern hat auch das Teilen dicken Vorteil, da nun mal nicht so oft geteilt werden muss ,
log ist dagegen bei kleinen Zahlen langsamer

da muss man wieder auf die Verteilung der Zahlen schauen,
9stellige machen natürlich von Natur aus mindestens 90% aus, da passt das gut

@gizmo
> Optimierung unnötig

na sowas gilt ja immer und überall, dann hätten wir am Anfang gar nicht nachdenken zu brauchen 

> Wenn du Code x mal ausführen willst, schreibst du ihn auch nicht x mal hin

diese Entscheidung muss man eben treffen oder nicht,
warum gibts in Java überhaupt die unterschiedlichen Datentypen und die jeweiligen Wrapper-Klassen mit replizierten Code und dann noch sowas wie in Arrrays:



> static int binarySearch(byte[] a, byte key)
> Searches the specified array of bytes for the specified value using the binary search algorithm.
> static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key)
> Searches a range of the specified array of bytes for the specified value using the binary search algorithm.
> ...





die Operation müsste hier ja letztlich nur einmal für long geschrieben werden, wenn man es erstmals braucht,
die anderen verweisen dann darauf


----------



## gizmo (28. Apr 2008)

Wo ist hier Code dupliziert, der es nicht sein muss? Ich habe nie behauptet, dass ich die Implementation der primitiven Datentypen in Java schön finde... Meiner Meinung nach sollte alles ein Objekt sein. Es sollte keine Unterscheidungen wie int <-> Integer geben. Aber darüber kann man sicher diskutieren.

Ich sagte nicht, dass Opitmierungen grundsätzlich nicht nötig sind, ich denke aber, man kann es auch zu weit treiben.



> > Wenn du Code x mal ausführen willst, schreibst du ihn auch nicht x mal hin
> 
> diese Entscheidung muss man eben treffen oder nicht,


Dann mach mir doch bitte ein Beispiel, wo es in Java Sinn macht, Code zu duplizieren.


----------



## Marco13 (28. Apr 2008)

SlaterB hat gesagt.:
			
		

> 9stellige machen natürlich von Natur aus mindestens 90% aus, da passt das gut


Wie sagte schon mein Krypto-Prof: "Die meisten Zahlen sind sehr, sehr groß"  :lol: 

Aber mal im ernst: In den meisten Fällen kann man's wohl machen, wie man will, weil es nicht zeitkritisch ist. 

Das schöne an der log-Lösung ist IMHO, dass sie ("im Durchschnitt") recht schnell ist, und außerdem (subjektiv) "schön", weil man die Länge geschickt und in geschlossen dargestellter Form _ausrechnet_ - und das funktioniert in praktisch allen Programmiersprachen gleich. 

WENN es Zeitkritisch ist, kann man ja die if-Lösung verwenden - aber ich kann mir kaum vorstellen, in welchem Zusammenhang das sein sollte.


----------



## gizmo (28. Apr 2008)

Wozu braucht man eigentlich die Länge eines ints?


----------



## SlaterB (28. Apr 2008)

gizmo hat gesagt.:
			
		

> Dann mach mir doch bitte ein Beispiel, wo es in Java Sinn macht, Code zu duplizieren.


wie gesagt müsste man in diesem Fall nur eine Operation für long schreiben, nix zu duplizieren falls du nicht die ifs selber auch schon meinst

bei solch engen Bereichen macht es aus meiner Sicht Sinn, die Zeilen hinzuschreiben und nie wieder hinzuschauen,
anstatt den Rechner für alle Ewigkeit rechnen zu lassen,
wie überall kann man hier fragen: bei wieviel Fällen, bei 10, bei 30, bei 100? 

ein anderes Beispiel was mir noch einfällt: 
mir graut es vor den schönen neuen Java-Operationen
public void doSomething(String.. params) {
}
an einzelnen Programmstellen eine schöne Vereinfachung, 
aber wenn dann in irgeneiner Schleife sehr oft ein Übergabe-Array erstellt wird, obwohls nur 1-3 Strings sind,
dann kann ich nicht ruhig schlafen 

bei einfachen Operation wie Nachschauen in einer anderen Liste/ auf null prüfen schreibe ich dann gerne mehrfache Operationen:
public void doSomething(String param) {
}

public void doSomething(String param1, String param2) {
}

usw., macht effektiv keinen Unterschied, aber schont den Rechner


----------



## gizmo (28. Apr 2008)

Wir haben wohl einfach eine andere Priorisierung. Mir ist Lesbarkeit, Erweiterbarkeit, Skalierbarkeit wichtiger, als das letzte Quäntchen Performance.

Vielleicht stehe ich bloss auf dem Schlauch, aber ich sehe nicht, wie man eine allgemeingültige binarySearch Methode schreiben könnte, an welche die anderen Methoden weiterdelegieren.


----------



## Ark (28. Apr 2008)

Ein ganz anderer Ansatz basiert auf der Frage, wie diese Zahlen eigentlich zustandekommen, denn unter Umständen lässt sich bereits bei ihrer Erzeugung ermitteln, wie "lang" sie sind.

Ich persönlich bin für den Einsatz der Logarithmusfunktion.

Ark


----------



## gizmo (28. Apr 2008)

Aus diesem Grund habe ich auch gefragt, wozu man die Länge eines ints braucht. Ich kann mir nur vorstellen, dass man den int darstellen will. Dann bräuchte man aber sowieso einen String und könnte dann auch gleich die String-Methode verwenden.


----------



## Gast (28. Apr 2008)

Wozu man das braucht?

Beispielsweise um die Länge zweier Integer effizient miteinander zu vergleichen.

Und das braucht man beispielsweise hier: http:www.projecteuler.net


----------



## SlaterB (28. Apr 2008)

gizmo hat gesagt.:
			
		

> Wir haben wohl einfach eine andere Priorisierung. Mir ist Lesbarkeit, Erweiterbarkeit, Skalierbarkeit wichtiger, als das letzte Quäntchen Performance.


solche Dinge sind für lebendigen Code relevant, für Programmlogik, Frameworks usw,
nicht für irgendeine versteckte statische Hilfsoperation,
wer schaut schon jemals in Math oder Integer rein, wie dort irgendwelche Standard-Funktionen definiert sind?

Operation x soll die Länge liefern und gut, niemand wird je diesen Code lesen solande nicht ein Fehler auftritt, 
nie wird er geändert durch neue Anforderungen/ Technik/ Stil/ Framework oder sonstwas, nichts zu erweitern oder skalieren,
aber ausgeführt wird er zig tausend Mal

edit: ach doch, eine Möglichkeit gibt es dorthin zu kommen: man merkt wie langsam der Code ist und optimiert  ,
ok wenig realistisch bei so einer Operation, aber noch die wahrscheinlichste Variante

natürlich ist das keine Entschuldigung für den gröbste Wirrwarr aus Schleifen, Verzweigungen und Sprüngen,
aber wenns nur ein aufgedröselter Code mit einheitlich leichter Struktur ist, dann kann man kaum meckern,
Länge an sich schadet nicht, Festplatten sind billig



> Vielleicht stehe ich bloss auf dem Schlauch, aber ich sehe nicht, wie man eine allgemeingültige binarySearch Methode schreiben könnte, an welche die anderen Methoden weiterdelegieren.


wieso sollte es auch, dafür gibts doch verschiedene?
falls du meinen Satz 'in diesem Fall nicht nötig' meinst: ich meinte für die Länge reicht eine Operation für long, int und co verweisen darauf


----------



## Leroy42 (29. Apr 2008)

Also ihr habt Probleme....  ???:L


----------



## Templarthelast (27. Jun 2012)

Was ist denn mit: 


```
int i = 2542495035234324;
String s = i;
System.out.println(s.length());
```

Dabei muss man ja noch nichteinmal mögliche Nachkommastellen beachten.


----------



## TR (27. Jun 2012)

1. Alter Thread.
2. int und long mit Nachkommerstellen? ja nee ist klar
3. als ich den thread titel gelesen habe, habe ich mal zuerst in die klasse integer geguckt:

```
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                      99999999, 999999999, Integer.MAX_VALUE };

    // Requires positive x
    static int stringSize(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }
```

Danach noch in die Klasse Long

```
// Requires positive x
    static int stringSize(long x) {
        long p = 10;
        for (int i=1; i<19; i++) {
            if (x < p)
                return i;
            p = 10*p;
        }
        return 19;
    }
```

Warum nicht so?!


----------

