Länge eines Integers ermitteln?

  • Themenstarter Themenstarter Guest
  • Beginndatum Beginndatum
Status
Nicht offen für weitere Antworten.
G

Guest

Gast
Hallo Leute,

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

Die naive Variante, die jedoch zu langsam ist wäre diese:
Code: 
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?
 
Nach Datum sortieren Nach Zustimmungen sortieren
Nun ja,

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

usw.
 
Zustimmen 0
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?
 
Zustimmen 0
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? 😉
 
Zustimmen 0
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
 
Zustimmen 0
Keine Ahnung, wie es mit der Geschwindigkeit aussieht, aber wie wäre es denn mit Rekursion?

Code: 
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;
}
 
Zustimmen 0
@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!
 
Zustimmen 0
Code: 
int c = 1;
        
        while((k /= 10) != 0) {
            c++;
        }
k deine zahl und c dann die 'laenge' der zahl
 
Zustimmen 0
Code: 
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);
    }
}
 
Zustimmen 0
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?
 
Zustimmen 0
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
 
Zustimmen 0
gizmo hat gesagt.:
Code: 
public class Test {
...
        double d = Math.log(z)/Math.log(10);
        int i = (int) d + 1;

}
Zum Vergrößern anklicken....

: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...)
 
Zustimmen 0
Ist das mit dem Logarithmus nicht ein bisschen riskant - aufgrund der Ungenauigkeit in der Gleitkommaarithmetik?
 
Zustimmen 0
interessant ist letztlich ja auch, wie dieser Vierkampf ausgeht 😉

Code: 
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
 
Zustimmen 0
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.
 
Zustimmen 0
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
Code: 
                public int calc(int i)
                {
                    return (int)Math.log10(i) + 1;
                }
schreiben kann, und wenn es Zeitkritisch ist "notgedrungen" auf sowas wie
Code: 
                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....
 
Zustimmen 0
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 😉
 
Zustimmen 0
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.
 
Zustimmen 0
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
 
Zustimmen 0
Ich schlage vor:
Code: 
                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?
 
Zustimmen 0
@SlaterB: Wenn man k mal auf Integer.MAX_VALUE/2 setzt, das if Entsprechend erweitert, und die Schleife
Code: 
        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....
 
Zustimmen 0
@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.
 
Zustimmen 0
@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.
static int binarySearch(char[] a, char key)
Searches the specified array of chars for the specified value using the binary search algorithm.
static int binarySearch(char[] a, int fromIndex, int toIndex, char key)
Searches a range of the specified array of chars for the specified value using the binary search algorithm.
static int binarySearch(double[] a, double key)
Searches the specified array of doubles for the specified value using the binary search algorithm.
static int binarySearch(double[] a, int fromIndex, int toIndex, double key)
Searches a range of the specified array of doubles for the specified value using the binary search algorithm.
static int binarySearch(float[] a, float key)
Searches the specified array of floats for the specified value using the binary search algorithm.
static int binarySearch(float[] a, int fromIndex, int toIndex, float key)
Searches a range of the specified array of floats for the specified value using the binary search algorithm.
static int binarySearch(int[] a, int key)
Searches the specified array of ints for the specified value using the binary search algorithm.
static int binarySearch(int[] a, int fromIndex, int toIndex, int key)
Searches a range of the specified array of ints for the specified value using the binary search algorithm.
static int binarySearch(long[] a, int fromIndex, int toIndex, long key)
Searches a range of the specified array of longs for the specified value using the binary search algorithm.
static int binarySearch(long[] a, long key)
Searches the specified array of longs for the specified value using the binary search algorithm.
static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key)
Searches a range of the specified array for the specified object using the binary search algorithm.
static int binarySearch(Object[] a, Object key)
Searches the specified array for the specified object using the binary search algorithm.
static int binarySearch(short[] a, int fromIndex, int toIndex, short key)
Searches a range of the specified array of shorts for the specified value using the binary search algorithm.
static int binarySearch(short[] a, short key)
Searches the specified array of shorts for the specified value using the binary search algorithm.
static <T> int
binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
Searches a range of the specified array for the specified object using the binary search algorithm.
static <T> int
binarySearch(T[] a, T key, Comparator<? super T> c)
Searches the specified array for the specified object using the binary search algorithm.
Zum Vergrößern anklicken....
😉


die Operation müsste hier ja letztlich nur einmal für long geschrieben werden, wenn man es erstmals braucht,
die anderen verweisen dann darauf
 
Zustimmen 0
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,
Zum Vergrößern anklicken....
Dann mach mir doch bitte ein Beispiel, wo es in Java Sinn macht, Code zu duplizieren.
 
Zustimmen 0
SlaterB hat gesagt.:
9stellige machen natürlich von Natur aus mindestens 90% aus, da passt das gut
Zum Vergrößern anklicken....
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.
 
Zustimmen 0
gizmo hat gesagt.:
Dann mach mir doch bitte ein Beispiel, wo es in Java Sinn macht, Code zu duplizieren.
Zum Vergrößern anklicken....
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 😉
 
Zustimmen 0
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.
 
Zustimmen 0
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
 
Zustimmen 0
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.
 
Zustimmen 0
gizmo hat gesagt.:
Wir haben wohl einfach eine andere Priorisierung. Mir ist Lesbarkeit, Erweiterbarkeit, Skalierbarkeit wichtiger, als das letzte Quäntchen Performance.
Zum Vergrößern anklicken....
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.
Zum Vergrößern anklicken....
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
 
Zustimmen 0
Was ist denn mit:

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

Dabei muss man ja noch nichteinmal mögliche Nachkommastellen beachten.
 
Zustimmen 0
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:
Java: 
    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
Java: 
    // 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?!
 
Zustimmen 0
Status
Nicht offen für weitere Antworten.

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Länge/Anzahl der Stellen eines Integers
Antworten: 8
Maximal und Minimalgröße eines Integers
Antworten: 3
Array auf Vorkommen eines Integers überprüfen
Antworten: 2
seltenes Vorkommen eines Integers in einem Array
Antworten: 13
maximaler Wert eines Integers
Antworten: 14

Zurück
Oben