Saya takut ceil (log10 (10)) = ceil (1) = 1, dan bukan 2 sebagaimana mestinya untuk pertanyaan ini!
ysap
3
Terima kasih, ini metode yang bagus. Meskipun tidak lebih cepat dari int count = 0; lakukan {count ++; } sementara ((i / = 10)> = 1); :(
Puterdo Borato
3
Jika rentang nomor Anda menyertakan negatif, Anda harus menggunakan Math.Floor (Math.Log10 (Math.Abs (n)) + 1);
mrcrowl
1
Nah jika nyaitu 0hanya dapat kembali 1:) Terlalu pegangan nilai-nilai negatif hanya mengganti ndengan Math.Abs(n).
Umair
3
@ Komputerdo Borato: uji kinerja saya sebenarnya menunjukkan bahwa metode Anda lebih cepat ketika jumlah digit <5. Lewati itu, Steve's Math.floor lebih cepat.
Perlu diketahui bahwa Anda mungkin akan mengalami masalah dengan metode ini jika Anda berurusan dengan angka negatif. (Dan jelas desimal, tapi contoh menggunakan int, jadi saya berasumsi itu bukan masalah.)
Cody Gray
2
Alokasi string @Kryic adalah tren baru di dunia .NET.
nawfal
1
baru? Hampir tidak. Saya mengalokasikan string secara mengerikan pada tahun 2010. Benar-benar seorang trend setter. Lol. Anda benar. Ini kotor!
Andiih
3
@Krythic Ini bukan tahun 1980-an, komputer Anda memiliki cukup RAM untuk menyimpan 10 karakter string ke dalam memori selama satu operasi.
MrLore
2
@MrLore Dalam aplikasi sederhana ini mungkin benar, tetapi dalam dunia pengembangan game, ini adalah binatang yang sama sekali berbeda.
Krythic
48
Solusinya
Salah satu dari metode ekstensi berikut akan melakukan pekerjaan itu. Semuanya menganggap tanda minus sebagai digit, dan berfungsi dengan benar untuk semua kemungkinan nilai input. Mereka juga bekerja untuk .NET Framework dan .NET Core. Namun ada perbedaan kinerja yang relevan (dibahas di bawah), tergantung pada pilihan Platform / Kerangka Anda.
Jawaban ini mencakup tes yang dilakukan untuk keduanya Int32dan Int64jenis, menggunakan larik 100.000.000sampel acak int/long angka . Dataset acak diproses sebelumnya menjadi larik sebelum menjalankan pengujian.
Tes konsistensi antara 4 metode yang berbeda juga dieksekusi, untuk MinValue, kasus perbatasan negatif, -1, 0, 1, kasus perbatasan yang positif, MaxValuedan juga untuk dataset acak seluruh. Tidak ada uji konsistensi yang gagal untuk metode yang disediakan di atas, KECUALI untuk metode LOG10 (ini akan dibahas nanti).
Tes dilaksanakan pada .NET Framework 4.7.2dan .NET Core 2.2; untuk x86dan x64platform, pada mesin Prosesor Intel 64-bit, dengan Windows 10, dan dengan VS2017 v.15.9.17. 4 kasus berikut memiliki efek yang sama pada hasil kinerja:
.NET Framework (x86)
Platform = x86
Platform = AnyCPU, Prefer 32-bitdicentang dalam pengaturan proyek
.NET Framework (x64)
Platform = x64
Platform = AnyCPU, Prefer 32-bittidak dicentang di setelan proyek
Uji kinerja di bawah ini menghasilkan distribusi nilai yang seragam di antara berbagai nilai yang dapat diasumsikan oleh integer. Ini berarti ada peluang yang jauh lebih tinggi untuk menguji nilai dengan jumlah digit yang besar. Dalam skenario kehidupan nyata, sebagian besar nilai mungkin kecil, jadi IF-CHAIN akan bekerja lebih baik. Selanjutnya, prosesor akan menyimpan dan mengoptimalkan keputusan IF-CHAIN sesuai dengan kumpulan data Anda.
Seperti yang ditunjukkan @AlanSingfield di bagian komentar, metode LOG10 harus diperbaiki dengan casting ke doubledalam Math.Abs()untuk kasus ketika nilai input adalah int.MinValueataulong.MinValue .
Mengenai tes kinerja awal yang saya terapkan sebelum mengedit pertanyaan ini (sudah diedit jutaan kali), ada kasus khusus yang ditunjukkan oleh @ GyörgyKőszeg , di mana metode IF-CHAIN bekerja lebih lambat daripada metode LOG10.
Ini masih terjadi, meskipun besarnya perbedaan menjadi jauh lebih rendah setelah perbaikan untuk masalah yang ditunjukkan oleh @AlanSingfield . Perbaikan ini (menambahkan cast ke double) menyebabkan kesalahan komputasi ketika nilai inputnya tepat -999999999999999999: metode LOG10 mengembalikan, 20bukan 19. Metode LOG10 juga harus memiliki ifpelindung untuk kasus ketika nilai input adalah nol.
Metode LOG10 cukup rumit untuk berfungsi untuk semua nilai, yang berarti Anda harus menghindarinya. Jika seseorang menemukan cara untuk membuatnya bekerja dengan benar untuk semua tes konsistensi di bawah ini, silakan kirim komentar!
Metode WHILE juga mendapat versi refactored terbaru yang lebih cepat, tetapi masih lambat Platform = x86(saya tidak dapat menemukan alasan mengapa, sampai sekarang).
Metode STRING selalu lambat: metode ini dengan rakus mengalokasikan terlalu banyak memori untuk apa-apa. Menariknya, di .NET Core, alokasi string tampaknya jauh lebih cepat daripada di .NET Framework. Senang mendengarnya.
Metode IF-CHAIN harus mengungguli semua metode lain dalam 99,99% kasus; dan, menurut pendapat pribadi saya, adalah pilihan terbaik Anda (mempertimbangkan semua penyesuaian yang diperlukan untuk membuat metode LOG10 berfungsi dengan benar, dan kinerja buruk dari dua metode lainnya).
Akhirnya, hasilnya adalah:
Karena hasil ini bergantung pada perangkat keras, saya sarankan untuk tetap menjalankan tes kinerja di bawah ini di komputer Anda sendiri jika Anda benar-benar perlu 100% yakin dalam kasus khusus Anda.
Kode Tes
Di bawah ini adalah kode untuk uji kinerja, dan juga uji konsistensi. Kode yang sama digunakan untuk .NET Framework dan .NET Core.
using System;
using System.Diagnostics;
namespace NumberOfDigits{// Performance Tests:classProgram{privatestaticvoidMain(string[] args){Console.WriteLine("\r\n.NET Core");RunTests_Int32();RunTests_Int64();}// Int32 Performance Tests:privatestaticvoidRunTests_Int32(){Console.WriteLine("\r\nInt32");constint size =100000000;int[] samples =newint[size];Random random =newRandom((int)DateTime.Now.Ticks);for(int i =0; i < size;++i)
samples[i]= random.Next(int.MinValue,int.MaxValue);Stopwatch sw1 =newStopwatch();
sw1.Start();for(int i =0; i < size;++i) samples[i].Digits_IfChain();
sw1.Stop();Console.WriteLine($"IfChain: {sw1.ElapsedMilliseconds} ms");Stopwatch sw2 =newStopwatch();
sw2.Start();for(int i =0; i < size;++i) samples[i].Digits_Log10();
sw2.Stop();Console.WriteLine($"Log10: {sw2.ElapsedMilliseconds} ms");Stopwatch sw3 =newStopwatch();
sw3.Start();for(int i =0; i < size;++i) samples[i].Digits_While();
sw3.Stop();Console.WriteLine($"While: {sw3.ElapsedMilliseconds} ms");Stopwatch sw4 =newStopwatch();
sw4.Start();for(int i =0; i < size;++i) samples[i].Digits_String();
sw4.Stop();Console.WriteLine($"String: {sw4.ElapsedMilliseconds} ms");// Start of consistency tests:Console.WriteLine("Running consistency tests...");bool isConsistent =true;// Consistency test on random set:for(int i =0; i < samples.Length;++i){int s = samples[i];int a = s.Digits_IfChain();int b = s.Digits_Log10();int c = s.Digits_While();int d = s.Digits_String();if(a != b || c != d || a != c){Console.WriteLine($"Digits({s}): IfChain={a} Log10={b} While={c} String={d}");
isConsistent =false;break;}}// Consistency test of special values:
samples =newint[]{0,int.MinValue,-1000000000,-999999999,-100000000,-99999999,-10000000,-9999999,-1000000,-999999,-100000,-99999,-10000,-9999,-1000,-999,-100,-99,-10,-9,-1,int.MaxValue,1000000000,999999999,100000000,99999999,10000000,9999999,1000000,999999,100000,99999,10000,9999,1000,999,100,99,10,9,1,};for(int i =0; i < samples.Length;++i){int s = samples[i];int a = s.Digits_IfChain();int b = s.Digits_Log10();int c = s.Digits_While();int d = s.Digits_String();if(a != b || c != d || a != c){Console.WriteLine($"Digits({s}): IfChain={a} Log10={b} While={c} String={d}");
isConsistent =false;break;}}// Consistency test result:if(isConsistent)Console.WriteLine("Consistency tests are OK");}// Int64 Performance Tests:privatestaticvoidRunTests_Int64(){Console.WriteLine("\r\nInt64");constint size =100000000;long[] samples =newlong[size];Random random =newRandom((int)DateTime.Now.Ticks);for(int i =0; i < size;++i)
samples[i]=Math.Sign(random.Next(-1,1))*(long)(random.NextDouble()*long.MaxValue);Stopwatch sw1 =newStopwatch();
sw1.Start();for(int i =0; i < size;++i) samples[i].Digits_IfChain();
sw1.Stop();Console.WriteLine($"IfChain: {sw1.ElapsedMilliseconds} ms");Stopwatch sw2 =newStopwatch();
sw2.Start();for(int i =0; i < size;++i) samples[i].Digits_Log10();
sw2.Stop();Console.WriteLine($"Log10: {sw2.ElapsedMilliseconds} ms");Stopwatch sw3 =newStopwatch();
sw3.Start();for(int i =0; i < size;++i) samples[i].Digits_While();
sw3.Stop();Console.WriteLine($"While: {sw3.ElapsedMilliseconds} ms");Stopwatch sw4 =newStopwatch();
sw4.Start();for(int i =0; i < size;++i) samples[i].Digits_String();
sw4.Stop();Console.WriteLine($"String: {sw4.ElapsedMilliseconds} ms");// Start of consistency tests:Console.WriteLine("Running consistency tests...");bool isConsistent =true;// Consistency test on random set:for(int i =0; i < samples.Length;++i){long s = samples[i];int a = s.Digits_IfChain();int b = s.Digits_Log10();int c = s.Digits_While();int d = s.Digits_String();if(a != b || c != d || a != c){Console.WriteLine($"Digits({s}): IfChain={a} Log10={b} While={c} String={d}");
isConsistent =false;break;}}// Consistency test of special values:
samples =newlong[]{0,long.MinValue,-1000000000000000000,-999999999999999999,-100000000000000000,-99999999999999999,-10000000000000000,-9999999999999999,-1000000000000000,-999999999999999,-100000000000000,-99999999999999,-10000000000000,-9999999999999,-1000000000000,-999999999999,-100000000000,-99999999999,-10000000000,-9999999999,-1000000000,-999999999,-100000000,-99999999,-10000000,-9999999,-1000000,-999999,-100000,-99999,-10000,-9999,-1000,-999,-100,-99,-10,-9,-1,long.MaxValue,1000000000000000000,999999999999999999,100000000000000000,99999999999999999,10000000000000000,9999999999999999,1000000000000000,999999999999999,100000000000000,99999999999999,10000000000000,9999999999999,1000000000000,999999999999,100000000000,99999999999,10000000000,9999999999,1000000000,999999999,100000000,99999999,10000000,9999999,1000000,999999,100000,99999,10000,9999,1000,999,100,99,10,9,1,};for(int i =0; i < samples.Length;++i){long s = samples[i];int a = s.Digits_IfChain();int b = s.Digits_Log10();int c = s.Digits_While();int d = s.Digits_String();if(a != b || c != d || a != c){Console.WriteLine($"Digits({s}): IfChain={a} Log10={b} While={c} String={d}");
isConsistent =false;break;}}// Consistency test result:if(isConsistent)Console.WriteLine("Consistency tests are OK");}}}
Saya suka solusi ini, jauh lebih mudah dibaca daripada trik matematika dan kecepatannya berbicara sendiri, pujian.
MrLore
3
Mengapa ini tidak ditandai sebagai solusi? Performa penting dan ini tampaknya merupakan jawaban yang paling luas.
Martien de Jong
Menarik, saya mendapatkan hasil yang berbeda . Untuk nilai acak Log10 dan brute force hampir sama tetapi untuk long.MaxValueLog10 jauh lebih baik. Atau hanya di .NET Core?
György Kőszeg
@ GyörgyKőszeg: Saya telah menambahkan tes untuk Int64. Perlu diketahui bahwa pengujian untuk Int32dan Int64menghasilkan kumpulan data yang berbeda, yang mungkin menjelaskan mengapa Int64menjadi lebih cepat daripada Int32dalam beberapa kasus. Meskipun, dalam Int32pengujian dan dalam Int64pengujian, kumpulan data tidak berubah saat menguji metode penghitungan yang berbeda. Sekarang mengenai .NET Core, saya ragu ada optimasi ajaib di pustaka Matematika yang akan mengubah hasil ini, tetapi saya ingin mendengar lebih banyak tentang itu (jawaban saya sudah sangat besar, mungkin salah satu yang terbesar di SO ;-)
sɐunıɔ ןɐ qɐp
@ GyörgyKőszeg: Selain itu, pengukuran kinerja tingkat rendah sangat rumit. Saya biasanya lebih suka untuk menjaga kode sesederhana mungkin (saya lebih suka sederhana forloop lebih enumerations, saya pra-proses dataset acak, dan menghindari penggunaan obat generik, Tugas, Function<>, Action<>, atau kerangka pengukuran hitam-kotak). Singkatnya, tetap sederhana. Saya juga mematikan semua aplikasi yang tidak perlu (Skype, Windows Defender, menonaktifkan Anti-Virus, Chrome, cache Microsoft Office, dll).
sɐunıɔ ןɐ qɐp
13
Bukan langsung C #, tapi rumusnya adalah: n = floor(log10(x)+1)
@Kl - log10 (0) sebenarnya tidak ditentukan. Tapi, Anda benar karena ini adalah kasus khusus yang perlu diuji dan diperlakukan secara terpisah. Ini juga berlaku untuk bilangan bulat non positif. Lihat komentar untuk jawaban Steve.
ysap
@ysap: Log10 cukup rumit untuk bekerja dengan benar. Apakah Anda tahu cara menerapkannya dengan benar untuk semua rentang nilai masukan yang mungkin?
sɐunıɔ ןɐ qɐp
@ sɐunıɔ ןɐ qɐp - log10dalam banyak kasus merupakan fungsi perpustakaan. Mengapa Anda ingin menerapkannya sendiri, dan masalah apa yang Anda temui? log10(x) = log2(x) / log2(10), atau secara umum logA(x) = logB(x) / logB(A).
ysap
Saya tidak bermaksud menerapkan Log10 lagi, maksud saya Log10(0)adalah -infinity. Log10 tidak dapat digunakan untuk menghitung jumlah digit angka negatif kecuali Anda menggunakan Math.Abs()sebelum meneruskan nilai ke Log10. Tapi kemudian Math.Abs(int.MinValue)melempar Exception ( long.MinValuejuga, dalam kasus Int64). Jika kita mentransmisikan nomor menjadi dua kali lipat sebelum meneruskannya ke Log10, maka itu berfungsi untuk hampir semua nomor kecuali -999999999999999999(dalam kasus Int64). Apakah Anda tahu rumus untuk menghitung jumlah digit yang menggunakan log10 dan menerima nilai int32 atau int64 sebagai input dan output hanya nilai yang valid?
sɐunıɔ ןɐ qɐp
9
Jawaban sudah ada di sini berfungsi untuk bilangan bulat tak bertanda tangan, tetapi saya belum menemukan solusi yang baik untuk mendapatkan jumlah digit dari desimal dan ganda.
publicstaticintLength(double number){
number =Math.Abs(number);int length =1;while((number /=10)>=1)
length++;return length;}//number of digits in 0 = 1,//number of digits in 22.1 = 2,//number of digits in -23 = 2
Anda dapat mengubah jenis masukan dari doublemenjadi decimaljika penting, tetapi desimal juga memiliki batas.
Berikut implementasi menggunakan pencarian biner. Tampaknya menjadi yang tercepat sejauh ini di int32.
Implementasi Int64 dibiarkan sebagai latihan untuk pembaca (!)
Saya mencoba menggunakan Array.BinarySearch daripada melakukan hard-coding pada pohon, tetapi itu sekitar setengah dari kecepatannya.
EDIT: Tabel pencarian jauh lebih cepat daripada pencarian biner, dengan mengorbankan lebih banyak memori. Secara realistis saya mungkin akan menggunakan pencarian biner dalam produksi, tabel pencarian adalah banyak kerumitan untuk mendapatkan kecepatan yang cenderung dibayangi oleh bagian lain dari perangkat lunak.
Lookup-Table:439 ms
Binary-Search:1069 ms
If-Chain:1409 ms
Log10:1145 ms
While:1768 ms
String:5153 ms
Versi tabel pencarian:
staticbyte[] _0000llll =newbyte[0x10000];staticbyte[]_FFFFllll=newbyte[0x10001];staticsbyte[] _hhhhXXXXdigits =newsbyte[0x10000];// Special cases where the high DWORD is not enough information to find out how// many digits.staticushort[] _lowordSplits =newushort[12];staticsbyte[] _lowordSplitDigitsLT =newsbyte[12];staticsbyte[] _lowordSplitDigitsGE =newsbyte[12];staticInt32Extensions(){// Simple lookup tables for number of digits where value is // 0000xxxx (0 .. 65535)// or FFFFxxxx (-1 .. -65536)
precomputePositiveLo16();
precomputeNegativeLo16();// Hiword is a little more complex
precomputeHiwordDigits();}privatestaticvoid precomputeHiwordDigits(){int b =0;for(int hhhh =0; hhhh <=0xFFFF; hhhh++){// For hiword hhhh, calculate integer value for loword of 0000 and FFFF.int hhhh0000 =(unchecked(hhhh *0x10000));// wrap around on negativesint hhhhFFFF = hhhh0000 +0xFFFF;// How many decimal digits for each?int digits0000 = hhhh0000.Digits_IfChain();int digitsFFFF = hhhhFFFF.Digits_IfChain();// If same number of decimal digits, we know that when we see that hiword// we don't have to look at the loword to know the right answer.if(digits0000 == digitsFFFF){
_hhhhXXXXdigits[hhhh]=(sbyte)digits0000;}else{bool negative = hhhh >=0x8000;// Calculate 10, 100, 1000, 10000 etcint tenToThePower =(int)Math.Pow(10,(negative ? digits0000 : digitsFFFF)-1);// Calculate the loword of the 10^n value.ushort lowordSplit =unchecked((ushort)tenToThePower);if(negative)
lowordSplit =unchecked((ushort)(2+(ushort)~lowordSplit));// Store the split point and digits into these arrays
_lowordSplits[b]= lowordSplit;
_lowordSplitDigitsLT[b]=(sbyte)digits0000;
_lowordSplitDigitsGE[b]=(sbyte)digitsFFFF;// Store the minus of the array index into the digits lookup. We look for// minus values and use these to trigger using the split points logic.
_hhhhXXXXdigits[hhhh]=(sbyte)(-b);
b++;}}}privatestaticvoid precomputePositiveLo16(){for(int i =0; i <=9; i++)
_0000llll[i]=1;for(int i =10; i <=99; i++)
_0000llll[i]=2;for(int i =100; i <=999; i++)
_0000llll[i]=3;for(int i =1000; i <=9999; i++)
_0000llll[i]=4;for(int i =10000; i <=65535; i++)
_0000llll[i]=5;}privatestaticvoid precomputeNegativeLo16(){for(int i =0; i <=9; i++)_FFFFllll[65536- i]=1;for(int i =10; i <=99; i++)_FFFFllll[65536- i]=2;for(int i =100; i <=999; i++)_FFFFllll[65536- i]=3;for(int i =1000; i <=9999; i++)_FFFFllll[65536- i]=4;for(int i =10000; i <=65535; i++)_FFFFllll[65536- i]=5;}publicstaticintDigits_LookupTable(thisint n){// Split input into low word and high word.ushort l =unchecked((ushort)n);ushort h =unchecked((ushort)(n >>16));// If the hiword is 0000 or FFFF we have precomputed tables for these.if(h ==0x0000){return _0000llll[l];}elseif(h ==0xFFFF){return_FFFFllll[l];}// In most cases the hiword will tell us the number of decimal digits.sbyte digits = _hhhhXXXXdigits[h];// We put a positive number in this lookup table when// hhhh0000 .. hhhhFFFF all have the same number of decimal digits.if(digits >0)return digits;// Where the answer is different for hhhh0000 to hhhhFFFF, we need to// look up in a separate array to tell us at what loword the change occurs.var splitIndex =(sbyte)(-digits);ushort lowordSplit = _lowordSplits[splitIndex];// Pick the correct answer from the relevant array, depending whether// our loword is lower than the split point or greater/equal. Note that for// negative numbers, the loword is LOWER for MORE decimal digits.if(l < lowordSplit)return _lowordSplitDigitsLT[splitIndex];elsereturn _lowordSplitDigitsGE[splitIndex];}
Pendekatan yang sangat menarik. Ini memang lebih cepat daripada metode "Log10", "string.Length", dan "While" untuk nilai integer yang terdistribusi secara seragam. Dalam skenario kasus nyata, distribusi nilai integer harus selalu dipertimbangkan pada solusi if-chain-like. +1
sɐunıɔ ןɐ qɐp
Pendekatan LookUpTable tampaknya super cepat untuk skenario di mana akses memori bukan penghambat. Saya sangat percaya bahwa untuk skenario dengan akses memori yang sering, LookUpTable menjadi lebih lambat daripada metode if-chain-like, seperti BinSearch yang Anda sarankan. Omong-omong, apakah Anda memiliki Int64implementasi untuk LookUpTable? Atau menurut Anda terlalu rumit untuk mengimplementasikannya? Saya ingin menjalankan tes kinerja nanti pada set lengkap.
sɐunıɔ ןɐ qɐp
Hei, tidak sampai yang 64-bit. Prinsipnya harus sedikit berbeda karena Anda memerlukan level 4x daripada hanya kata tinggi dan nada rendah. Sangat setuju bahwa di dunia nyata, cache CPU Anda akan memiliki banyak kebutuhan lain yang bersaing untuk ruang, dan ada banyak ruang untuk perbaikan dalam mengurangi ukuran pencarian (>> 1 maka angka genap hanya muncul dalam pikiran) . Pencarian biner satu dapat ditingkatkan dengan condong ke 9,10,8 digit bukannya 1,2,3,4 - mengingat distribusi kumpulan data acak Anda.
Alan Singfield
1
membagi angka dengan 10 akan menghasilkan digit paling kiri kemudian melakukan mod 10 pada nomor tersebut memberikan nomor tanpa digit pertama dan ulangi sampai Anda memiliki semua digit
Ini terasa seperti pendekatan yang lebih intuitif bagi saya saat menangani masalah ini. Saya mencobaLog10 metode ini terlebih dahulu karena kesederhanaannya yang tampak, tetapi metode ini memiliki jumlah kasus sudut dan masalah presisi yang tidak masuk akal.
Saya juga menemukan if -chain yang diusulkan dalam jawaban lain agak jelek untuk dilihat.
Saya tahu ini bukan metode yang paling efisien, tetapi ini memberi Anda ekstensi lain untuk mengembalikan angka juga untuk penggunaan lain (Anda bisa menandainya privatejika Anda tidak perlu menggunakannya di luar kelas).
Perlu diingat bahwa tanda negatif tidak dianggap sebagai digit.
Mengalokasikan string sama sekali tidak diperlukan.
Krythic
-2
Itu tergantung apa sebenarnya yang ingin Anda lakukan dengan angka tersebut. Anda dapat mengulang melalui digit mulai dari yang terakhir hingga yang pertama seperti ini:
Jawaban:
Tanpa mengonversi menjadi string, Anda dapat mencoba:
Koreksi mengikuti komentar ysap:
sumber
n
yaitu0
hanya dapat kembali1
:) Terlalu pegangan nilai-nilai negatif hanya menggantin
denganMath.Abs(n)
.Coba ini:
Apakah itu bekerja ?
sumber
int
, jadi saya berasumsi itu bukan masalah.)Solusinya
Salah satu dari metode ekstensi berikut akan melakukan pekerjaan itu. Semuanya menganggap tanda minus sebagai digit, dan berfungsi dengan benar untuk semua kemungkinan nilai input. Mereka juga bekerja untuk .NET Framework dan .NET Core. Namun ada perbedaan kinerja yang relevan (dibahas di bawah), tergantung pada pilihan Platform / Kerangka Anda.
Versi int32:
Versi Int64:
Diskusi
Jawaban ini mencakup tes yang dilakukan untuk keduanya
Int32
danInt64
jenis, menggunakan larik100.000.000
sampel acakint
/long
angka . Dataset acak diproses sebelumnya menjadi larik sebelum menjalankan pengujian.Tes konsistensi antara 4 metode yang berbeda juga dieksekusi, untuk
MinValue
, kasus perbatasan negatif,-1
,0
,1
, kasus perbatasan yang positif,MaxValue
dan juga untuk dataset acak seluruh. Tidak ada uji konsistensi yang gagal untuk metode yang disediakan di atas, KECUALI untuk metode LOG10 (ini akan dibahas nanti).Tes dilaksanakan pada
.NET Framework 4.7.2
dan.NET Core 2.2
; untukx86
danx64
platform, pada mesin Prosesor Intel 64-bit, denganWindows 10
, dan denganVS2017 v.15.9.17
. 4 kasus berikut memiliki efek yang sama pada hasil kinerja:.NET Framework (x86)
Platform = x86
Platform = AnyCPU
,Prefer 32-bit
dicentang dalam pengaturan proyek.NET Framework (x64)
Platform = x64
Platform = AnyCPU
,Prefer 32-bit
tidak dicentang di setelan proyek.NET Core (x86)
"C:\Program Files (x86)\dotnet\dotnet.exe" bin\Release\netcoreapp2.2\ConsoleApp.dll
"C:\Program Files (x86)\dotnet\dotnet.exe" bin\x86\Release\netcoreapp2.2\ConsoleApp.dll
.NET Core (x64)
"C:\Program Files\dotnet\dotnet.exe" bin\Release\netcoreapp2.2\ConsoleApp.dll
"C:\Program Files\dotnet\dotnet.exe" bin\x64\Release\netcoreapp2.2\ConsoleApp.dll
Hasil
Uji kinerja di bawah ini menghasilkan distribusi nilai yang seragam di antara berbagai nilai yang dapat diasumsikan oleh integer. Ini berarti ada peluang yang jauh lebih tinggi untuk menguji nilai dengan jumlah digit yang besar. Dalam skenario kehidupan nyata, sebagian besar nilai mungkin kecil, jadi IF-CHAIN akan bekerja lebih baik. Selanjutnya, prosesor akan menyimpan dan mengoptimalkan keputusan IF-CHAIN sesuai dengan kumpulan data Anda.
Seperti yang ditunjukkan @AlanSingfield di bagian komentar, metode LOG10 harus diperbaiki dengan casting ke
double
dalamMath.Abs()
untuk kasus ketika nilai input adalahint.MinValue
ataulong.MinValue
.Mengenai tes kinerja awal yang saya terapkan sebelum mengedit pertanyaan ini (sudah diedit jutaan kali), ada kasus khusus yang ditunjukkan oleh @ GyörgyKőszeg , di mana metode IF-CHAIN bekerja lebih lambat daripada metode LOG10.
Ini masih terjadi, meskipun besarnya perbedaan menjadi jauh lebih rendah setelah perbaikan untuk masalah yang ditunjukkan oleh @AlanSingfield . Perbaikan ini (menambahkan cast ke
double
) menyebabkan kesalahan komputasi ketika nilai inputnya tepat-999999999999999999
: metode LOG10 mengembalikan,20
bukan19
. Metode LOG10 juga harus memilikiif
pelindung untuk kasus ketika nilai input adalah nol.Metode LOG10 cukup rumit untuk berfungsi untuk semua nilai, yang berarti Anda harus menghindarinya. Jika seseorang menemukan cara untuk membuatnya bekerja dengan benar untuk semua tes konsistensi di bawah ini, silakan kirim komentar!
Metode WHILE juga mendapat versi refactored terbaru yang lebih cepat, tetapi masih lambat
Platform = x86
(saya tidak dapat menemukan alasan mengapa, sampai sekarang).Metode STRING selalu lambat: metode ini dengan rakus mengalokasikan terlalu banyak memori untuk apa-apa. Menariknya, di .NET Core, alokasi string tampaknya jauh lebih cepat daripada di .NET Framework. Senang mendengarnya.
Metode IF-CHAIN harus mengungguli semua metode lain dalam 99,99% kasus; dan, menurut pendapat pribadi saya, adalah pilihan terbaik Anda (mempertimbangkan semua penyesuaian yang diperlukan untuk membuat metode LOG10 berfungsi dengan benar, dan kinerja buruk dari dua metode lainnya).
Akhirnya, hasilnya adalah:
Karena hasil ini bergantung pada perangkat keras, saya sarankan untuk tetap menjalankan tes kinerja di bawah ini di komputer Anda sendiri jika Anda benar-benar perlu 100% yakin dalam kasus khusus Anda.
Kode Tes
Di bawah ini adalah kode untuk uji kinerja, dan juga uji konsistensi. Kode yang sama digunakan untuk .NET Framework dan .NET Core.
sumber
long.MaxValue
Log10 jauh lebih baik. Atau hanya di .NET Core?Int32
danInt64
menghasilkan kumpulan data yang berbeda, yang mungkin menjelaskan mengapaInt64
menjadi lebih cepat daripadaInt32
dalam beberapa kasus. Meskipun, dalamInt32
pengujian dan dalamInt64
pengujian, kumpulan data tidak berubah saat menguji metode penghitungan yang berbeda. Sekarang mengenai .NET Core, saya ragu ada optimasi ajaib di pustaka Matematika yang akan mengubah hasil ini, tetapi saya ingin mendengar lebih banyak tentang itu (jawaban saya sudah sangat besar, mungkin salah satu yang terbesar di SO ;-)for
loop lebihenumerations
, saya pra-proses dataset acak, dan menghindari penggunaan obat generik, Tugas,Function<>
,Action<>
, atau kerangka pengukuran hitam-kotak). Singkatnya, tetap sederhana. Saya juga mematikan semua aplikasi yang tidak perlu (Skype, Windows Defender, menonaktifkan Anti-Virus, Chrome, cache Microsoft Office, dll).Bukan langsung C #, tapi rumusnya adalah:
n = floor(log10(x)+1)
sumber
log10
dalam banyak kasus merupakan fungsi perpustakaan. Mengapa Anda ingin menerapkannya sendiri, dan masalah apa yang Anda temui?log10(x) = log2(x) / log2(10)
, atau secara umumlogA(x) = logB(x) / logB(A)
.Log10(0)
adalah -infinity. Log10 tidak dapat digunakan untuk menghitung jumlah digit angka negatif kecuali Anda menggunakanMath.Abs()
sebelum meneruskan nilai ke Log10. Tapi kemudianMath.Abs(int.MinValue)
melempar Exception (long.MinValue
juga, dalam kasus Int64). Jika kita mentransmisikan nomor menjadi dua kali lipat sebelum meneruskannya ke Log10, maka itu berfungsi untuk hampir semua nomor kecuali-999999999999999999
(dalam kasus Int64). Apakah Anda tahu rumus untuk menghitung jumlah digit yang menggunakan log10 dan menerima nilai int32 atau int64 sebagai input dan output hanya nilai yang valid?Jawaban sudah ada di sini berfungsi untuk bilangan bulat tak bertanda tangan, tetapi saya belum menemukan solusi yang baik untuk mendapatkan jumlah digit dari desimal dan ganda.
Anda dapat mengubah jenis masukan dari
double
menjadidecimal
jika penting, tetapi desimal juga memiliki batas.sumber
Jawaban Steve benar , tetapi tidak berfungsi untuk bilangan bulat kurang dari 1.
Berikut versi terbaru yang berfungsi untuk negatif:
sumber
digits = n == 0 ? 1 : (int)Math.Floor(Math.Log10(Math.Abs(n)) + 1);
n = int.MinValue
.Menggunakan rekursi (terkadang ditanyakan pada wawancara)
sumber
number = int.MinValue
.sumber
-1
= 2Berikut implementasi menggunakan pencarian biner. Tampaknya menjadi yang tercepat sejauh ini di int32.
Implementasi Int64 dibiarkan sebagai latihan untuk pembaca (!)
Saya mencoba menggunakan Array.BinarySearch daripada melakukan hard-coding pada pohon, tetapi itu sekitar setengah dari kecepatannya.
EDIT: Tabel pencarian jauh lebih cepat daripada pencarian biner, dengan mengorbankan lebih banyak memori. Secara realistis saya mungkin akan menggunakan pencarian biner dalam produksi, tabel pencarian adalah banyak kerumitan untuk mendapatkan kecepatan yang cenderung dibayangi oleh bagian lain dari perangkat lunak.
Versi tabel pencarian:
Versi pencarian biner
sumber
Int64
implementasi untuk LookUpTable? Atau menurut Anda terlalu rumit untuk mengimplementasikannya? Saya ingin menjalankan tes kinerja nanti pada set lengkap.membagi angka dengan 10 akan menghasilkan digit paling kiri kemudian melakukan mod 10 pada nomor tersebut memberikan nomor tanpa digit pertama dan ulangi sampai Anda memiliki semua digit
sumber
sumber
string.TrimStart('-')
lebih baikBuat metode yang mengembalikan semua digit, dan metode lain yang menghitungnya:
Ini terasa seperti pendekatan yang lebih intuitif bagi saya saat menangani masalah ini. Saya mencoba
Log10
metode ini terlebih dahulu karena kesederhanaannya yang tampak, tetapi metode ini memiliki jumlah kasus sudut dan masalah presisi yang tidak masuk akal.Saya juga menemukan
if
-chain yang diusulkan dalam jawaban lain agak jelek untuk dilihat.Saya tahu ini bukan metode yang paling efisien, tetapi ini memberi Anda ekstensi lain untuk mengembalikan angka juga untuk penggunaan lain (Anda bisa menandainya
private
jika Anda tidak perlu menggunakannya di luar kelas).Perlu diingat bahwa tanda negatif tidak dianggap sebagai digit.
sumber
dikonversi menjadi string dan kemudian Anda dapat menghitung angka tatal angka dengan metode .length. Suka:
sumber
Itu tergantung apa sebenarnya yang ingin Anda lakukan dengan angka tersebut. Anda dapat mengulang melalui digit mulai dari yang terakhir hingga yang pertama seperti ini:
sumber
%
untuk mendapatkan digitnya, dan kemudian/=
memotongnya.Jika hanya untuk memvalidasi Anda dapat melakukan:
887979789 > 99999999
sumber
Dengan asumsi pertanyaan Anda mengacu pada int, berikut ini berfungsi untuk negatif / positif dan nol juga:
sumber