Obawiam się, że ceil (log10 (10)) = ceil (1) = 1, a nie 2, jak powinno być w przypadku tego pytania!
ysap
3
Dzięki, to niezła metoda. Chociaż nie jest szybsza niż int count = 0; do {count ++; } while ((i / = 10)> = 1); :(
Puterdo Borato
3
Jeśli twój zakres liczb zawiera liczby ujemne, musisz użyć Math.Floor (Math.Log10 (Math.Abs (n)) + 1);
mrcrowl
1
Cóż, jeśli nto 0może po prostu zwrócić 1:) Wartości ujemne zbytnio obsłużą, po prostu zastąp nje Math.Abs(n).
Umair
3
@Puterdo Borato: mój test wydajności faktycznie wykazał, że twoja metoda jest szybsza, gdy liczba cyfr jest <5. Pomiń, Math.floor Steve'a jest szybszy.
Warto zauważyć, że prawdopodobnie napotkasz problemy z tą metodą, jeśli masz do czynienia z liczbami ujemnymi. (I oczywiście ułamki dziesiętne, ale w przykładzie użyto znaku int, więc zakładam, że to nie problem.)
Cody Gray
2
@Krythic przydzielanie ciągów znaków to nowy szał w świecie .NET.
nawfal
1
Nowy? Ledwie. W 2010 roku rażąco przydzielałem ciągi znaków. Co za wyznacznik trendów. Lol. Masz jednak rację. To jest brudne!
Andiih,
3
@Krythic To nie lata 80., Twój komputer ma wystarczającą ilość pamięci RAM, aby zapisać w pamięci ciąg 10 znaków na czas jednej operacji.
MrLore
2
@MrLore W prostych aplikacjach może to być prawda, ale w świecie tworzenia gier to zupełnie inna bestia.
Krythic
48
Rozwiązanie
Dowolna z poniższych metod rozszerzających wykona zadanie. Wszystkie traktują znak minus jako cyfrę i działają poprawnie dla wszystkich możliwych wartości wejściowych. Działają również dla .NET Framework i .NET Core. Istnieją jednak istotne różnice w wydajności (omówione poniżej), w zależności od wybranej platformy / struktury.
Odpowiedź ta obejmuje testy wykonywane zarówno Int32i Int64rodzaju, z wykorzystaniem tablicy 100.000.000losowo wybranych int/ longnumerów. Losowy zestaw danych jest wstępnie przetwarzany na tablicę przed wykonaniem testów.
Testy spójności między 4 różnymi metodami również zostały wykonane, na MinValue, negatywnych przypadkach granicznych -1, 0, 1, pozytywne przypadki graniczne, MaxValuei również dla całego zestawu danych losowych. Żadne testy spójności nie kończą się niepowodzeniem w przypadku powyższych metod, Z WYJĄTKIEM metody LOG10 (zostanie to omówione później).
Testy zostały wykonane na .NET Framework 4.7.2i .NET Core 2.2; dla platform x86i x64platform, na komputerze z 64-bitowym procesorem Intel, zi Windows 10z VS2017 v.15.9.17. Poniższe 4 przypadki mają taki sam wpływ na wyniki wydajności:
.NET Framework (x86)
Platform = x86
Platform = AnyCPU, Prefer 32-bitjest zaznaczone w ustawieniach projektu
.NET Framework (x64)
Platform = x64
Platform = AnyCPU, Prefer 32-bitnie jest zaznaczone w ustawieniach projektu
Poniższe testy wydajności dają jednolity rozkład wartości w szerokim zakresie wartości, jakie może przyjąć liczba całkowita. Oznacza to, że istnieje znacznie większa szansa na testowanie wartości z dużą liczbą cyfr. W rzeczywistych scenariuszach większość wartości może być małych, więc IF-CHAIN powinien działać jeszcze lepiej. Ponadto procesor będzie buforował i optymalizował decyzje IF-CHAIN zgodnie z Twoim zbiorem danych.
Jak @AlanSingfield wskazał w sekcji komentarzy, metoda LOG10 musiała zostać naprawiona z rzutowaniem do doublewewnątrz Math.Abs()w przypadku, gdy wartością wejściową jest int.MinValuelub long.MinValue.
Jeśli chodzi o wczesne testy wydajności, które zaimplementowałem przed edycją tego pytania (musiało być już edytowane milion razy), @ GyörgyKőszeg wskazał konkretny przypadek , w którym metoda IF-CHAIN działa wolniej niż metoda LOG10.
Dzieje się tak nadal, chociaż skala różnicy stała się znacznie mniejsza po rozwiązaniu problemu wskazanego przez @AlanSingfield . Ta poprawka (dodanie rzutowania double) powoduje błąd obliczeniowy, gdy wartość wejściowa jest dokładnie -999999999999999999: metoda LOG10 zwraca 20zamiast 19. Metoda LOG10 musi również mieć ifochronę na wypadek, gdy wartość wejściowa wynosi zero.
Metoda LOG10 jest dość trudna do uzyskania działania dla wszystkich wartości, co oznacza, że należy jej unikać. Jeśli ktoś znajdzie sposób na poprawne działanie wszystkich poniższych testów spójności, napisz komentarz!
Metoda WHILE również otrzymała ostatnio refaktoryzowaną wersję, która jest szybsza, ale nadal działa wolno Platform = x86(do tej pory nie mogłem znaleźć powodu dlaczego).
Metoda STRING jest konsekwentnie powolna: łapczywie przydziela zbyt dużo pamięci na nic. Co ciekawe, w .NET Core alokacja ciągów wydaje się być znacznie szybsza niż w .NET Framework. Dobrze wiedzieć.
Metoda IF-CHAIN powinna przewyższać wszystkie inne metody w 99,99% przypadków; i, moim zdaniem, jest to najlepszy wybór (biorąc pod uwagę wszystkie poprawki niezbędne do prawidłowego działania metody LOG10 oraz słabe działanie pozostałych dwóch metod).
Ostatecznie wyniki są następujące:
Ponieważ wyniki te są zależne od sprzętu, mimo wszystko zalecam przeprowadzenie poniższych testów wydajności na własnym komputerze, jeśli naprawdę potrzebujesz 100% pewności w swoim konkretnym przypadku.
Kod testowy
Poniżej znajduje się kod testu wydajności, a także testu spójności. Ten sam kod jest używany zarówno dla .NET Framework, jak i .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");}}}
Podoba mi się to rozwiązanie, jest dużo bardziej czytelne niż sztuczki matematyczne, a szybkość mówi sama za siebie, chwała.
MrLore,
3
Dlaczego nie jest to oznaczone jako rozwiązanie? Wydajność ma znaczenie i wydaje się, że jest to najbardziej obszerna odpowiedź.
Martien de Jong
Co ciekawe, otrzymuję różne wyniki . Dla wartości losowych Log10 i brutalna siła są prawie takie same, ale dla long.MaxValueLog10 jest znacznie lepsze. A może tylko w .NET Core?
György Kőszeg
@ GyörgyKőszeg: Dodałem testy dla Int64. Należy pamiętać, że testy Int32i Int64generują różne zestawy danych, co może wyjaśniać, dlaczego Int64stało się to szybciej niż Int32w niektórych przypadkach. Chociaż w ramach Int32testu i w ramach Int64testu zbiory danych nie ulegają zmianie podczas testowania różnych metod obliczeniowych. Jeśli chodzi o .NET Core, wątpię, czy jest jakaś magiczna optymalizacja w bibliotece Math, która zmieniłaby te wyniki, ale chciałbym usłyszeć więcej na ten temat (moja odpowiedź jest już ogromna, prawdopodobnie jedna z największych w SO ;-)
sɐunıɔ ןɐ qɐp
@ GyörgyKőszeg: Również pomiary wydajności na niskim poziomie są bardzo trudne. I zazwyczaj wolą zachować kod jak najprostsze (wolę proste forpętle nad enumerations, I pre-process losowe zestawy danych i unikanie stosowania leków generycznych, zadania Function<>, Action<>lub jakiegokolwiek czarnym-box ramach pomiaru). Podsumowując, nie komplikuj. Zabijam też wszystkie niepotrzebne aplikacje (Skype, Windows Defender, wyłączam antywirusa, Chrome, pamięć podręczną Microsoft Office itp.).
sɐunıɔ ןɐ qɐp
13
Nie bezpośrednio C #, ale formuła jest taka: n = floor(log10(x)+1)
@Klaus - log10 (0) jest faktycznie niezdefiniowane. Ale masz rację, ponieważ jest to szczególny przypadek, który należy zbadać i potraktować oddzielnie. Dotyczy to również wszystkich nie dodatnich liczb całkowitych. Zobacz komentarze do odpowiedzi Steve'a.
ysap
@ysap: Log10 jest dość trudny do poprawnego działania. Czy masz pomysł, jak go poprawnie zaimplementować dla wszystkich możliwych wartości wejściowych?
sɐunıɔ ןɐ qɐp
@ sɐunıɔ ןɐ qɐp - log10w większości przypadków jest funkcją biblioteczną. Dlaczego miałbyś chcieć to wdrożyć samodzielnie i jakie problemy napotykasz? log10(x) = log2(x) / log2(10)lub ogólnie logA(x) = logB(x) / logB(A).
ysap
Nie chciałem ponownie zaimplementować Log10, mam na myśli Log10(0)to-nieskończoność. Log10 nie może służyć do obliczania liczby cyfr liczb ujemnych, chyba że użyjesz go Math.Abs()przed przekazaniem wartości do Log10. Ale potem Math.Abs(int.MinValue)zgłasza wyjątek ( long.MinValuetakże w przypadku Int64). Jeśli -999999999999999999rzucimy liczbę na podwojenie przed przekazaniem jej do Log10, to działa ona dla prawie wszystkich liczb z wyjątkiem (w przypadku Int64). Czy znasz jakąś formułę do obliczania liczby cyfr, która używa log10 i akceptuje dowolną wartość int32 lub int64 jako dane wejściowe i wyświetla tylko prawidłowe wartości?
sɐunıɔ ןɐ qɐp
9
Odpowiedzi już tutaj działają dla liczb całkowitych bez znaku, ale nie znalazłem dobrego rozwiązania, aby uzyskać liczbę cyfr z liczb dziesiętnych i podwójnych.
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
Możesz zmienić typ danych wejściowych z doublena, decimaljeśli liczy się precyzja, ale liczba dziesiętna również ma limit.
Oto implementacja wykorzystująca wyszukiwanie binarne. Wygląda na to, że jak dotąd jest najszybszy na int32.
Implementację Int64 pozostawiono jako ćwiczenie dla czytelnika (!)
Próbowałem użyć Array.BinarySearch zamiast kodowania drzewa na stałe, ale to było o połowę wolniejsze.
EDYCJA: Tabela przeglądowa jest znacznie szybsza niż wyszukiwanie binarne kosztem użycia większej ilości pamięci. Realistycznie rzecz biorąc, prawdopodobnie użyłbym wyszukiwania binarnego w środowisku produkcyjnym, tabela wyszukiwania jest bardzo złożona, jeśli chodzi o wzrost szybkości, który prawdopodobnie zostanie przyćmiony przez inne części oprogramowania.
Lookup-Table:439 ms
Binary-Search:1069 ms
If-Chain:1409 ms
Log10:1145 ms
While:1768 ms
String:5153 ms
Wersja tabeli przeglądowej:
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];}
Bardzo ciekawe podejście. Jest rzeczywiście szybszy niż metody „Log10”, „string.Length” i „While” dla równomiernie rozłożonych wartości całkowitych. W rzeczywistych przypadkach rozkład wartości całkowitych musi być zawsze brany pod uwagę w rozwiązaniach typu if-chain. +1
sɐunıɔ ןɐ qɐp
Podejście LookUpTable wydaje się być bardzo szybkie w scenariuszach, w których dostęp do pamięci nie jest wąskim gardłem. Jestem głęboko przekonany, że w scenariuszach z częstym dostępem do pamięci LookUpTable działa wolniej niż metody łańcuchowe typu if, takie jak zasugerowana przez BinSearch. Przy okazji, czy masz Int64implementację LookUpTable? A może uważasz, że wdrożenie go jest zbyt skomplikowane? Chciałbym przeprowadzić testy wydajności później na całym zestawie.
sɐunıɔ ןɐ qɐp
Hej, nie dotarłem aż do wersji 64-bitowej. Zasada musiałaby być nieco inna, ponieważ potrzebujesz 4x poziomów, a nie tylko hiword i loword. Zdecydowanie zgadzam się, że w prawdziwym świecie pamięć podręczna procesora będzie miała wiele innych konkurencyjnych potrzeb w zakresie przestrzeni i jest dużo miejsca na poprawę w zmniejszaniu rozmiaru wyszukiwania (>> 1 wtedy przychodzą na myśl tylko liczby parzyste) . Wyszukiwanie binarne można poprawić, odchylając w kierunku 9,10,8 cyfr zamiast 1,2,3,4 - biorąc pod uwagę rozkład losowego zestawu danych.
Alan Singfield
1
podzielenie liczby przez 10 da ci ostatnią cyfrę z lewej strony, a następnie wykonanie mod 10 na liczbie da liczbę bez pierwszej cyfry i powtórz to, aż będziesz miał wszystkie cyfry
To było dla mnie bardziej intuicyjne podejście do rozwiązywania tego problemu. Log10Najpierw wypróbowałem tę metodę ze względu na jej pozorną prostotę, ale ma ona niesamowitą liczbę przypadków narożnych i problemy z precyzją.
Również if-chain zaproponowany w drugiej odpowiedzi uznałem za nieco brzydki.
Wiem, że nie jest to najbardziej wydajna metoda, ale daje ci drugie rozszerzenie do zwracania cyfr, a także do innych zastosowań (możesz je po prostu zaznaczyć, privatejeśli nie musisz używać go poza klasą).
Odpowiedzi:
Bez konwersji na łańcuch możesz spróbować:
Korekta po komentarzu ysap:
źródło
n
to0
może po prostu zwrócić1
:) Wartości ujemne zbytnio obsłużą, po prostu zastąpn
jeMath.Abs(n)
.Spróbuj tego:
Czy to działa ?
źródło
int
, więc zakładam, że to nie problem.)Rozwiązanie
Dowolna z poniższych metod rozszerzających wykona zadanie. Wszystkie traktują znak minus jako cyfrę i działają poprawnie dla wszystkich możliwych wartości wejściowych. Działają również dla .NET Framework i .NET Core. Istnieją jednak istotne różnice w wydajności (omówione poniżej), w zależności od wybranej platformy / struktury.
Wersja Int32:
Wersja Int64:
Dyskusja
Odpowiedź ta obejmuje testy wykonywane zarówno
Int32
iInt64
rodzaju, z wykorzystaniem tablicy100.000.000
losowo wybranychint
/long
numerów. Losowy zestaw danych jest wstępnie przetwarzany na tablicę przed wykonaniem testów.Testy spójności między 4 różnymi metodami również zostały wykonane, na
MinValue
, negatywnych przypadkach granicznych-1
,0
,1
, pozytywne przypadki graniczne,MaxValue
i również dla całego zestawu danych losowych. Żadne testy spójności nie kończą się niepowodzeniem w przypadku powyższych metod, Z WYJĄTKIEM metody LOG10 (zostanie to omówione później).Testy zostały wykonane na
.NET Framework 4.7.2
i.NET Core 2.2
; dla platformx86
ix64
platform, na komputerze z 64-bitowym procesorem Intel, ziWindows 10
zVS2017 v.15.9.17
. Poniższe 4 przypadki mają taki sam wpływ na wyniki wydajności:.NET Framework (x86)
Platform = x86
Platform = AnyCPU
,Prefer 32-bit
jest zaznaczone w ustawieniach projektu.NET Framework (x64)
Platform = x64
Platform = AnyCPU
,Prefer 32-bit
nie jest zaznaczone w ustawieniach projektu.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
Wyniki
Poniższe testy wydajności dają jednolity rozkład wartości w szerokim zakresie wartości, jakie może przyjąć liczba całkowita. Oznacza to, że istnieje znacznie większa szansa na testowanie wartości z dużą liczbą cyfr. W rzeczywistych scenariuszach większość wartości może być małych, więc IF-CHAIN powinien działać jeszcze lepiej. Ponadto procesor będzie buforował i optymalizował decyzje IF-CHAIN zgodnie z Twoim zbiorem danych.
Jak @AlanSingfield wskazał w sekcji komentarzy, metoda LOG10 musiała zostać naprawiona z rzutowaniem do
double
wewnątrzMath.Abs()
w przypadku, gdy wartością wejściową jestint.MinValue
lublong.MinValue
.Jeśli chodzi o wczesne testy wydajności, które zaimplementowałem przed edycją tego pytania (musiało być już edytowane milion razy), @ GyörgyKőszeg wskazał konkretny przypadek , w którym metoda IF-CHAIN działa wolniej niż metoda LOG10.
Dzieje się tak nadal, chociaż skala różnicy stała się znacznie mniejsza po rozwiązaniu problemu wskazanego przez @AlanSingfield . Ta poprawka (dodanie rzutowania
double
) powoduje błąd obliczeniowy, gdy wartość wejściowa jest dokładnie-999999999999999999
: metoda LOG10 zwraca20
zamiast19
. Metoda LOG10 musi również miećif
ochronę na wypadek, gdy wartość wejściowa wynosi zero.Metoda LOG10 jest dość trudna do uzyskania działania dla wszystkich wartości, co oznacza, że należy jej unikać. Jeśli ktoś znajdzie sposób na poprawne działanie wszystkich poniższych testów spójności, napisz komentarz!
Metoda WHILE również otrzymała ostatnio refaktoryzowaną wersję, która jest szybsza, ale nadal działa wolno
Platform = x86
(do tej pory nie mogłem znaleźć powodu dlaczego).Metoda STRING jest konsekwentnie powolna: łapczywie przydziela zbyt dużo pamięci na nic. Co ciekawe, w .NET Core alokacja ciągów wydaje się być znacznie szybsza niż w .NET Framework. Dobrze wiedzieć.
Metoda IF-CHAIN powinna przewyższać wszystkie inne metody w 99,99% przypadków; i, moim zdaniem, jest to najlepszy wybór (biorąc pod uwagę wszystkie poprawki niezbędne do prawidłowego działania metody LOG10 oraz słabe działanie pozostałych dwóch metod).
Ostatecznie wyniki są następujące:
Ponieważ wyniki te są zależne od sprzętu, mimo wszystko zalecam przeprowadzenie poniższych testów wydajności na własnym komputerze, jeśli naprawdę potrzebujesz 100% pewności w swoim konkretnym przypadku.
Kod testowy
Poniżej znajduje się kod testu wydajności, a także testu spójności. Ten sam kod jest używany zarówno dla .NET Framework, jak i .NET Core.
źródło
long.MaxValue
Log10 jest znacznie lepsze. A może tylko w .NET Core?Int32
iInt64
generują różne zestawy danych, co może wyjaśniać, dlaczegoInt64
stało się to szybciej niżInt32
w niektórych przypadkach. Chociaż w ramachInt32
testu i w ramachInt64
testu zbiory danych nie ulegają zmianie podczas testowania różnych metod obliczeniowych. Jeśli chodzi o .NET Core, wątpię, czy jest jakaś magiczna optymalizacja w bibliotece Math, która zmieniłaby te wyniki, ale chciałbym usłyszeć więcej na ten temat (moja odpowiedź jest już ogromna, prawdopodobnie jedna z największych w SO ;-)for
pętle nadenumerations
, I pre-process losowe zestawy danych i unikanie stosowania leków generycznych, zadaniaFunction<>
,Action<>
lub jakiegokolwiek czarnym-box ramach pomiaru). Podsumowując, nie komplikuj. Zabijam też wszystkie niepotrzebne aplikacje (Skype, Windows Defender, wyłączam antywirusa, Chrome, pamięć podręczną Microsoft Office itp.).Nie bezpośrednio C #, ale formuła jest taka:
n = floor(log10(x)+1)
źródło
log10
w większości przypadków jest funkcją biblioteczną. Dlaczego miałbyś chcieć to wdrożyć samodzielnie i jakie problemy napotykasz?log10(x) = log2(x) / log2(10)
lub ogólnielogA(x) = logB(x) / logB(A)
.Log10(0)
to-nieskończoność. Log10 nie może służyć do obliczania liczby cyfr liczb ujemnych, chyba że użyjesz goMath.Abs()
przed przekazaniem wartości do Log10. Ale potemMath.Abs(int.MinValue)
zgłasza wyjątek (long.MinValue
także w przypadku Int64). Jeśli-999999999999999999
rzucimy liczbę na podwojenie przed przekazaniem jej do Log10, to działa ona dla prawie wszystkich liczb z wyjątkiem (w przypadku Int64). Czy znasz jakąś formułę do obliczania liczby cyfr, która używa log10 i akceptuje dowolną wartość int32 lub int64 jako dane wejściowe i wyświetla tylko prawidłowe wartości?Odpowiedzi już tutaj działają dla liczb całkowitych bez znaku, ale nie znalazłem dobrego rozwiązania, aby uzyskać liczbę cyfr z liczb dziesiętnych i podwójnych.
Możesz zmienić typ danych wejściowych z
double
na,decimal
jeśli liczy się precyzja, ale liczba dziesiętna również ma limit.źródło
Odpowiedź Steve'a jest poprawna , ale nie działa dla liczb całkowitych mniejszych niż 1.
Oto zaktualizowana wersja, która działa w przypadku negatywów:
źródło
digits = n == 0 ? 1 : (int)Math.Floor(Math.Log10(Math.Abs(n)) + 1);
n = int.MinValue
.Korzystanie z rekursji (czasami zadawane podczas wywiadów)
źródło
number = int.MinValue
.źródło
-1
= 2Oto implementacja wykorzystująca wyszukiwanie binarne. Wygląda na to, że jak dotąd jest najszybszy na int32.
Implementację Int64 pozostawiono jako ćwiczenie dla czytelnika (!)
Próbowałem użyć Array.BinarySearch zamiast kodowania drzewa na stałe, ale to było o połowę wolniejsze.
EDYCJA: Tabela przeglądowa jest znacznie szybsza niż wyszukiwanie binarne kosztem użycia większej ilości pamięci. Realistycznie rzecz biorąc, prawdopodobnie użyłbym wyszukiwania binarnego w środowisku produkcyjnym, tabela wyszukiwania jest bardzo złożona, jeśli chodzi o wzrost szybkości, który prawdopodobnie zostanie przyćmiony przez inne części oprogramowania.
Wersja tabeli przeglądowej:
Wersja wyszukiwania binarnego
źródło
Int64
implementację LookUpTable? A może uważasz, że wdrożenie go jest zbyt skomplikowane? Chciałbym przeprowadzić testy wydajności później na całym zestawie.podzielenie liczby przez 10 da ci ostatnią cyfrę z lewej strony, a następnie wykonanie mod 10 na liczbie da liczbę bez pierwszej cyfry i powtórz to, aż będziesz miał wszystkie cyfry
źródło
źródło
string.TrimStart('-')
lepiejUtwórz metodę, która zwraca wszystkie cyfry i inną, która je zlicza:
To było dla mnie bardziej intuicyjne podejście do rozwiązywania tego problemu.
Log10
Najpierw wypróbowałem tę metodę ze względu na jej pozorną prostotę, ale ma ona niesamowitą liczbę przypadków narożnych i problemy z precyzją.Również
if
-chain zaproponowany w drugiej odpowiedzi uznałem za nieco brzydki.Wiem, że nie jest to najbardziej wydajna metoda, ale daje ci drugie rozszerzenie do zwracania cyfr, a także do innych zastosowań (możesz je po prostu zaznaczyć,
private
jeśli nie musisz używać go poza klasą).Pamiętaj, że nie traktuje znaku minus jako cyfry.
źródło
zamień na ciąg, a następnie możesz policzyć liczbę cyfr według metody .length. Lubić:
źródło
Zależy, co dokładnie chcesz zrobić z cyframi. Możesz iterować po cyfrach, zaczynając od ostatniej do pierwszej, w ten sposób:
źródło
%
aby uzyskać cyfrę, a następnie/=
ją wyciąć.Jeśli służy to tylko do walidacji, możesz zrobić:
887979789 > 99999999
źródło
Zakładając, że twoje pytanie odnosiło się do int, poniższe działa również dla wartości ujemnych / pozytywnych i zerowych:
źródło