Saya pikir dia ingin menghitung angka dalam angka.
Alberto Zaccagni
3
Jawaban yang diberikan orang kepada Anda benar ... mereka memberi Anda panjang int tanpa mengubahnya menjadi string ... tapi mengapa Anda tidak ingin mengubahnya menjadi string? Apakah ini hal yang cepat? Jika demikian, saya tidak yakin bahwa metode ini akan lebih cepat ... Anda mungkin ingin melakukan beberapa tes (atau memutuskan apakah itu penting).
Beska
3
Digit @ptomli hexadecimal masih digit, hanya di sistem basis yang berbeda.
Mark Pim
2
@ Patomli Tentu, tetapi keduanya dalam fungsi Integer.toString, dan dalam percakapan umum, desimal adalah default. Ketika bank memberi tahu saya, "Tuliskan jumlah cek Anda di kotak ini", saya tidak bertanya kepada mereka apakah saya harus menuliskannya dalam desimal, hex, atau oktal. Kami menganggap desimal kecuali ditentukan atau dipanggil oleh konteks.
Jay
Jawaban:
349
Solusi berbasis String Anda benar-benar oke, tidak ada yang "tidak rapi" tentangnya. Anda harus menyadari bahwa secara matematis, angka tidak memiliki panjang, juga angka. Panjang dan digit sama-sama properti dari representasi fisik angka dalam basis tertentu, yaitu String.
Solusi berbasis logaritma melakukan (beberapa) hal-hal yang sama dengan yang berbasis string secara internal, dan mungkin melakukannya (tidak signifikan) lebih cepat karena hanya menghasilkan panjang dan mengabaikan angka. Tetapi saya tidak akan benar-benar mempertimbangkannya dengan maksud yang lebih jelas - dan itulah faktor terpenting.
1 untuk mempertimbangkan niat kode ketika memilih cara untuk memecahkan masalah
pupeno
5
Datapoint: Di mesin saya, metode log tampaknya berjalan di bawah dua kali lebih cepat dari metode panjang string. Saya tidak akan menyebut itu tidak penting jika metode dipanggil banyak atau dalam bagian kode waktu-kritis.
CPerkins
1
Lihat unit test benchmark saya di bawah ini (yang mungkin juga cacat saya bukan ahli benchmark). Lebih dari sejumlah besar berjalan (100.000), kecepatan 11s sampai 8s pada mesin saya hampir tidak dua kali lebih cepat.
Jean
5
@CPerkins. Optimalisasi prematur. Anda tahu omongan itu.
Michael Borgwardt
11
Beberapa tambahan (sangat terlambat): Ini mungkin tidak berfungsi dengan baik untuk nilai negatif, tergantung jika Anda mengharapkan "-" menjadi digit atau tidak. Menambahkan Math.abs()akan memperbaiki ini, meskipun.
Dan apakah ini lebih cepat atau lebih baik daripada menggunakan varian saya?
fnst
+1 Anda mengalahkan saya sebentar, dan jawaban Anda benar, di mana jawaban saya sedikit salah. Perhatikan, bagaimanapun, bahwa kompiler akan mengeluh karena pemain hilang ke int
Dirk
2
@ Tom Mengapa Anda menganggap itu mahal? Orang mungkin berasumsi bahwa co-prosesor matematika akan mengeksekusinya, sehingga mungkin mendekati kecepatan penambahan. Bahkan jika java tidak menggunakan co-prosesor sekarang, itu asumsi yang baik bahwa itu mungkin ... (Kami hanya akan mengabaikan implikasi Anda yang bahkan lebih tidak berpendidikan bahwa Java lambat karena Anda mungkin tidak tertarik pada bukti - atau jika Anda, Anda akan pergi ke shootout.alioth.debian.org dan mencari tahu sendiri)
Bill K
8
Berfungsi ... kecuali nilai yang Anda periksa = 0, yang akan memberi Anda hasil aneh (-2147483647). Math.log10 API: "Jika argumennya positif nol atau nol negatif, maka hasilnya adalah infinity negatif."
mujimu
2
+1 Menyajikan metode yang tidak melibatkan alokasi memori objek, yang merupakan keharusan untuk memaksimalkan penggunaan kembali untuk menghindari koleksi GC.
Michael Wojcik
159
Pendekatan tercepat: bagilah dan taklukkan.
Dengan asumsi rentang Anda adalah 0 hingga MAX_INT, maka Anda memiliki 1 hingga 10 digit. Anda dapat mendekati interval ini menggunakan membagi dan menaklukkan, dengan hingga 4 perbandingan per setiap input. Pertama, Anda membagi [1..10] menjadi [1..5] dan [6..10] dengan satu perbandingan, dan kemudian setiap interval 5 panjang yang Anda bagi menggunakan satu perbandingan menjadi satu interval 3 dan satu panjang 2. Interval panjang 2 membutuhkan satu perbandingan lagi (total 3 perbandingan), interval panjang 3 dapat dibagi menjadi interval panjang 1 (solusi) dan interval panjang 2. Jadi, Anda perlu 3 atau 4 perbandingan.
Tidak ada divisi, tidak ada operasi floating point, tidak ada logaritma mahal, hanya perbandingan integer.
Kode (panjang tapi cepat):
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 (setelah pemanasan JVM) - lihat kode di bawah ini untuk melihat bagaimana benchmark dijalankan:
metode dasar (dengan String.length): 2145ms
metode log10: 711ms = 3.02 kali lebih cepat dari baseline
pembagian berulang: 2797 ms = 0,77 kali lebih cepat dari baseline
Divide-and-Conquer: 74ms = 28,99
kali lebih cepat dari baseline
Kode lengkap:
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;}
Sekali lagi, patokan:
metode dasar (dengan String.length): 2145ms
metode log10: 711ms = 3.02 kali lebih cepat dari baseline
pembagian berulang: 2797 ms = 0,77 kali lebih cepat dari baseline
Divide-and-Conquer: 74ms = 28,99
kali lebih cepat dari baseline
Sunting:
Setelah saya menulis patokan, saya menyelinap ke Integer.toString dari Java 6, dan saya menemukan bahwa ia menggunakan:
ini terlihat hebat. Anda bisa menulisnya sedikit lebih kompak menggunakan operator?: untuk mendapatkan lebih banyak penerimaan
André Pareis
88
berbicara tentang pengoptimalan prematur: D
Gordon Gustafson
2
Saya suka itu! Bagaimana dengan blok switch alih-alih bersarang jika-elses?
Kebman
2
Saya tidak menyadari semua ini jika pernyataan lain akan jauh lebih cepat daripada mengubah int ke String lalu memanggil .length. +1
Ogen
15
Menggunakan operator ternary, membawanya ke 101 karakter: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
Dua komentar tentang tolok ukur Anda: Java adalah lingkungan yang kompleks, apa dengan kompilasi just-in-time dan pengumpulan sampah dan sebagainya, sehingga untuk mendapatkan perbandingan yang adil, setiap kali saya menjalankan tolok ukur, saya selalu: (a) melampirkan dua tes dalam satu loop yang menjalankannya secara berurutan 5 atau 10 kali. Cukup sering runtime pada pass kedua melalui loop sangat berbeda dari yang pertama. Dan (b) Setelah setiap "pendekatan", saya melakukan System.gc () untuk mencoba memicu pengumpulan sampah. Kalau tidak, pendekatan pertama mungkin menghasilkan banyak objek, tetapi tidak cukup untuk memaksa pengumpulan sampah, maka pendekatan kedua menciptakan beberapa objek, tumpukan habis, dan pengumpulan sampah berjalan. Kemudian pendekatan kedua "dibebankan" untuk mengambil sampah yang ditinggalkan oleh pendekatan pertama. Sangat tidak adil!
Yang mengatakan, tak satu pun di atas membuat perbedaan yang signifikan dalam contoh ini.
Dengan atau tanpa modifikasi itu, saya mendapat hasil yang sangat berbeda dari yang Anda lakukan. Ketika saya menjalankan ini, ya, pendekatan toString memberikan waktu berjalan dari 6400 hingga 6600 milis, sedangkan pendekatan log topok 20.000 hingga 20.400 milis. Alih-alih sedikit lebih cepat, pendekatan log 3 kali lebih lambat bagi saya.
Perhatikan bahwa kedua pendekatan ini melibatkan biaya yang sangat berbeda, jadi ini tidak terlalu mengejutkan: Pendekatan toString akan menciptakan banyak objek sementara yang harus dibersihkan, sementara pendekatan log membutuhkan perhitungan yang lebih intens. Jadi mungkin perbedaannya adalah bahwa pada mesin dengan memori lebih sedikit, toString membutuhkan lebih banyak putaran pengumpulan sampah, sedangkan pada mesin dengan prosesor yang lebih lambat, perhitungan ekstra dari log akan lebih menyakitkan.
Saya juga mencoba pendekatan ketiga. Saya menulis fungsi kecil ini:
Itu berjalan pada 1600 hingga 1900 milis - kurang dari 1/3 pendekatan toString, dan 1/10 pendekatan log pada mesin saya.
Jika Anda memiliki rentang angka yang luas, Anda bisa mempercepatnya lebih jauh dengan mulai membagi dengan 1.000 atau 1.000.000 untuk mengurangi jumlah kali melalui loop. Saya belum bermain dengan itu.
Sudahkah Anda mencoba memvariasikan input? VM hotspot dapat mengoptimalkan grafik ini jika tidak, menghasilkan tolok ukur yang salah, karena ia mengembalikan hal yang sama yang telah dihitung sebelumnya.
Erik Aigner
11
Menggunakan Java
int nDigits =Math.floor(Math.log10(Math.abs(the_integer)))+1;
Keren. tapi saya pikir itu perlu abs (angka) dan juga "0" adalah case khusus juga?
DmitryK
Iya. Jika Anda perlu memperhitungkan tanda, Anda harus melakukan sesuatu seperti 1 + (int) Math.floor (Math.log10 (Math.abs (angka))) + + ((angka <0)? 1: 0)
Dirk
5
Ini Math.flooragak berlebihan, bukan? Tetap intakan membulatkannya ke bawah.
CompuChip
5
Solusi Marian disesuaikan untuk nomor tipe lama (hingga 9.223.372.036.854.775.807), jika seseorang ingin menyalin & menempelkannya. Dalam program saya menulis ini untuk angka hingga 10.000 jauh lebih mungkin, jadi saya membuat cabang khusus untuk mereka. Pokoknya itu tidak akan membuat perbedaan yang signifikan.
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;}}}}}
Sudahkah Anda mengujinya? Anda tahu, meski sulit, bagi sudut pandang manusia, itu tidak benar-benar bekerja sama dengan "cara berpikir" mesin, kan? --- Mari saya usulkan satu hal: Buatlah array dua juta angka, lebih disukai Long.MAX_VALUE, yang merupakan kasus kompleksitas terburuk kode Anda, dan gunakan System.nanoTime()untuk melakukan uji coba pencatatan jam kerja terhadap kasus kompleksitas terburuk dari solusi lain. ++ Sebenarnya, cobalah dengan array diisi oleh satu set randomizer untuk kisaran 0untuk Long.MAX_VALUEjuga, hanya untuk "rata-rata kompleksitas" menguji ++ Anda mungkin menemukan hasil ... sangat mengejutkan.
XenoRo
@ thelima Ini tidak berfungsi dengan benar untuk nol atau negatif, tapi itu bug kecil. Prinsipnya terlihat benar bagi saya. Apa hasil "mengejutkan" yang Anda maksud?
Jay
Anggap saja komputer ... Ya ... Mereka tidak suka membagi. Dan dalam kasus-kasus di mana "antrian" besar dalam jumlah besar perlu diproses, dan setiap digit di setiap nomor yang diproses akan membutuhkan pembagian ... Ya ... Hal-hal "mulai menjadi sangat lambat sangat cepat" ... Jika Anda menangkap artinya ... --- Inilah sebabnya mengapa Anda melihat banyak jawaban di sini menggunakan kode berdasarkan tes dan perbandingan dengan setiap angka desimal menggunakan 'jika, daripada pembagian: Jika tidak lebih cepat, setidaknya itu mempertahankan sebagian besar kecepatan itu terlepas itu kasus terburuk. --- Lakukan tes antara menggunakan divisi dan logaritma dalam jumlah besar ...
XenoRo
@ Theima apa yang kamu bicarakan? Untuk int,loop ini dieksekusi maksimal 11 kali. Apakah Anda memiliki beberapa bukti untuk pernyataan Anda?
Marquis of Lorne
@ EJP Dari sudut pandang perangkat keras, pembagian adalah proses berulang. Algoritma pembagian tercepat yang saya tahu adalah radix4, yang menghasilkan 4 bit per iterasi; jadi membagi 32 bit membutuhkan 8 iterasi setidaknya. Perkalian, misalnya, dapat dilakukan secara paralel, dan juga dapat dipecah menjadi perkalian yang lebih sederhana; baik turun ke tingkat bit (hanya membutuhkan 5 operasi), atau dengan kerusakan sebagian ditambah tabel pencarian di akhir (ukuran klasik VS kecepatan trade-off). Ini bukan hanya tentang "berapa banyak iterasi"; masalah dengan divisi terletak pada "apa yang disiratkan / dilakukan setiap iterasi, pada tingkat perangkat keras"
Jalankan waktu 1: 6765
s: 400000000
Jalankan waktu 2: 6000
s: 400000000
Sekarang saya bertanya-tanya apakah tolok ukur saya benar-benar berarti tetapi saya mendapatkan hasil yang konsisten (variasi dalam ms) selama beberapa kali tolok ukur itu sendiri ... :) Sepertinya tidak ada gunanya mencoba dan mengoptimalkan ini ...
sunting: mengikuti komentar ptomli, saya mengganti 'angka' dengan 'i' dalam kode di atas dan mendapatkan hasil sebagai berikut selama 5 kali pelaksanaan:
Jalankan waktu 1: 11500
s: 788888890
Jalankan waktu 2: 8547
s: 788888890
Jalankan waktu 1: 11485
s: 788888890
Jalankan waktu 2: 8547
s: 788888890
Jalankan waktu 1: 11469
s: 788888890
Jalankan waktu 2: 8547
s: 788888890
Jalankan waktu 1: 11500
s: 788888890
Jalankan waktu 2: 8547
s: 788888890
Jalankan waktu 1: 11484
s: 788888890
Jalankan waktu 2: 8547
s: 788888890
Saya tidak akan memanggil satu baris untuk loop dengan tubuh kosong yang sederhana. Atau modulo kekuatan 10 untuk melihat apakah Anda mendapatkan hal yang sama kembali (tidak bisakah Anda hanya menggunakan perbandingan?).
Teepeemm
0
Atau sebaliknya panjang Anda dapat memeriksa apakah jumlahnya lebih besar atau lebih kecil dari angka yang diinginkan.
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);}}
Saya tidak mengerti. Sepertinya Anda menjawab pertanyaan yang berbeda.
Teepeemm
0
Saya belum melihat solusi berbasis perkalian. Logaritma, pembagian, dan solusi berbasis string akan menjadi agak sulit melawan jutaan kasus uji, jadi inilah satu untuk 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;}
Dalam basis 10, ini bekerja karena n pada dasarnya dibandingkan dengan 9, 99, 999 ... karena min adalah 9, 90, 900 ... dan n sedang dikurangi dengan 9, 90, 900 ...
Sayangnya, ini tidak portabel longhanya dengan mengganti setiap instance intkarena overflow. Di sisi lain, kebetulan ia akan bekerja untuk basis 2 dan 10 (tetapi gagal untuk sebagian besar basis lainnya). Anda akan membutuhkan tabel pencarian untuk titik-titik luapan (atau tes pembagian ... 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;}
Dengan desain (berdasarkan masalah). Ini adalah alternatif dari divide-and-conquer. Kami pertama-tama akan mendefinisikan enum (mengingat itu hanya untuk int yang tidak ditandatangani).
Divide-and-conquer akan dimulai di tengah dan membagi dua area pencarian yang tersisa. Ini memiliki waktu menjalankan linier. Tapi itu tidak masalah hanya untuk 9 perbandingan. Tapi bukankah ini akan berantakan jika num>=Nine.getValue()?
Teepeemm
0
Seseorang ingin melakukan ini sebagian besar karena dia ingin "menyajikan", yang sebagian besar berarti akhirnya harus "toString-ed" (atau diubah dengan cara lain) secara eksplisit atau implisit pula; sebelum dapat disajikan (dicetak misalnya).
Jika itu masalahnya, maka cobalah membuat "toString" yang diperlukan secara eksplisit dan hitung bitnya.
Saya melihat orang-orang menggunakan perpustakaan String atau bahkan menggunakan kelas Integer. Tidak ada yang salah dengan itu tetapi algoritma untuk mendapatkan jumlah digit tidak terlalu rumit. Saya menggunakan panjang dalam contoh ini tetapi berfungsi dengan baik dengan int.
privatestaticint getLength(long num){int count =1;while(num >=10){
num = num /10;
count++;}return count;}
tanpa API String, tanpa utils, tanpa konversi tipe, hanya iterasi java murni ->
publicstaticint getNumberOfDigits(int input){int numOfDigits =1;int base =1;while(input >= base *10){
base = base *10;
numOfDigits++;}return numOfDigits;}
Anda bisa merindukan nilai yang lebih besar jika Anda mau.
Anda mungkin harus mengujinya (dan pastikan itu Java yang valid dan diformat dengan benar). Tapi pendekatan "divide by 10" rekursif diposting oleh Jedi Dula 3 tahun yang lalu.
Teepeemm
-2
Anda dapat menggunakan digit dengan pembagian berurutan sebanyak sepuluh:
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);
Pendekatan "divide by 10" pertama kali diposting oleh Sinista 3 tahun yang lalu. Itulah satu-satunya alasan saya dapat berpikir bahwa Anda mendapat downvote.
Teepeemm
-2
Masukkan nomor dan buat Arraylist, dan loop sementara akan mencatat semua digit ke dalam Arraylist. Lalu kita bisa mengambil ukuran array, yang akan menjadi panjang nilai integer yang Anda masukkan.
ArrayList<Integer> a=newArrayList<>();while(number >0){
remainder = num %10;
a.add(remainder);
number = number /10;}int m=a.size();
Cara kerjanya adalah dengan variabel penghitung angka yaitu 10 = 1 digit spasi. Misalnya .1 = 1 persepuluh => 1 digit spasi. Karenanya, jika Anda memilikinya, int number = 103342;Anda akan mendapatkan 6, karena itu setara dengan 0,000001 spasi kembali. Juga, apakah ada yang punya nama variabel yang lebih baik numberCounter? Saya tidak bisa memikirkan yang lebih baik.
Sunting: Pikirkan penjelasan yang lebih baik. Pada dasarnya apa yang dilakukan loop ini adalah membuatnya Anda membagi angka dengan 10, sampai kurang dari satu. Pada dasarnya, ketika Anda membagi sesuatu dengan 10 Anda memindahkannya kembali satu ruang angka, jadi Anda cukup membaginya dengan 10 sampai Anda mencapai <1 untuk jumlah digit dalam nomor Anda.
Berikut ini versi lain yang dapat menghitung jumlah angka dalam desimal:
Jawaban:
Solusi berbasis String Anda benar-benar oke, tidak ada yang "tidak rapi" tentangnya. Anda harus menyadari bahwa secara matematis, angka tidak memiliki panjang, juga angka. Panjang dan digit sama-sama properti dari representasi fisik angka dalam basis tertentu, yaitu String.
Solusi berbasis logaritma melakukan (beberapa) hal-hal yang sama dengan yang berbasis string secara internal, dan mungkin melakukannya (tidak signifikan) lebih cepat karena hanya menghasilkan panjang dan mengabaikan angka. Tetapi saya tidak akan benar-benar mempertimbangkannya dengan maksud yang lebih jelas - dan itulah faktor terpenting.
sumber
Math.abs()
akan memperbaiki ini, meskipun.Logaritma adalah teman Anda:
NB: hanya valid untuk n> 0.
sumber
Pendekatan tercepat: bagilah dan taklukkan.
Dengan asumsi rentang Anda adalah 0 hingga MAX_INT, maka Anda memiliki 1 hingga 10 digit. Anda dapat mendekati interval ini menggunakan membagi dan menaklukkan, dengan hingga 4 perbandingan per setiap input. Pertama, Anda membagi [1..10] menjadi [1..5] dan [6..10] dengan satu perbandingan, dan kemudian setiap interval 5 panjang yang Anda bagi menggunakan satu perbandingan menjadi satu interval 3 dan satu panjang 2. Interval panjang 2 membutuhkan satu perbandingan lagi (total 3 perbandingan), interval panjang 3 dapat dibagi menjadi interval panjang 1 (solusi) dan interval panjang 2. Jadi, Anda perlu 3 atau 4 perbandingan.
Tidak ada divisi, tidak ada operasi floating point, tidak ada logaritma mahal, hanya perbandingan integer.
Kode (panjang tapi cepat):
Benchmark (setelah pemanasan JVM) - lihat kode di bawah ini untuk melihat bagaimana benchmark dijalankan:
kali lebih cepat dari baseline
Kode lengkap:
Sekali lagi, patokan:
kali lebih cepat dari baseline
Sunting: Setelah saya menulis patokan, saya menyelinap ke Integer.toString dari Java 6, dan saya menemukan bahwa ia menggunakan:
Saya membandingkannya dengan solusi divide-and-conquer saya:
Tambang saya sekitar 4x lebih cepat dari solusi Java 6.
sumber
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
Dua komentar tentang tolok ukur Anda: Java adalah lingkungan yang kompleks, apa dengan kompilasi just-in-time dan pengumpulan sampah dan sebagainya, sehingga untuk mendapatkan perbandingan yang adil, setiap kali saya menjalankan tolok ukur, saya selalu: (a) melampirkan dua tes dalam satu loop yang menjalankannya secara berurutan 5 atau 10 kali. Cukup sering runtime pada pass kedua melalui loop sangat berbeda dari yang pertama. Dan (b) Setelah setiap "pendekatan", saya melakukan System.gc () untuk mencoba memicu pengumpulan sampah. Kalau tidak, pendekatan pertama mungkin menghasilkan banyak objek, tetapi tidak cukup untuk memaksa pengumpulan sampah, maka pendekatan kedua menciptakan beberapa objek, tumpukan habis, dan pengumpulan sampah berjalan. Kemudian pendekatan kedua "dibebankan" untuk mengambil sampah yang ditinggalkan oleh pendekatan pertama. Sangat tidak adil!
Yang mengatakan, tak satu pun di atas membuat perbedaan yang signifikan dalam contoh ini.
Dengan atau tanpa modifikasi itu, saya mendapat hasil yang sangat berbeda dari yang Anda lakukan. Ketika saya menjalankan ini, ya, pendekatan toString memberikan waktu berjalan dari 6400 hingga 6600 milis, sedangkan pendekatan log topok 20.000 hingga 20.400 milis. Alih-alih sedikit lebih cepat, pendekatan log 3 kali lebih lambat bagi saya.
Perhatikan bahwa kedua pendekatan ini melibatkan biaya yang sangat berbeda, jadi ini tidak terlalu mengejutkan: Pendekatan toString akan menciptakan banyak objek sementara yang harus dibersihkan, sementara pendekatan log membutuhkan perhitungan yang lebih intens. Jadi mungkin perbedaannya adalah bahwa pada mesin dengan memori lebih sedikit, toString membutuhkan lebih banyak putaran pengumpulan sampah, sedangkan pada mesin dengan prosesor yang lebih lambat, perhitungan ekstra dari log akan lebih menyakitkan.
Saya juga mencoba pendekatan ketiga. Saya menulis fungsi kecil ini:
Itu berjalan pada 1600 hingga 1900 milis - kurang dari 1/3 pendekatan toString, dan 1/10 pendekatan log pada mesin saya.
Jika Anda memiliki rentang angka yang luas, Anda bisa mempercepatnya lebih jauh dengan mulai membagi dengan 1.000 atau 1.000.000 untuk mengurangi jumlah kali melalui loop. Saya belum bermain dengan itu.
sumber
Menggunakan Java
gunakan
import java.lang.Math.*;
di awalMenggunakan C
gunakan
inclue math.h
di awalsumber
the_integer
ini0
, jadi untuk itu.Tidak dapat meninggalkan komentar, jadi saya akan memposting sebagai jawaban terpisah.
Solusi berbasis logaritma tidak menghitung jumlah digit yang benar untuk bilangan bulat yang sangat besar, misalnya:
Solusi berbasis logaritma menghitung jumlah digit yang tidak benar dalam bilangan bulat besar
sumber
Karena jumlah digit dalam basis 10 integer hanya 1 + truncate (log10 (angka)) , Anda dapat melakukan:
Diedit karena edit terakhir saya memperbaiki contoh kode, tetapi bukan deskripsi.
sumber
Math.floor
agak berlebihan, bukan? Tetapint
akan membulatkannya ke bawah.Solusi Marian disesuaikan untuk nomor tipe lama (hingga 9.223.372.036.854.775.807), jika seseorang ingin menyalin & menempelkannya. Dalam program saya menulis ini untuk angka hingga 10.000 jauh lebih mungkin, jadi saya membuat cabang khusus untuk mereka. Pokoknya itu tidak akan membuat perbedaan yang signifikan.
sumber
Pendekatan string lain. Pendek dan manis - untuk bilangan bulat apa pun
n
.sumber
n
dan nol. Dapat digunakan("" + Math.abs(n)).length()
untuk mendapatkan panjang bilangan bulat negatif.Bisakah saya mencoba? ;)
berdasarkan solusi Dirk
sumber
Bagaimana dengan Matematika kuno? Bagi dengan 10 hingga Anda mencapai 0.
sumber
Long.MAX_VALUE
, yang merupakan kasus kompleksitas terburuk kode Anda, dan gunakanSystem.nanoTime()
untuk melakukan uji coba pencatatan jam kerja terhadap kasus kompleksitas terburuk dari solusi lain. ++ Sebenarnya, cobalah dengan array diisi oleh satu set randomizer untuk kisaran0
untukLong.MAX_VALUE
juga, hanya untuk "rata-rata kompleksitas" menguji ++ Anda mungkin menemukan hasil ... sangat mengejutkan.int,
loop ini dieksekusi maksimal 11 kali. Apakah Anda memiliki beberapa bukti untuk pernyataan Anda?Solusi Marian, sekarang dengan Ternary:
Karena kita bisa.
sumber
Penasaran, saya mencoba membandingkannya ...
hasilnya adalah:
Sekarang saya bertanya-tanya apakah tolok ukur saya benar-benar berarti tetapi saya mendapatkan hasil yang konsisten (variasi dalam ms) selama beberapa kali tolok ukur itu sendiri ... :) Sepertinya tidak ada gunanya mencoba dan mengoptimalkan ini ...
sunting: mengikuti komentar ptomli, saya mengganti 'angka' dengan 'i' dalam kode di atas dan mendapatkan hasil sebagai berikut selama 5 kali pelaksanaan:
sumber
Bagaimana dengan metode rekursif ini?
sumber
solusi sederhana:
sumber
Solusi yang sangat sederhana:
sumber
Atau sebaliknya panjang Anda dapat memeriksa apakah jumlahnya lebih besar atau lebih kecil dari angka yang diinginkan.
}
sumber
Saya belum melihat solusi berbasis perkalian. Logaritma, pembagian, dan solusi berbasis string akan menjadi agak sulit melawan jutaan kasus uji, jadi inilah satu untuk
ints
:Dalam basis 10, ini bekerja karena n pada dasarnya dibandingkan dengan 9, 99, 999 ... karena min adalah 9, 90, 900 ... dan n sedang dikurangi dengan 9, 90, 900 ...
Sayangnya, ini tidak portabel
long
hanya dengan mengganti setiap instanceint
karena overflow. Di sisi lain, kebetulan ia akan bekerja untuk basis 2 dan 10 (tetapi gagal untuk sebagian besar basis lainnya). Anda akan membutuhkan tabel pencarian untuk titik-titik luapan (atau tes pembagian ... ew)sumber
Dengan desain (berdasarkan masalah). Ini adalah alternatif dari divide-and-conquer. Kami pertama-tama akan mendefinisikan enum (mengingat itu hanya untuk int yang tidak ditandatangani).
Sekarang kita akan mendefinisikan kelas yang melewati nilai enum dan membandingkan dan mengembalikan panjang yang sesuai.
Run time dari solusi ini sama dengan pendekatan divide-and-conquer.
sumber
num>=Nine.getValue()
?Seseorang ingin melakukan ini sebagian besar karena dia ingin "menyajikan", yang sebagian besar berarti akhirnya harus "toString-ed" (atau diubah dengan cara lain) secara eksplisit atau implisit pula; sebelum dapat disajikan (dicetak misalnya).
Jika itu masalahnya, maka cobalah membuat "toString" yang diperlukan secara eksplisit dan hitung bitnya.
sumber
Kita dapat mencapai ini menggunakan loop rekursif
sumber
Saya menulis fungsi ini setelah mencari
Integer.java
kode sumber.sumber
Saya melihat orang-orang menggunakan perpustakaan String atau bahkan menggunakan kelas Integer. Tidak ada yang salah dengan itu tetapi algoritma untuk mendapatkan jumlah digit tidak terlalu rumit. Saya menggunakan panjang dalam contoh ini tetapi berfungsi dengan baik dengan int.
sumber
tanpa API String, tanpa utils, tanpa konversi tipe, hanya iterasi java murni ->
Anda bisa merindukan nilai yang lebih besar jika Anda mau.
sumber
sumber
Cara rekursif mudah
tidak diuji
sumber
Anda dapat menggunakan digit dengan pembagian berurutan sebanyak sepuluh:
sumber
Masukkan nomor dan buat
Arraylist
, dan loop sementara akan mencatat semua digit ke dalamArraylist
. Lalu kita bisa mengambil ukuran array, yang akan menjadi panjang nilai integer yang Anda masukkan.sumber
Inilah metode yang sangat sederhana yang saya buat yang berfungsi untuk nomor apa pun:
Cara kerjanya adalah dengan variabel penghitung angka yaitu 10 = 1 digit spasi. Misalnya .1 = 1 persepuluh => 1 digit spasi. Karenanya, jika Anda memilikinya,
int number = 103342;
Anda akan mendapatkan 6, karena itu setara dengan 0,000001 spasi kembali. Juga, apakah ada yang punya nama variabel yang lebih baiknumberCounter
? Saya tidak bisa memikirkan yang lebih baik.Sunting: Pikirkan penjelasan yang lebih baik. Pada dasarnya apa yang dilakukan loop ini adalah membuatnya Anda membagi angka dengan 10, sampai kurang dari satu. Pada dasarnya, ketika Anda membagi sesuatu dengan 10 Anda memindahkannya kembali satu ruang angka, jadi Anda cukup membaginya dengan 10 sampai Anda mencapai <1 untuk jumlah digit dalam nomor Anda.
Berikut ini versi lain yang dapat menghitung jumlah angka dalam desimal:
sumber
Cobalah mengubah int ke string yang dan kemudian mendapatkan panjang tali . Itu harus mendapatkan panjang int .
sumber
number
negatif.