Ich denke, er möchte die Ziffern in der Zahl zählen.
Alberto Zaccagni
3
Die Antworten, die die Leute Ihnen geben, sind richtig ... sie geben Ihnen die Länge Ihres int an, ohne es in eine Zeichenfolge umzuwandeln ... aber warum möchten Sie es nicht in eine Zeichenfolge konvertieren? Ist es eine Geschwindigkeitssache? Wenn ja, bin ich nicht davon überzeugt, dass diese Methoden schneller sein werden ... vielleicht möchten Sie einige Tests durchführen (oder entscheiden, ob es überhaupt darauf ankommt)
Beska
3
@ptomli hexadezimale Ziffern sind immer noch Ziffern, nur in einem anderen Basissystem.
Mark Pim
2
@Ptomli Sicher, aber sowohl in der Integer.toString-Funktion als auch in der allgemeinen Konversation ist die Dezimalzahl die Standardeinstellung. Wenn die Bank mir sagt: "Schreiben Sie den Betrag Ihres Schecks in dieses Feld", frage ich sie nicht, ob ich ihn in Dezimal, Hex oder Oktal schreiben soll. Wir gehen von einer Dezimalzahl aus, sofern im Kontext nichts anderes angegeben oder gefordert ist.
Jay
Antworten:
349
Ihre String-basierte Lösung ist vollkommen in Ordnung, es gibt nichts "Unordentliches". Sie müssen erkennen, dass Zahlen mathematisch gesehen weder eine Länge noch Ziffern haben. Länge und Ziffern sind beide Eigenschaften einer physischen Darstellung einer Zahl in einer bestimmten Basis, dh einer Zeichenfolge.
Eine logarithmusbasierte Lösung macht (einige) die gleichen Dinge wie die String-basierte intern und wahrscheinlich (unwesentlich) schneller, weil sie nur die Länge erzeugt und die Ziffern ignoriert. Aber ich würde es nicht als klarer in der Absicht betrachten - und das ist der wichtigste Faktor.
+1 für die Absicht des Codes bei der Auswahl eines Weges zur Lösung eines Problems zu
berücksichtigen
5
Datenpunkt: Auf meinem Computer scheint die Protokollmethode knapp doppelt so schnell zu laufen wie die Methoden für die Zeichenfolgenlänge. Ich würde das nicht als unbedeutend bezeichnen, wenn die Methode häufig oder in einem zeitkritischen Codeabschnitt aufgerufen wird.
CPerkins
1
Siehe meinen Benchmark-Unit-Test unten (der möglicherweise auch fehlerhaft ist, ich bin kein Benchmark-Experte). Bei einer großen Anzahl von Läufen (100 000 000) beträgt die Geschwindigkeit auf meiner Maschine 11 bis 8 Sekunden und ist kaum doppelt so hoch.
Jean
5
@ CPerkins. Vorzeitige Optimierung. Du kennst das Spiel.
Michael Borgwardt
11
Einige (ziemlich späte) Ergänzungen: Es funktioniert möglicherweise nicht richtig für negative Werte, je nachdem, ob Sie erwarten, dass das "-" eine Ziffer ist oder nicht. Durch Hinzufügen Math.abs()wird dies jedoch behoben.
Und ist das schneller oder besser als mit meiner Variante?
Am
+1 Du hast mich um eine Sekunde geschlagen und deine Antwort war richtig, wo meine leicht abweicht. Beachten Sie jedoch, dass sich der Compiler aufgrund einer fehlenden Besetzung von int
Dirk
2
@ Tom Warum sollten Sie annehmen, dass es teuer ist? Man könnte annehmen, dass der mathematische Co-Prozessor es ausführen würde, so dass es nahe an der Geschwindigkeit einer Addition liegen könnte. Selbst wenn Java den Co-Prozessor jetzt nicht verwendet, ist es eine gute Annahme, dass es ... (Wir werden Ihre noch ungebildete Implikation, dass Java langsam ist, einfach ignorieren, weil Sie wahrscheinlich nicht an Beweisen interessiert sind - oder wenn Sie wäre , würde Sie gehen shootout.alioth.debian.org und für sich selbst herausfinden)
Bill K
8
Funktioniert ... es sei denn, der Wert, den Sie überprüfen, ist = 0, was zu ungeraden Ergebnissen führt (-2147483647). Math.log10 API: "Wenn das Argument eine positive Null oder eine negative Null ist, ist das Ergebnis eine negative Unendlichkeit."
Mujimu
2
+1 Präsentation einer Methode ohne Objektspeicherzuweisungen. Dies ist ein Muss, um die Wiederverwendung zu maximieren und GC-Sammlungen zu vermeiden.
Michael Wojcik
159
Der schnellste Ansatz: Teilen und Erobern.
Angenommen, Ihr Bereich liegt zwischen 0 und MAX_INT, dann haben Sie 1 bis 10 Stellen. Sie können dieses Intervall mit Teilen und Erobern mit bis zu 4 Vergleichen pro Eingabe erreichen. Zuerst teilen Sie [1..10] mit einem Vergleich in [1..5] und [6..10], und dann teilen Sie jedes Intervall der Länge 5 mit einem Vergleich in ein Intervall der Länge 3 und 2. Das Intervall der Länge 2 erfordert einen weiteren Vergleich (insgesamt 3 Vergleiche), das Intervall der Länge 3 kann in ein Intervall der Länge 1 (Lösung) und ein Intervall der Länge 2 unterteilt werden. Sie benötigen also 3 oder 4 Vergleiche.
Keine Divisionen, keine Gleitkommaoperationen, keine teuren Logarithmen, nur ganzzahlige Vergleiche.
Code (lang aber schnell):
if(n <100000){// 5 or lessif(n <100){// 1 or 2if(n <10)return1;elsereturn2;}else{// 3 or 4 or 5if(n <1000)return3;else{// 4 or 5if(n <10000)return4;elsereturn5;}}}else{// 6 or moreif(n <10000000){// 6 or 7if(n <1000000)return6;elsereturn7;}else{// 8 to 10if(n <100000000)return8;else{// 9 or 10if(n <1000000000)return9;elsereturn10;}}}
Benchmark (nach dem Aufwärmen der JVM) - Sehen Sie sich den folgenden Code an, um zu sehen, wie der Benchmark ausgeführt wurde:
Basismethode (mit String.length): 2145 ms
log10-Methode: 711 ms = 3,02-mal so schnell wie die Basislinie
wiederholte Teilung: 2797 ms = 0,77-mal so schnell wie die Grundlinie
Teilen und Erobern: 74 ms = 28,99-
mal so schnell wie die Grundlinie
Vollständiger Code:
publicstaticvoid main(String[] args)throwsException{// validate methods:for(int i =0; i <1000; i++)if(method1(i)!= method2(i))System.out.println(i);for(int i =0; i <1000; i++)if(method1(i)!= method3(i))System.out.println(i +" "+ method1(i)+" "+ method3(i));for(int i =333; i <2000000000; i +=1000)if(method1(i)!= method3(i))System.out.println(i +" "+ method1(i)+" "+ method3(i));for(int i =0; i <1000; i++)if(method1(i)!= method4(i))System.out.println(i +" "+ method1(i)+" "+ method4(i));for(int i =333; i <2000000000; i +=1000)if(method1(i)!= method4(i))System.out.println(i +" "+ method1(i)+" "+ method4(i));// work-up the JVM - make sure everything will be run in hot-spot mode
allMethod1();
allMethod2();
allMethod3();
allMethod4();// run benchmarkChronometer c;
c =newChronometer(true);
allMethod1();
c.stop();long baseline = c.getValue();System.out.println(c);
c =newChronometer(true);
allMethod2();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");
c =newChronometer(true);
allMethod3();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");
c =newChronometer(true);
allMethod4();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");}privatestaticint method1(int n){returnInteger.toString(n).length();}privatestaticint method2(int n){if(n ==0)return1;return(int)(Math.log10(n)+1);}privatestaticint method3(int n){if(n ==0)return1;int l;for(l =0; n >0;++l)
n /=10;return l;}privatestaticint method4(int n){if(n <100000){// 5 or lessif(n <100){// 1 or 2if(n <10)return1;elsereturn2;}else{// 3 or 4 or 5if(n <1000)return3;else{// 4 or 5if(n <10000)return4;elsereturn5;}}}else{// 6 or moreif(n <10000000){// 6 or 7if(n <1000000)return6;elsereturn7;}else{// 8 to 10if(n <100000000)return8;else{// 9 or 10if(n <1000000000)return9;elsereturn10;}}}}privatestaticint allMethod1(){int x =0;for(int i =0; i <1000; i++)
x = method1(i);for(int i =1000; i <100000; i +=10)
x = method1(i);for(int i =100000; i <1000000; i +=100)
x = method1(i);for(int i =1000000; i <2000000000; i +=200)
x = method1(i);return x;}privatestaticint allMethod2(){int x =0;for(int i =0; i <1000; i++)
x = method2(i);for(int i =1000; i <100000; i +=10)
x = method2(i);for(int i =100000; i <1000000; i +=100)
x = method2(i);for(int i =1000000; i <2000000000; i +=200)
x = method2(i);return x;}privatestaticint allMethod3(){int x =0;for(int i =0; i <1000; i++)
x = method3(i);for(int i =1000; i <100000; i +=10)
x = method3(i);for(int i =100000; i <1000000; i +=100)
x = method3(i);for(int i =1000000; i <2000000000; i +=200)
x = method3(i);return x;}privatestaticint allMethod4(){int x =0;for(int i =0; i <1000; i++)
x = method4(i);for(int i =1000; i <100000; i +=10)
x = method4(i);for(int i =100000; i <1000000; i +=100)
x = method4(i);for(int i =1000000; i <2000000000; i +=200)
x = method4(i);return x;}
Wieder Benchmark:
Basismethode (mit String.length): 2145 ms
log10-Methode: 711 ms = 3,02-mal so schnell wie die Basislinie
wiederholte Teilung: 2797 ms = 0,77-mal so schnell wie die Grundlinie
Teilen und Erobern: 74 ms = 28,99-
mal so schnell wie die Grundlinie
Bearbeiten:
Nachdem ich den Benchmark geschrieben hatte, nahm ich einen kleinen Einblick in Integer.toString von Java 6 und stellte fest, dass es Folgendes verwendet:
das sieht gut aus Sie könnten es mit dem Operator ?: etwas kompakter schreiben, um mehr Akzeptanz zu erhalten
André Pareis
88
Sprechen Sie über vorzeitige Optimierung: D
Gordon Gustafson
2
Ich mag das! Wie wäre es mit einem Switch-Block anstelle von so verschachtelten If-Elses?
Kebman
2
Ich wusste nicht, dass all diese Anweisungen SO viel schneller wären, als das int in String zu konvertieren und dann .length aufzurufen. +1
Ogen
15
Mit dem ternären Operator werden 101 Zeichen erreicht:n<100000?n<100?n<10?1:2:n<1000?3:n<10000?4:5:n<10000000?n<1000000?6:7:n<100000000?8:n<1000000000?9:10
Jonathan Gawrych
13
Zwei Kommentare zu Ihrem Benchmark: Java ist eine komplexe Umgebung, was mit Just-in-Time-Kompilierung und Garbage Collection usw. zu tun hat. Um einen fairen Vergleich zu erhalten, wenn ich einen Benchmark durchführe, schließe ich immer: (a) die beiden Tests ein in einer Schleife, die sie 5 oder 10 Mal nacheinander ausführt. Sehr oft unterscheidet sich die Laufzeit beim zweiten Durchlauf durch die Schleife erheblich von der ersten. Und (b) Nach jedem "Ansatz" mache ich ein System.gc (), um zu versuchen, eine Garbage Collection auszulösen. Andernfalls generiert der erste Ansatz möglicherweise eine Reihe von Objekten, die jedoch nicht ausreichen, um eine Speicherbereinigung zu erzwingen. Der zweite Ansatz erstellt dann einige Objekte, der Heap ist erschöpft und die Speicherbereinigung wird ausgeführt. Dann wird der zweite Ansatz "aufgeladen", um den vom ersten Ansatz hinterlassenen Müll aufzunehmen. Sehr unfair!
Trotzdem hat keiner der oben genannten Punkte in diesem Beispiel einen signifikanten Unterschied gemacht.
Mit oder ohne diese Änderungen habe ich ganz andere Ergebnisse erzielt als Sie. Als ich dies ausführte, gab der toString-Ansatz Laufzeiten von 6400 bis 6600 Millis an, während der Log-Ansatz 20.000 bis 20.400 Millis überstieg. Anstatt etwas schneller zu sein, war der Log-Ansatz für mich dreimal langsamer.
Beachten Sie, dass die beiden Ansätze sehr unterschiedliche Kosten verursachen, sodass dies nicht völlig schockierend ist: Der toString-Ansatz erstellt viele temporäre Objekte, die bereinigt werden müssen, während der Protokollansatz eine intensivere Berechnung erfordert. Vielleicht besteht der Unterschied darin, dass toString auf einem Computer mit weniger Speicher mehr Speicherbereinigungsrunden erfordert, während auf einem Computer mit einem langsameren Prozessor die zusätzliche Berechnung des Protokolls schmerzhafter wäre.
Ich habe auch einen dritten Ansatz versucht. Ich habe diese kleine Funktion geschrieben:
Das lief zwischen 1600 und 1900 Millis - weniger als 1/3 des toString-Ansatzes und 1/10 des Log-Ansatzes auf meinem Computer.
Wenn Sie über ein breites Spektrum an Zahlen verfügen, können Sie diese weiter beschleunigen, indem Sie zunächst durch 1.000 oder 1.000.000 dividieren, um die Anzahl der Durchgänge durch die Schleife zu verringern. Damit habe ich nicht gespielt.
Haben Sie versucht, die Eingabe zu variieren? Die Hotspot-VM könnte dieses Diagramm andernfalls optimieren, was zu falschen Benchmarks führt, da jedes Mal dasselbe vorberechnete Element zurückgegeben wird.
Erik Aigner
11
Verwenden von Java
int nDigits =Math.floor(Math.log10(Math.abs(the_integer)))+1;
Cool. aber ich denke es braucht abs (nummer) und auch "0" ist auch ein Sonderfall?
DmitryK
Ja. Wenn Sie das Zeichen berücksichtigen müssen, müssen Sie etwas wie 1 + (int) Math.floor (Math.log10 (Math.abs (Nummer))) + ((Nummer <0)? 1: 0)
Dirk
5
Das Math.floorist ein bisschen überflüssig, nicht wahr? Casting to intwird es trotzdem abrunden.
CompuChip
5
Marians Lösung für lange Typennummern (bis zu 9.223.372.036.854.775.807), falls jemand sie kopieren und einfügen möchte. In dem Programm, das ich für Zahlen geschrieben habe, waren bis zu 10000 viel wahrscheinlicher, also habe ich einen bestimmten Zweig für sie gemacht. Auf jeden Fall wird es keinen signifikanten Unterschied machen.
publicstaticint numberOfDigits (long n){// Guessing 4 digit numbers will be more probable.// They are set in the first branch.if(n <10000L){// from 1 to 4if(n <100L){// 1 or 2if(n <10L){return1;}else{return2;}}else{// 3 or 4if(n <1000L){return3;}else{return4;}}}else{// from 5 a 20 (albeit longs can't have more than 18 or 19)if(n <1000000000000L){// from 5 to 12if(n <100000000L){// from 5 to 8if(n <1000000L){// 5 or 6if(n <100000L){return5;}else{return6;}}else{// 7 u 8if(n <10000000L){return7;}else{return8;}}}else{// from 9 to 12if(n <10000000000L){// 9 or 10if(n <1000000000L){return9;}else{return10;}}else{// 11 or 12if(n <100000000000L){return11;}else{return12;}}}}else{// from 13 to ... (18 or 20)if(n <10000000000000000L){// from 13 to 16if(n <100000000000000L){// 13 or 14if(n <10000000000000L){return13;}else{return14;}}else{// 15 or 16if(n <1000000000000000L){return15;}else{return16;}}}else{// from 17 to ...¿20?if(n <1000000000000000000L){// 17 or 18if(n <100000000000000000L){return17;}else{return18;}}else{// 19? Can it be?// 10000000000000000000L is'nt a valid long.return19;}}}}}
Funktioniert nur für positive Ganzzahlen nund Null. Kann verwendet werden ("" + Math.abs(n)).length(), um die Länge einer negativen Ganzzahl zu ermitteln.
Hast du es getestet? Sie wissen, dass es, auch wenn es aus menschlicher Sicht sinnvoll ist, mit der "Denkweise" der Maschine nicht so funktioniert, oder? --- Lassen Sie mich eines vorschlagen: Erstellen Sie ein Array mit zwei Millionen Zahlen, vorzugsweise Long.MAX_VALUEdem Fall mit der schlimmsten Komplexität Ihres Codes, und System.nanoTime()führen Sie einen Taktversuch gegen die Fälle mit der schlimmsten Komplexität der anderen Lösung durch. ++ Versuchen Sie es tatsächlich mit einem Array, das mit einem Zufallsgenerator gefüllt ist, der auf den Bereich von 0bis eingestellt Long.MAX_VALUEist, nur für den Test der "durchschnittlichen Komplexität". ++ Sie finden die Ergebnisse möglicherweise ... sehr schockierend.
XenoRo
@thelima Dies funktioniert nicht richtig für Null oder Negative, aber das ist ein kleiner Fehler. Das Prinzip sieht für mich richtig aus. Auf welches "schockierende" Ergebnis beziehen Sie sich?
Jay
Sagen wir einfach, dass Computer ... Nun ... sie teilen sich nicht gern. Und in Fällen, in denen große "Warteschlangen" mit großen Zahlen verarbeitet werden müssen und jede Ziffer in jeder verarbeiteten Zahl eine Unterteilung erfordert ... Nun ... Dinge "werden sehr langsam, sehr schnell" ... Wenn Sie meine fangen Bedeutung ... --- Aus diesem Grund sehen Sie viele der Antworten hier mit Codes, die auf Test und Vergleich mit jeder Dezimalstelle basieren, wobei 'if's' anstelle von Divisionen verwendet werden: Wenn es nicht schneller ist, behält es zumindest den größten Teil seiner Geschwindigkeit bei von seinen schlimmsten Fällen. --- Machen Sie einen Test zwischen der Verwendung von Divisionen und Logarithmus auf großen Zahlen ...
XenoRo
@ TheLima wovon redest du? Für eine wird int,diese Schleife maximal 11 Mal ausgeführt. Haben Sie Beweise für Ihre Behauptungen?
Marquis von Lorne
@EJP Aus Hardware-Sicht ist die Division ein iterativer Prozess. Der schnellste mir bekannte Divisionsalgorithmus ist radix4, der 4 Bits pro Iteration generiert. Eine 32-Bit-Teilung benötigt also mindestens 8 Iterationen. Multiplikationen können beispielsweise parallel durchgeführt und auch in einfachere Multiplikationen unterteilt werden. entweder bis auf Bitebene (erfordert nur 5 Operationen) oder mit teilweiser Aufschlüsselung plus einer Nachschlagetabelle am Ende (Kompromiss zwischen klassischer Größe und Geschwindigkeit). Es geht nicht nur darum, "wie viele Iterationen"; Das Problem mit Divisionen liegt darin, "was jede Iteration auf Hardwareebene impliziert / tut"
Jetzt muss ich mich fragen, ob mein Benchmark tatsächlich etwas bedeutet, aber ich erhalte konsistente Ergebnisse (Variationen innerhalb einer ms) über mehrere Läufe des Benchmarks selbst ... :) Es sieht so aus, als wäre es sinnlos, dies zu optimieren ...
edit: Nach dem Kommentar von ptomli habe ich im obigen Code 'number' durch 'i' ersetzt und über 5 Läufe der Bank die folgenden Ergebnisse erhalten:
Ich würde eine einfache Zeile für eine Schleife mit einem leeren Körper nicht einfach nennen. Noch modulo eine Potenz von 10, um zu sehen, ob Sie das Gleiche zurückbekommen (können Sie nicht einfach einen Vergleich verwenden?).
Teepeemm
0
Oder stattdessen die Länge, die Sie überprüfen können, ob die Zahl größer oder kleiner als die gewünschte Zahl ist.
publicvoid createCard(int cardNumber,int cardStatus,int customerId)throwsSQLException{if(cardDao.checkIfCardExists(cardNumber)==false){if(cardDao.createCard(cardNumber, cardStatus, customerId)==true){System.out.println("Card created successfully");}else{}}else{System.out.println("Card already exists, try with another Card Number");do{System.out.println("Enter your new Card Number: ");
scan =newScanner(System.in);int inputCardNumber = scan.nextInt();
cardNumber = inputCardNumber;}while(cardNumber <95000000);
cardDao.createCard(cardNumber, cardStatus, customerId);}}
Ich verstehe nicht Anscheinend beantworten Sie eine andere Frage.
Teepeemm
0
Ich habe noch keine multiplikationsbasierte Lösung gesehen. Logarithmus-, Divison- und String-basierte Lösungen werden für Millionen von Testfällen ziemlich unhandlich. Hier ist eine für ints:
/**
* Returns the number of digits needed to represents an {@code int} value in
* the given radix, disregarding any sign.
*/publicstaticint len(int n,int radix){
radixCheck(radix);// if you want to establish some limitation other than radix > 2
n =Math.abs(n);int len =1;long min = radix -1;while(n > min){
n -= min;
min *= radix;
len++;}return len;}
In Basis 10 funktioniert dies, weil n im Wesentlichen mit 9, 99, 999 verglichen wird ... da min 9, 90, 900 ... ist und n von 9, 90, 900 ... subtrahiert wird.
Leider ist dies nicht longnur durch Ersetzen jeder Instanz intaufgrund von Überlauf portierbar . Auf der anderen Seite, es passiert einfach so , es wird für Basen arbeitet 2 und 10 (aber nicht schlecht für die meisten anderen Basen). Sie benötigen eine Nachschlagetabelle für die Überlaufpunkte (oder einen Teilungstest ... ew)
/**
* For radices 2 &le r &le Character.MAX_VALUE (36)
*/privatestaticlong[] overflowpt ={-1,-1,4611686018427387904L,8105110306037952534L,3458764513820540928L,5960464477539062500L,3948651115268014080L,3351275184499704042L,8070450532247928832L,1200757082375992968L,9000000000000000000L,5054470284992937710L,2033726847845400576L,7984999310198158092L,2022385242251558912L,6130514465332031250L,1080863910568919040L,2694045224950414864L,6371827248895377408L,756953702320627062L,1556480000000000000L,3089447554782389220L,5939011215544737792L,482121737504447062L,839967991029301248L,1430511474609375000L,2385723916542054400L,3902460517721977146L,6269893157408735232L,341614273439763212L,513726300000000000L,762254306892144930L,1116892707587883008L,1617347408439258144L,2316231840055068672L,3282671350683593750L,4606759634479349760L};publicstaticint len(long n,int radix){
radixCheck(radix);
n = abs(n);int len =1;long min = radix -1;while(n > min){
len++;if(min == overflowpt[radix])break;
n -= min;
min *= radix;}return len;}
Mit Design (basierend auf dem Problem). Dies ist eine Alternative von Teilen und Erobern. Wir definieren zuerst eine Aufzählung (wenn man bedenkt, dass es sich nur um ein Int ohne Vorzeichen handelt).
Ein Teilen und Erobern würde in der Mitte beginnen und den verbleibenden Suchbereich halbieren. Dies hat eine lineare Laufzeit. Aber es spielt keine Rolle für nur 9 Vergleiche. Aber wird das nicht durcheinander bringen, wenn num>=Nine.getValue()?
Teepeemm
0
Man möchte dies meistens tun, weil man es "präsentieren" möchte, was meistens bedeutet, dass es schließlich explizit oder implizit "toString-ed" (oder auf andere Weise transformiert) werden muss; bevor es präsentiert werden kann (zum Beispiel gedruckt).
Wenn dies der Fall ist, versuchen Sie einfach, den erforderlichen "toString" explizit zu machen und die Bits zu zählen.
Ich sehe Leute, die String-Bibliotheken oder sogar die Integer-Klasse verwenden. Daran ist nichts auszusetzen, aber der Algorithmus zum Abrufen der Anzahl der Ziffern ist nicht so kompliziert. Ich verwende in diesem Beispiel ein Long, aber es funktioniert genauso gut mit einem Int.
privatestaticint getLength(long num){int count =1;while(num >=10){
num = num /10;
count++;}return count;}
Keine String-API, keine Utils, keine Typkonvertierung, nur reine Java-Iteration ->
publicstaticint getNumberOfDigits(int input){int numOfDigits =1;int base =1;while(input >= base *10){
base = base *10;
numOfDigits++;}return numOfDigits;}
Wenn Sie möchten, können Sie sich nach größeren Werten sehnen.
Sie sollten es dann wahrscheinlich testen (und sicherstellen, dass es gültiges Java und richtig formatiert ist). Ein rekursiver "Division durch 10" -Ansatz wurde jedoch vor 3 Jahren von Jedi Dula veröffentlicht.
Teepeemm
-2
Sie könnten die Ziffern durch sukzessive Division durch zehn:
int a=0;if(no <0){
no =-no;}elseif(no ==0){
no =1;}while(no >0){
no = no /10;
a++;}System.out.println("Number of digits in given number is: "+a);
Ein "Divide by 10" -Ansatz wurde erstmals vor 3 Jahren von Sinista veröffentlicht. Das ist der einzige Grund, warum ich mir vorstellen kann, dass Sie eine Ablehnung erhalten haben.
Teepeemm
-2
Geben Sie die Nummer ein und erstellen Sie eine Arraylist, und die while-Schleife zeichnet alle Ziffern in der auf Arraylist. Dann können wir die Größe des Arrays herausnehmen, die der Länge des von Ihnen eingegebenen ganzzahligen Werts entspricht.
ArrayList<Integer> a=newArrayList<>();while(number >0){
remainder = num %10;
a.add(remainder);
number = number /10;}int m=a.size();
Die Art und Weise, wie es mit der Zahlenzählervariablen funktioniert, ist, dass 10 = 1 stelliges Leerzeichen. Zum Beispiel .1 = 1 Zehntel => 1 Stellen. Wenn Sie also haben, erhalten int number = 103342;Sie 6, da dies das Äquivalent von .000001 Leerzeichen zurück ist. Hat jemand einen besseren Variablennamen fürnumberCounter ? Ich kann mir nichts Besseres vorstellen.
Edit: Ich dachte nur an eine bessere Erklärung. Im Wesentlichen bewirkt diese while-Schleife, dass Sie Ihre Zahl durch 10 teilen, bis sie kleiner als eins ist. Wenn Sie etwas durch 10 teilen, verschieben Sie es im Wesentlichen um ein Zahlenfeld zurück. Teilen Sie es also einfach durch 10, bis Sie <1 für die Anzahl der Stellen in Ihrer Zahl erreichen.
Hier ist eine andere Version, die die Anzahl der Zahlen in Dezimalzahlen zählen kann:
Versuchen Sie, das int in eine Zeichenfolge zu konvertieren , und ermitteln Sie dann die Länge der Zeichenfolge . Das sollte die Länge des int bekommen .
publicstaticint intLength(int num){String n =Integer.toString(num);int newNum = n.length();return newNum;}
Antworten:
Ihre String-basierte Lösung ist vollkommen in Ordnung, es gibt nichts "Unordentliches". Sie müssen erkennen, dass Zahlen mathematisch gesehen weder eine Länge noch Ziffern haben. Länge und Ziffern sind beide Eigenschaften einer physischen Darstellung einer Zahl in einer bestimmten Basis, dh einer Zeichenfolge.
Eine logarithmusbasierte Lösung macht (einige) die gleichen Dinge wie die String-basierte intern und wahrscheinlich (unwesentlich) schneller, weil sie nur die Länge erzeugt und die Ziffern ignoriert. Aber ich würde es nicht als klarer in der Absicht betrachten - und das ist der wichtigste Faktor.
quelle
Math.abs()
wird dies jedoch behoben.Der Logarithmus ist dein Freund:
NB: nur gültig für n> 0.
quelle
Der schnellste Ansatz: Teilen und Erobern.
Angenommen, Ihr Bereich liegt zwischen 0 und MAX_INT, dann haben Sie 1 bis 10 Stellen. Sie können dieses Intervall mit Teilen und Erobern mit bis zu 4 Vergleichen pro Eingabe erreichen. Zuerst teilen Sie [1..10] mit einem Vergleich in [1..5] und [6..10], und dann teilen Sie jedes Intervall der Länge 5 mit einem Vergleich in ein Intervall der Länge 3 und 2. Das Intervall der Länge 2 erfordert einen weiteren Vergleich (insgesamt 3 Vergleiche), das Intervall der Länge 3 kann in ein Intervall der Länge 1 (Lösung) und ein Intervall der Länge 2 unterteilt werden. Sie benötigen also 3 oder 4 Vergleiche.
Keine Divisionen, keine Gleitkommaoperationen, keine teuren Logarithmen, nur ganzzahlige Vergleiche.
Code (lang aber schnell):
Benchmark (nach dem Aufwärmen der JVM) - Sehen Sie sich den folgenden Code an, um zu sehen, wie der Benchmark ausgeführt wurde:
mal so schnell wie die Grundlinie
Vollständiger Code:
Wieder Benchmark:
mal so schnell wie die Grundlinie
Bearbeiten: Nachdem ich den Benchmark geschrieben hatte, nahm ich einen kleinen Einblick in Integer.toString von Java 6 und stellte fest, dass es Folgendes verwendet:
Ich habe es mit meiner Divide-and-Conquer-Lösung verglichen:
Meins ist ungefähr 4x so schnell wie die Java 6-Lösung.
quelle
n<100000?n<100?n<10?1:2:n<1000?3:n<10000?4:5:n<10000000?n<1000000?6:7:n<100000000?8:n<1000000000?9:10
Zwei Kommentare zu Ihrem Benchmark: Java ist eine komplexe Umgebung, was mit Just-in-Time-Kompilierung und Garbage Collection usw. zu tun hat. Um einen fairen Vergleich zu erhalten, wenn ich einen Benchmark durchführe, schließe ich immer: (a) die beiden Tests ein in einer Schleife, die sie 5 oder 10 Mal nacheinander ausführt. Sehr oft unterscheidet sich die Laufzeit beim zweiten Durchlauf durch die Schleife erheblich von der ersten. Und (b) Nach jedem "Ansatz" mache ich ein System.gc (), um zu versuchen, eine Garbage Collection auszulösen. Andernfalls generiert der erste Ansatz möglicherweise eine Reihe von Objekten, die jedoch nicht ausreichen, um eine Speicherbereinigung zu erzwingen. Der zweite Ansatz erstellt dann einige Objekte, der Heap ist erschöpft und die Speicherbereinigung wird ausgeführt. Dann wird der zweite Ansatz "aufgeladen", um den vom ersten Ansatz hinterlassenen Müll aufzunehmen. Sehr unfair!
Trotzdem hat keiner der oben genannten Punkte in diesem Beispiel einen signifikanten Unterschied gemacht.
Mit oder ohne diese Änderungen habe ich ganz andere Ergebnisse erzielt als Sie. Als ich dies ausführte, gab der toString-Ansatz Laufzeiten von 6400 bis 6600 Millis an, während der Log-Ansatz 20.000 bis 20.400 Millis überstieg. Anstatt etwas schneller zu sein, war der Log-Ansatz für mich dreimal langsamer.
Beachten Sie, dass die beiden Ansätze sehr unterschiedliche Kosten verursachen, sodass dies nicht völlig schockierend ist: Der toString-Ansatz erstellt viele temporäre Objekte, die bereinigt werden müssen, während der Protokollansatz eine intensivere Berechnung erfordert. Vielleicht besteht der Unterschied darin, dass toString auf einem Computer mit weniger Speicher mehr Speicherbereinigungsrunden erfordert, während auf einem Computer mit einem langsameren Prozessor die zusätzliche Berechnung des Protokolls schmerzhafter wäre.
Ich habe auch einen dritten Ansatz versucht. Ich habe diese kleine Funktion geschrieben:
Das lief zwischen 1600 und 1900 Millis - weniger als 1/3 des toString-Ansatzes und 1/10 des Log-Ansatzes auf meinem Computer.
Wenn Sie über ein breites Spektrum an Zahlen verfügen, können Sie diese weiter beschleunigen, indem Sie zunächst durch 1.000 oder 1.000.000 dividieren, um die Anzahl der Durchgänge durch die Schleife zu verringern. Damit habe ich nicht gespielt.
quelle
Verwenden von Java
Verwendung
import java.lang.Math.*;
am AnfangVerwenden von C.
Verwendung
inclue math.h
am Anfangquelle
the_integer
ist0
. Überprüfen Sie dies.Ich kann noch keinen Kommentar hinterlassen, daher werde ich als separate Antwort posten.
Die logarithmusbasierte Lösung berechnet nicht die richtige Anzahl von Stellen für sehr große lange Ganzzahlen, zum Beispiel:
Die logarithmusbasierte Lösung berechnet die falsche Anzahl von Ziffern in großen Ganzzahlen
quelle
Da die Anzahl der Ziffern in Basis 10 einer Ganzzahl nur 1 + abgeschnitten ist (log10 (Zahl)) , können Sie Folgendes tun:
Bearbeitet, weil meine letzte Bearbeitung das Codebeispiel behoben hat, aber nicht die Beschreibung.
quelle
Math.floor
ist ein bisschen überflüssig, nicht wahr? Casting toint
wird es trotzdem abrunden.Marians Lösung für lange Typennummern (bis zu 9.223.372.036.854.775.807), falls jemand sie kopieren und einfügen möchte. In dem Programm, das ich für Zahlen geschrieben habe, waren bis zu 10000 viel wahrscheinlicher, also habe ich einen bestimmten Zweig für sie gemacht. Auf jeden Fall wird es keinen signifikanten Unterschied machen.
quelle
Ein weiterer String-Ansatz. Kurz und bündig - für jede ganze Zahl
n
.quelle
n
und Null. Kann verwendet werden("" + Math.abs(n)).length()
, um die Länge einer negativen Ganzzahl zu ermitteln.Kann ich es versuchen? ;)
basierend auf Dirks Lösung
quelle
Wie wäre es mit einfacher alter Mathematik? Teilen Sie durch 10, bis Sie 0 erreichen.
quelle
Long.MAX_VALUE
dem Fall mit der schlimmsten Komplexität Ihres Codes, undSystem.nanoTime()
führen Sie einen Taktversuch gegen die Fälle mit der schlimmsten Komplexität der anderen Lösung durch. ++ Versuchen Sie es tatsächlich mit einem Array, das mit einem Zufallsgenerator gefüllt ist, der auf den Bereich von0
bis eingestelltLong.MAX_VALUE
ist, nur für den Test der "durchschnittlichen Komplexität". ++ Sie finden die Ergebnisse möglicherweise ... sehr schockierend.int,
diese Schleife maximal 11 Mal ausgeführt. Haben Sie Beweise für Ihre Behauptungen?Marians Lösung, jetzt mit Ternary:
Weil wir können.
quelle
Neugierig habe ich versucht, es zu vergleichen ...
Die Ergebnisse sind:
Jetzt muss ich mich fragen, ob mein Benchmark tatsächlich etwas bedeutet, aber ich erhalte konsistente Ergebnisse (Variationen innerhalb einer ms) über mehrere Läufe des Benchmarks selbst ... :) Es sieht so aus, als wäre es sinnlos, dies zu optimieren ...
edit: Nach dem Kommentar von ptomli habe ich im obigen Code 'number' durch 'i' ersetzt und über 5 Läufe der Bank die folgenden Ergebnisse erhalten:
quelle
Was ist mit dieser rekursiven Methode?
quelle
einfache Lösung:
quelle
Eine wirklich einfache Lösung:
quelle
Oder stattdessen die Länge, die Sie überprüfen können, ob die Zahl größer oder kleiner als die gewünschte Zahl ist.
}}
quelle
Ich habe noch keine multiplikationsbasierte Lösung gesehen. Logarithmus-, Divison- und String-basierte Lösungen werden für Millionen von Testfällen ziemlich unhandlich. Hier ist eine für
ints
:In Basis 10 funktioniert dies, weil n im Wesentlichen mit 9, 99, 999 verglichen wird ... da min 9, 90, 900 ... ist und n von 9, 90, 900 ... subtrahiert wird.
Leider ist dies nicht
long
nur durch Ersetzen jeder Instanzint
aufgrund von Überlauf portierbar . Auf der anderen Seite, es passiert einfach so , es wird für Basen arbeitet 2 und 10 (aber nicht schlecht für die meisten anderen Basen). Sie benötigen eine Nachschlagetabelle für die Überlaufpunkte (oder einen Teilungstest ... ew)quelle
Mit Design (basierend auf dem Problem). Dies ist eine Alternative von Teilen und Erobern. Wir definieren zuerst eine Aufzählung (wenn man bedenkt, dass es sich nur um ein Int ohne Vorzeichen handelt).
Jetzt definieren wir eine Klasse, die die Werte der Aufzählung durchläuft und die entsprechende Länge vergleicht und zurückgibt.
Die Laufzeit dieser Lösung entspricht der des Divide-and-Conquer-Ansatzes.
quelle
num>=Nine.getValue()
?Man möchte dies meistens tun, weil man es "präsentieren" möchte, was meistens bedeutet, dass es schließlich explizit oder implizit "toString-ed" (oder auf andere Weise transformiert) werden muss; bevor es präsentiert werden kann (zum Beispiel gedruckt).
Wenn dies der Fall ist, versuchen Sie einfach, den erforderlichen "toString" explizit zu machen und die Bits zu zählen.
quelle
Wir können dies mit einer rekursiven Schleife erreichen
quelle
Ich habe diese Funktion geschrieben, nachdem ich den
Integer.java
Quellcode gesucht habe .quelle
Ich sehe Leute, die String-Bibliotheken oder sogar die Integer-Klasse verwenden. Daran ist nichts auszusetzen, aber der Algorithmus zum Abrufen der Anzahl der Ziffern ist nicht so kompliziert. Ich verwende in diesem Beispiel ein Long, aber es funktioniert genauso gut mit einem Int.
quelle
Keine String-API, keine Utils, keine Typkonvertierung, nur reine Java-Iteration ->
Wenn Sie möchten, können Sie sich nach größeren Werten sehnen.
quelle
quelle
Einfacher rekursiver Weg
nicht getestet
quelle
Sie könnten die Ziffern durch sukzessive Division durch zehn:
quelle
Geben Sie die Nummer ein und erstellen Sie eine
Arraylist
, und die while-Schleife zeichnet alle Ziffern in der aufArraylist
. Dann können wir die Größe des Arrays herausnehmen, die der Länge des von Ihnen eingegebenen ganzzahligen Werts entspricht.quelle
Hier ist eine wirklich einfache Methode, die ich gemacht habe und die für jede Zahl funktioniert:
Die Art und Weise, wie es mit der Zahlenzählervariablen funktioniert, ist, dass 10 = 1 stelliges Leerzeichen. Zum Beispiel .1 = 1 Zehntel => 1 Stellen. Wenn Sie also haben, erhalten
int number = 103342;
Sie 6, da dies das Äquivalent von .000001 Leerzeichen zurück ist. Hat jemand einen besseren Variablennamen fürnumberCounter
? Ich kann mir nichts Besseres vorstellen.Edit: Ich dachte nur an eine bessere Erklärung. Im Wesentlichen bewirkt diese while-Schleife, dass Sie Ihre Zahl durch 10 teilen, bis sie kleiner als eins ist. Wenn Sie etwas durch 10 teilen, verschieben Sie es im Wesentlichen um ein Zahlenfeld zurück. Teilen Sie es also einfach durch 10, bis Sie <1 für die Anzahl der Stellen in Ihrer Zahl erreichen.
Hier ist eine andere Version, die die Anzahl der Zahlen in Dezimalzahlen zählen kann:
quelle
Versuchen Sie, das int in eine Zeichenfolge zu konvertieren , und ermitteln Sie dann die Länge der Zeichenfolge . Das sollte die Länge des int bekommen .
quelle
number
negativ ist.