Ich fürchte, Ceil (log10 (10)) = Ceil (1) = 1 und nicht 2, wie es für diese Frage sein sollte!
Ysap
3
Danke, es ist eine schöne Methode. Obwohl es nicht schneller als int count = 0 ist; do {count ++; } while ((i / = 10)> = 1); :(
Puterdo Borato
3
Wenn Ihr Nummernkreis Negative enthält, müssen Sie Math.Floor (Math.Log10 (Math.Abs (n)) + 1) verwenden.
Mrcrowl
1
Nun , wenn nheißt 0kann nur zurückkehren 1:) Too Griff negative Werte ersetzen Sie einfach nmit Math.Abs(n).
Umair
3
@Puterdo Borato: Mein Leistungstest hat tatsächlich gezeigt, dass Ihre Methode schneller ist, wenn die Anzahl der Ziffern <5 ist. Bestehen Sie das, Steve's Math.floor ist schneller.
Es ist erwähnenswert, dass Sie wahrscheinlich auf Probleme mit dieser Methode stoßen, wenn Sie mit negativen Zahlen arbeiten. (Und natürlich Dezimalstellen, aber das Beispiel verwendet eine int, also nehme ich an, dass das kein Problem ist.)
Cody Gray
2
@Krythic String Allocation ist der neue Wahnsinn in der .NET-Welt.
Nawfal
1
Neu? Kaum. Ich habe 2010 ungeheuerlich Saiten vergeben. Was für ein Trendsetter. Lol. Du hast aber recht. Das ist dreckig!
Andiih
3
@Krythic Es ist nicht die 1980er Jahre, Ihr Computer verfügt über genügend RAM, um eine 10-Zeichen-Zeichenfolge für die Dauer eines Vorgangs im Speicher zu speichern.
MrLore
2
@ MrLore In einfachen Anwendungen mag dies zutreffen, aber in der Welt der Spieleentwicklung ist es ein ganz anderes Biest.
Krythic
48
Die Lösung
Jede der folgenden Erweiterungsmethoden erledigt den Job. Alle betrachten das Minuszeichen als Ziffer und funktionieren für alle möglichen Eingabewerte korrekt. Sie funktionieren auch für .NET Framework und .NET Core. Abhängig von Ihrer Wahl der Plattform / des Frameworks gibt es jedoch relevante Leistungsunterschiede (siehe unten).
Diese Antwort enthält Tests, die für beide Int32und Int64Typen unter Verwendung eines Arrays von 100.000.000zufällig ausgewählten int/ longZahlen durchgeführt wurden. Der zufällige Datensatz wird vor dem Ausführen der Tests in ein Array vorverarbeitet.
Konsistenzprüfungen unter den 4 verschiedenen Methoden wurden auch durchgeführt, für die MinValuenegativen Grenzfall -1, 0, 1, positive Grenzfälle, MaxValueund auch für den ganzen Zufallsdatensatz. Für die oben angegebenen Methoden schlagen keine Konsistenztests fehl, AUSSER für die LOG10-Methode (dies wird später erläutert).
Die Tests wurden am .NET Framework 4.7.2und durchgeführt .NET Core 2.2; für x86und x64Plattformen auf einem 64-Bit-Intel-Prozessor mit Windows 10und mitVS2017 v.15.9.17 . Die folgenden 4 Fälle haben den gleichen Effekt auf die Leistungsergebnisse:
.NET Framework (x86)
Platform = x86
Platform = AnyCPU, Prefer 32-bitWird in den Projekteinstellungen überprüft
.NET Framework (x64)
Platform = x64
Platform = AnyCPU, Prefer 32-bitIst in Projekteinstellungen nicht aktiviert
Die folgenden Leistungstests ergeben eine gleichmäßige Verteilung der Werte auf den weiten Wertebereich, den eine Ganzzahl annehmen könnte. Dies bedeutet, dass die Wahrscheinlichkeit, Werte mit einer großen Anzahl von Ziffern zu testen, viel höher ist. In realen Szenarien können die meisten Werte klein sein, daher sollte die IF-CHAIN eine noch bessere Leistung erbringen. Darüber hinaus speichert der Prozessor die IF-CHAIN-Entscheidungen entsprechend Ihrem Datensatz zwischen und optimiert sie.
Wie @AlanSingfield im Kommentarbereich hervorhob, musste die LOG10-Methode für den Fall, dass der Eingabewert oder ist, mit einem Casting nach doubleinnen korrigiert werdenMath.Abs()int.MinValuelong.MinValue .
In Bezug auf die frühen Leistungstests, die ich vor der Bearbeitung dieser Frage implementiert habe (sie musste bereits millionenfach bearbeitet werden), gab es einen speziellen Fall, auf den @ GyörgyKőszeg hingewiesen hat , bei dem die IF-CHAIN-Methode langsamer als die LOG10-Methode ist.
Dies geschieht immer noch, obwohl die Größe des Unterschieds nach der Behebung des von @AlanSingfield hervorgehobenen Problems viel geringer wurde . Dieser Fix (Hinzufügen einer Umwandlung zu double) verursacht einen Berechnungsfehler, wenn der Eingabewert genau ist -999999999999999999: Die LOG10-Methode gibt 20statt zurück 19. Die LOG10-Methode muss auch einen ifSchutz für den Fall haben, dass der Eingabewert Null ist.
Die LOG10-Methode ist ziemlich schwierig, um für alle Werte zu arbeiten, was bedeutet, dass Sie sie vermeiden sollten. Wenn jemand einen Weg findet, es für alle unten aufgeführten Konsistenztests richtig funktionieren zu lassen, schreibe bitte einen Kommentar!
Die WHILE-Methode hat auch eine kürzlich überarbeitete Version erhalten, die schneller ist, aber immer noch langsam ist Platform = x86(ich konnte bis jetzt keinen Grund dafür finden).
Die STRING-Methode ist durchweg langsam: Sie weist gierig zu viel Speicher für nichts zu. Interessanterweise scheint die Zuweisung von Zeichenfolgen in .NET Core viel schneller zu sein als in .NET Framework. Gut zu wissen.
Die IF-CHAIN-Methode sollte in 99,99% der Fälle alle anderen Methoden übertreffen. und meiner persönlichen Meinung nach ist dies Ihre beste Wahl (unter Berücksichtigung aller Anpassungen, die erforderlich sind, damit die LOG10-Methode ordnungsgemäß funktioniert, und der schlechten Leistung der beiden anderen Methoden).
Schließlich sind die Ergebnisse:
Da diese Ergebnisse hardwareabhängig sind, empfehle ich trotzdem, die folgenden Leistungstests auf Ihrem eigenen Computer durchzuführen, wenn Sie in Ihrem speziellen Fall wirklich 100% sicher sein müssen.
Testcode
Unten finden Sie den Code für den Leistungstest und den Konsistenztest. Für .NET Framework und .NET Core wird derselbe Code verwendet.
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");}}}
Ich mag diese Lösung, sie ist viel lesbarer als Mathe-Tricks und die Geschwindigkeit spricht für sich, ein dickes Lob.
MrLore
3
Warum ist dies nicht als Lösung gekennzeichnet? Leistung ist wichtig und dies scheint die umfassendste Antwort zu sein.
Martien de Jong
Interessant, ich bekomme unterschiedliche Ergebnisse . Für zufällige Werte sind Log10 und Brute Force fast gleich, für long.MaxValueLog10 jedoch deutlich besser. Oder ist es nur in .NET Core?
György Kőszeg
@ GyörgyKőszeg: Ich habe Tests für Int64 hinzugefügt. Bitte beachten Sie, dass die Tests für Int32und Int64unterschiedliche Datensätze generieren, was erklären kann, warum Int64schneller als Int32in einigen Fällen. Obwohl innerhalb des Int32Tests und innerhalb des Int64Tests die Datensätze beim Testen der verschiedenen Berechnungsmethoden nicht geändert werden. In Bezug auf .NET Core bezweifle ich, dass es eine magische Optimierung in der Mathematikbibliothek gibt, die diese Ergebnisse ändern würde, aber ich würde gerne mehr darüber hören (meine Antwort ist bereits riesig, wahrscheinlich eine der größten in SO ;-)
sɐunıɔ ןɐ qɐp
@ GyörgyKőszeg: Auch Low-Level-Leistungsmessungen sind sehr schwierig. Ich bevorzuge es in der Regel den Code so einfach wie möglich zu halten (ich ziehe einfach forSchleifen über enumerations, ich vorverarbeiten zufällige Datensätze, und vermeiden den Einsatz von Generika, Aufgaben Function<>, Action<>oder jede schwarz-Box - Messrahmen). Zusammenfassend halten Sie es einfach. Ich töte auch alle unnötigen Anwendungen (Skype, Windows Defender, Deaktivieren von Anti-Virus, Chrome, Microsoft Office-Cache usw.).
sɐunıɔ ןɐ qɐp
13
Nicht direkt C #, aber die Formel lautet: n = floor(log10(x)+1)
@Klaus - log10 (0) ist eigentlich undefiniert. Sie haben jedoch Recht, da es sich um einen Sonderfall handelt, der separat getestet und behandelt werden muss. Dies gilt auch für nicht positive Ganzzahlen. Siehe Kommentare zu Steves Antwort.
Ysap
@ysap: Log10 ist ziemlich schwierig, um richtig zu arbeiten. Haben Sie eine Idee, wie Sie es für alle möglichen Eingabewerte korrekt implementieren können?
sɐunıɔ ןɐ qɐp
@ sɐunıɔ ןɐ qɐp - log10ist in den meisten Fällen eine Bibliotheksfunktion. Warum sollten Sie es selbst implementieren und auf welche Probleme stoßen Sie? log10(x) = log2(x) / log2(10)oder allgemein logA(x) = logB(x) / logB(A).
Ysap
Ich wollte Log10 nicht erneut implementieren, ich meine Log10(0)-infinity. Log10 kann nicht zur Berechnung der Anzahl der Ziffern negativer Zahlen verwendet werden, es sei denn, Sie verwenden diese, Math.Abs()bevor Sie den Wert an Log10 übergeben. Aber dann wird Math.Abs(int.MinValue)eine Ausnahme long.MinValueausgelöst ( auch im Fall von Int64). Wenn wir die Zahl verdoppeln, bevor wir sie an Log10 übergeben, funktioniert sie für fast alle Zahlen außer -999999999999999999(im Fall von Int64). Kennen Sie eine Formel zur Berechnung der Anzahl der Ziffern, die log10 verwendet und einen int32- oder int64-Wert als Eingabe akzeptiert und nur gültige Werte ausgibt?
sɐunıɔ ןɐ qɐp
8
Die Antworten hier funktionieren bereits für vorzeichenlose Ganzzahlen, aber ich habe keine guten Lösungen gefunden, um die Anzahl der Stellen von Dezimalstellen und Doppelten zu erhalten.
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
Sie können den Eingabetyp von doubleauf ändern , decimalwenn die Genauigkeit wichtig ist, aber auch die Dezimalzahl hat eine Grenze.
Hier ist eine Implementierung mit einer binären Suche. Scheint auf int32 der bisher schnellste zu sein.
Die Int64-Implementierung bleibt als Übung für den Leser (!)
Ich habe versucht, Array.BinarySearch zu verwenden, anstatt den Baum fest zu codieren, aber das war ungefähr die Hälfte der Geschwindigkeit.
BEARBEITEN: Eine Nachschlagetabelle ist viel schneller als die binäre Suche, auf Kosten der Verwendung von mehr Speicher. Realistisch gesehen würde ich wahrscheinlich die binäre Suche in der Produktion verwenden. Die Nachschlagetabelle ist sehr komplex für einen Geschwindigkeitsgewinn, der wahrscheinlich von anderen Teilen der Software überschattet wird.
Lookup-Table:439 ms
Binary-Search:1069 ms
If-Chain:1409 ms
Log10:1145 ms
While:1768 ms
String:5153 ms
Nachschlagetabellenversion:
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];}
Sehr interessanter Ansatz. Es ist in der Tat schneller als die Methoden "Log10", "string.Length" und "While" für gleichmäßig verteilte ganzzahlige Werte. In realen Fällen muss die Verteilung der ganzzahligen Werte bei if-chain-ähnlichen Lösungen immer berücksichtigt werden. +1
sɐunıɔ ןɐ qɐp
Der LookUpTable-Ansatz scheint in Szenarien, in denen der Speicherzugriff nicht der Engpass ist, sehr schnell zu sein. Ich bin der festen Überzeugung, dass in Szenarien mit häufigem Speicherzugriff die LookUpTable langsamer wird als wenn-kettenähnliche Methoden, wie die von Ihnen vorgeschlagene BinSearch-Methode. Haben Sie übrigens die Int64Implementierung für die LookUpTable? Oder halten Sie es für zu kompliziert, es umzusetzen? Ich möchte die Leistungstests später für den gesamten Satz ausführen.
sɐunıɔ ןɐ qɐp
Hey, bin nicht so weit gekommen wie das 64-Bit. Das Prinzip müsste etwas anders sein, da Sie 4x Levels benötigen würden und nicht nur Hiword und Loword. Stimmen Sie auf jeden Fall zu, dass Ihr CPU-Cache in der realen Welt viele andere konkurrierende Anforderungen an den Speicherplatz hat und es viel Raum für Verbesserungen gibt, wenn Sie die Größe der Suche reduzieren (>> 1, dann kommen nur gerade Zahlen in den Sinn). . Die binäre Suche könnte verbessert werden, indem Sie auf 9,10,8 Stellen anstatt auf 1,2,3,4 vorrücken - angesichts der Verteilung Ihres zufälligen Datensatzes.
Alan Singfield
1
Wenn Sie eine Zahl durch 10 teilen, erhalten Sie die am weitesten links stehende Ziffer. Wenn Sie dann eine Mod 10 für die Zahl ausführen, erhalten Sie die Zahl ohne die erste Ziffer. Wiederholen Sie dies, bis Sie alle Ziffern haben
Dies schien mir die intuitivere Herangehensweise an dieses Problem zu sein. Ich habe es versuchtLog10 Methode zuerst wegen ihrer scheinbaren Einfachheit , aber sie hat eine wahnsinnige Menge an Eckfällen und Präzisionsproblemen.
Ich habe auch die gefunden if in der anderen Antwort vorgeschlagene Kette etwas hässlich anzusehen.
Ich weiß, dass dies nicht die effizienteste Methode ist, aber es gibt Ihnen die andere Erweiterung, um die Ziffern auch für andere privateZwecke zurückzugeben (Sie können sie nur markieren, wenn Sie sie nicht außerhalb der Klasse verwenden müssen).
Beachten Sie, dass das negative Vorzeichen nicht als Ziffer betrachtet wird.
Antworten:
Ohne in eine Zeichenfolge zu konvertieren, können Sie Folgendes versuchen:
Korrektur nach dem Kommentar von ysap:
quelle
n
heißt0
kann nur zurückkehren1
:) Too Griff negative Werte ersetzen Sie einfachn
mitMath.Abs(n)
.Versuche dies:
Funktioniert es ?
quelle
int
, also nehme ich an, dass das kein Problem ist.)Die Lösung
Jede der folgenden Erweiterungsmethoden erledigt den Job. Alle betrachten das Minuszeichen als Ziffer und funktionieren für alle möglichen Eingabewerte korrekt. Sie funktionieren auch für .NET Framework und .NET Core. Abhängig von Ihrer Wahl der Plattform / des Frameworks gibt es jedoch relevante Leistungsunterschiede (siehe unten).
Int32-Version:
Int64-Version:
Diskussion
Diese Antwort enthält Tests, die für beide
Int32
undInt64
Typen unter Verwendung eines Arrays von100.000.000
zufällig ausgewähltenint
/long
Zahlen durchgeführt wurden. Der zufällige Datensatz wird vor dem Ausführen der Tests in ein Array vorverarbeitet.Konsistenzprüfungen unter den 4 verschiedenen Methoden wurden auch durchgeführt, für die
MinValue
negativen Grenzfall-1
,0
,1
, positive Grenzfälle,MaxValue
und auch für den ganzen Zufallsdatensatz. Für die oben angegebenen Methoden schlagen keine Konsistenztests fehl, AUSSER für die LOG10-Methode (dies wird später erläutert).Die Tests wurden am
.NET Framework 4.7.2
und durchgeführt.NET Core 2.2
; fürx86
undx64
Plattformen auf einem 64-Bit-Intel-Prozessor mitWindows 10
und mitVS2017 v.15.9.17
. Die folgenden 4 Fälle haben den gleichen Effekt auf die Leistungsergebnisse:.NET Framework (x86)
Platform = x86
Platform = AnyCPU
,Prefer 32-bit
Wird in den Projekteinstellungen überprüft.NET Framework (x64)
Platform = x64
Platform = AnyCPU
,Prefer 32-bit
Ist in Projekteinstellungen nicht aktiviert.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
Ergebnisse
Die folgenden Leistungstests ergeben eine gleichmäßige Verteilung der Werte auf den weiten Wertebereich, den eine Ganzzahl annehmen könnte. Dies bedeutet, dass die Wahrscheinlichkeit, Werte mit einer großen Anzahl von Ziffern zu testen, viel höher ist. In realen Szenarien können die meisten Werte klein sein, daher sollte die IF-CHAIN eine noch bessere Leistung erbringen. Darüber hinaus speichert der Prozessor die IF-CHAIN-Entscheidungen entsprechend Ihrem Datensatz zwischen und optimiert sie.
Wie @AlanSingfield im Kommentarbereich hervorhob, musste die LOG10-Methode für den Fall, dass der Eingabewert oder ist, mit einem Casting nach
double
innen korrigiert werdenMath.Abs()
int.MinValue
long.MinValue
.In Bezug auf die frühen Leistungstests, die ich vor der Bearbeitung dieser Frage implementiert habe (sie musste bereits millionenfach bearbeitet werden), gab es einen speziellen Fall, auf den @ GyörgyKőszeg hingewiesen hat , bei dem die IF-CHAIN-Methode langsamer als die LOG10-Methode ist.
Dies geschieht immer noch, obwohl die Größe des Unterschieds nach der Behebung des von @AlanSingfield hervorgehobenen Problems viel geringer wurde . Dieser Fix (Hinzufügen einer Umwandlung zu
double
) verursacht einen Berechnungsfehler, wenn der Eingabewert genau ist-999999999999999999
: Die LOG10-Methode gibt20
statt zurück19
. Die LOG10-Methode muss auch einenif
Schutz für den Fall haben, dass der Eingabewert Null ist.Die LOG10-Methode ist ziemlich schwierig, um für alle Werte zu arbeiten, was bedeutet, dass Sie sie vermeiden sollten. Wenn jemand einen Weg findet, es für alle unten aufgeführten Konsistenztests richtig funktionieren zu lassen, schreibe bitte einen Kommentar!
Die WHILE-Methode hat auch eine kürzlich überarbeitete Version erhalten, die schneller ist, aber immer noch langsam ist
Platform = x86
(ich konnte bis jetzt keinen Grund dafür finden).Die STRING-Methode ist durchweg langsam: Sie weist gierig zu viel Speicher für nichts zu. Interessanterweise scheint die Zuweisung von Zeichenfolgen in .NET Core viel schneller zu sein als in .NET Framework. Gut zu wissen.
Die IF-CHAIN-Methode sollte in 99,99% der Fälle alle anderen Methoden übertreffen. und meiner persönlichen Meinung nach ist dies Ihre beste Wahl (unter Berücksichtigung aller Anpassungen, die erforderlich sind, damit die LOG10-Methode ordnungsgemäß funktioniert, und der schlechten Leistung der beiden anderen Methoden).
Schließlich sind die Ergebnisse:
Da diese Ergebnisse hardwareabhängig sind, empfehle ich trotzdem, die folgenden Leistungstests auf Ihrem eigenen Computer durchzuführen, wenn Sie in Ihrem speziellen Fall wirklich 100% sicher sein müssen.
Testcode
Unten finden Sie den Code für den Leistungstest und den Konsistenztest. Für .NET Framework und .NET Core wird derselbe Code verwendet.
quelle
long.MaxValue
Log10 jedoch deutlich besser. Oder ist es nur in .NET Core?Int32
undInt64
unterschiedliche Datensätze generieren, was erklären kann, warumInt64
schneller alsInt32
in einigen Fällen. Obwohl innerhalb desInt32
Tests und innerhalb desInt64
Tests die Datensätze beim Testen der verschiedenen Berechnungsmethoden nicht geändert werden. In Bezug auf .NET Core bezweifle ich, dass es eine magische Optimierung in der Mathematikbibliothek gibt, die diese Ergebnisse ändern würde, aber ich würde gerne mehr darüber hören (meine Antwort ist bereits riesig, wahrscheinlich eine der größten in SO ;-)for
Schleifen überenumerations
, ich vorverarbeiten zufällige Datensätze, und vermeiden den Einsatz von Generika, AufgabenFunction<>
,Action<>
oder jede schwarz-Box - Messrahmen). Zusammenfassend halten Sie es einfach. Ich töte auch alle unnötigen Anwendungen (Skype, Windows Defender, Deaktivieren von Anti-Virus, Chrome, Microsoft Office-Cache usw.).Nicht direkt C #, aber die Formel lautet:
n = floor(log10(x)+1)
quelle
log10
ist in den meisten Fällen eine Bibliotheksfunktion. Warum sollten Sie es selbst implementieren und auf welche Probleme stoßen Sie?log10(x) = log2(x) / log2(10)
oder allgemeinlogA(x) = logB(x) / logB(A)
.Log10(0)
-infinity. Log10 kann nicht zur Berechnung der Anzahl der Ziffern negativer Zahlen verwendet werden, es sei denn, Sie verwenden diese,Math.Abs()
bevor Sie den Wert an Log10 übergeben. Aber dann wirdMath.Abs(int.MinValue)
eine Ausnahmelong.MinValue
ausgelöst ( auch im Fall von Int64). Wenn wir die Zahl verdoppeln, bevor wir sie an Log10 übergeben, funktioniert sie für fast alle Zahlen außer-999999999999999999
(im Fall von Int64). Kennen Sie eine Formel zur Berechnung der Anzahl der Ziffern, die log10 verwendet und einen int32- oder int64-Wert als Eingabe akzeptiert und nur gültige Werte ausgibt?Die Antworten hier funktionieren bereits für vorzeichenlose Ganzzahlen, aber ich habe keine guten Lösungen gefunden, um die Anzahl der Stellen von Dezimalstellen und Doppelten zu erhalten.
Sie können den Eingabetyp von
double
auf ändern ,decimal
wenn die Genauigkeit wichtig ist, aber auch die Dezimalzahl hat eine Grenze.quelle
Die Antwort von Steve ist richtig , funktioniert aber nicht für ganze Zahlen unter 1.
Hier eine aktualisierte Version, die für Negative funktioniert:
quelle
digits = n == 0 ? 1 : (int)Math.Floor(Math.Log10(Math.Abs(n)) + 1);
n = int.MinValue
.Rekursion verwenden (manchmal in Interviews gefragt)
quelle
number = int.MinValue
.quelle
-1
= 2Hier ist eine Implementierung mit einer binären Suche. Scheint auf int32 der bisher schnellste zu sein.
Die Int64-Implementierung bleibt als Übung für den Leser (!)
Ich habe versucht, Array.BinarySearch zu verwenden, anstatt den Baum fest zu codieren, aber das war ungefähr die Hälfte der Geschwindigkeit.
BEARBEITEN: Eine Nachschlagetabelle ist viel schneller als die binäre Suche, auf Kosten der Verwendung von mehr Speicher. Realistisch gesehen würde ich wahrscheinlich die binäre Suche in der Produktion verwenden. Die Nachschlagetabelle ist sehr komplex für einen Geschwindigkeitsgewinn, der wahrscheinlich von anderen Teilen der Software überschattet wird.
Nachschlagetabellenversion:
Binäre Suchversion
quelle
Int64
Implementierung für die LookUpTable? Oder halten Sie es für zu kompliziert, es umzusetzen? Ich möchte die Leistungstests später für den gesamten Satz ausführen.Wenn Sie eine Zahl durch 10 teilen, erhalten Sie die am weitesten links stehende Ziffer. Wenn Sie dann eine Mod 10 für die Zahl ausführen, erhalten Sie die Zahl ohne die erste Ziffer. Wiederholen Sie dies, bis Sie alle Ziffern haben
quelle
quelle
string.TrimStart('-')
besserErstellen Sie eine Methode, die alle Ziffern zurückgibt, und eine andere, die sie zählt:
Dies schien mir die intuitivere Herangehensweise an dieses Problem zu sein. Ich habe es versucht
Log10
Methode zuerst wegen ihrer scheinbaren Einfachheit , aber sie hat eine wahnsinnige Menge an Eckfällen und Präzisionsproblemen.Ich habe auch die gefunden
if
in der anderen Antwort vorgeschlagene Kette etwas hässlich anzusehen.Ich weiß, dass dies nicht die effizienteste Methode ist, aber es gibt Ihnen die andere Erweiterung, um die Ziffern auch für andere
private
Zwecke zurückzugeben (Sie können sie nur markieren, wenn Sie sie nicht außerhalb der Klasse verwenden müssen).Beachten Sie, dass das negative Vorzeichen nicht als Ziffer betrachtet wird.
quelle
In eine Zeichenfolge konvertieren und dann können Sie die Gesamtzahl der Ziffern nach der Methode .length zählen. Mögen:
quelle
Es kommt darauf an, was genau Sie mit den Ziffern machen wollen. Sie können die Ziffern vom letzten bis zum ersten wie folgt durchlaufen:
quelle
%
, um die Ziffer zu erhalten und sie dann/=
zu kürzen.Wenn es nur zur Validierung ist, könnten Sie Folgendes tun:
887979789 > 99999999
quelle
Angenommen, Ihre Frage bezieht sich auf ein int, funktioniert das Folgende auch für negativ / positiv und null:
quelle