J'ai peur ceil (log10 (10)) = ceil (1) = 1, et non 2 comme il se doit pour cette question!
ysap
3
Merci, c'est une bonne méthode. Bien que ce ne soit pas plus rapide que int count = 0; do {count ++; } tandis que ((i / = 10)> = 1); :(
Puterdo Borato
3
Si votre plage de nombres comprend des négatifs, vous devrez utiliser Math.Floor (Math.Log10 (Math.Abs (n)) + 1);
mrcrowl
1
Eh bien, si nc'est 0peut simplement retourner 1:) Trop gérer les valeurs négatives, il suffit de les remplacer npar Math.Abs(n).
Umair
3
@Puterdo Borato: mon test de performance a en fait montré que votre méthode est plus rapide lorsque le nombre de chiffres est <5. Passez ça, Steve's Math.floor est plus rapide.
Il convient de noter que vous rencontrerez probablement des problèmes avec cette méthode si vous avez affaire à des nombres négatifs. (Et évidemment des décimales, mais l'exemple utilise un int, donc je suppose que ce n'est pas un problème.)
Cody Gray
2
L'allocation de chaînes @Krythic est le nouvel engouement dans le monde .NET.
nawfal
1
Nouveau? À peine. J'allouais de manière flagrante des chaînes en 2010. Quel créateur de tendance. Lol. Vous avez raison cependant. C'est sale!
Andiih
3
@Krythic Ce n'est pas les années 1980, votre ordinateur dispose de suffisamment de RAM pour enregistrer une chaîne de 10 caractères en mémoire pour la durée d'une opération.
MrLore
2
@MrLore Dans les applications simples, cela peut être vrai, mais dans le monde du développement de jeux, c'est une bête complètement différente.
Krythic
48
La solution
L'une des méthodes d'extension suivantes fera l'affaire. Tous considèrent le signe moins comme un chiffre et fonctionnent correctement pour toutes les valeurs d'entrée possibles. Ils fonctionnent également pour .NET Framework et pour .NET Core. Il existe cependant des différences de performances pertinentes (décrites ci-dessous), en fonction de votre choix de plate-forme / cadre.
Cette réponse comprend des tests effectués pour les deux types Int32et Int64, en utilisant un tableau de nombres / 100.000.000échantillonnés au hasard . L'ensemble de données aléatoires est prétraité dans un tableau avant d'exécuter les tests.intlong
Des tests de cohérence entre les 4 méthodes différentes ont également été exécutées, pour MinValue, cas de frontières négatives, -1, 0, 1, cas de frontière positifs, MaxValueet aussi pour l'ensemble jeu de données aléatoire. Aucun test de cohérence n'échoue pour les méthodes fournies ci-dessus, SAUF pour la méthode LOG10 (cela sera discuté plus tard).
Les tests ont été exécutés sur .NET Framework 4.7.2et .NET Core 2.2; pour x86et x64plates - formes, sur une machine à processeur Intel 64 bits, avec Windows 10et avec VS2017 v.15.9.17. Les 4 cas suivants ont le même effet sur les résultats de performance:
.NET Framework (x86)
Platform = x86
Platform = AnyCPU, Prefer 32-bitest cochée dans les paramètres du projet
.NET Framework (x64)
Platform = x64
Platform = AnyCPU, Prefer 32-bitn'est pas cochée dans les paramètres du projet
Les tests de performance ci-dessous produisent une distribution uniforme des valeurs parmi la large gamme de valeurs qu'un entier peut prendre. Cela signifie qu'il y a une chance beaucoup plus élevée de tester des valeurs avec un grand nombre de chiffres. Dans les scénarios réels, la plupart des valeurs peuvent être petites, donc l'IF-CHAIN devrait fonctionner encore mieux. De plus, le processeur mettra en cache et optimisera les décisions IF-CHAIN en fonction de votre ensemble de données.
Comme @AlanSingfield l'a souligné dans la section commentaire, la méthode LOG10 a dû être corrigée avec un casting vers l' doubleintérieur Math.Abs()pour le cas où la valeur d'entrée est int.MinValueou long.MinValue.
En ce qui concerne les premiers tests de performances que j'ai mis en œuvre avant de modifier cette question (elle devait déjà être modifiée un million de fois), il y avait un cas spécifique signalé par @ GyörgyKőszeg , dans lequel la méthode IF-CHAIN fonctionne plus lentement que la méthode LOG10.
Cela se produit toujours, bien que l'ampleur de la différence soit devenue beaucoup plus faible après le correctif du problème signalé par @AlanSingfield . Ce correctif (ajouter un cast à double) provoque une erreur de calcul lorsque la valeur d'entrée est exactement -999999999999999999: la méthode LOG10 renvoie à la 20place de 19. La méthode LOG10 doit également avoir une ifgarde pour le cas où la valeur d'entrée est zéro.
La méthode LOG10 est assez délicate à utiliser pour toutes les valeurs, ce qui signifie que vous devez l'éviter. Si quelqu'un trouve un moyen de le faire fonctionner correctement pour tous les tests de cohérence ci-dessous, veuillez poster un commentaire!
La méthode WHILE a également obtenu une version refactorisée récente qui est plus rapide, mais elle est encore lente Platform = x86(je n'ai pas pu trouver la raison pour laquelle, jusqu'à présent).
La méthode STRING est toujours lente: elle alloue avec gourmandise trop de mémoire pour rien. Fait intéressant, dans .NET Core, l'allocation de chaînes semble être beaucoup plus rapide que dans .NET Framework. Bon à savoir.
La méthode IF-CHAIN devrait surpasser toutes les autres méthodes dans 99,99% des cas; et, à mon avis personnel, est votre meilleur choix (compte tenu de tous les ajustements nécessaires pour que la méthode LOG10 fonctionne correctement, et des mauvaises performances des deux autres méthodes).
Enfin, les résultats sont:
Étant donné que ces résultats dépendent du matériel, je recommande quand même d'exécuter les tests de performances ci-dessous sur votre propre ordinateur si vous avez vraiment besoin d'être sûr à 100% dans votre cas spécifique.
Code de test
Vous trouverez ci-dessous le code du test de performance, ainsi que le test de cohérence. Le même code est utilisé pour .NET Framework et .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");}}}
J'aime cette solution, elle est beaucoup plus lisible que les astuces mathématiques et la vitesse parle d'elle-même, bravo.
MrLore
3
Pourquoi n'est-ce pas indiqué comme la solution? La performance compte et cela semble être la réponse la plus complète.
Martien de Jong
Intéressant, j'obtiens des résultats différents . Pour les valeurs aléatoires, Log10 et force brute sont presque les mêmes, mais pour long.MaxValueLog10, c'est nettement mieux. Ou est-ce juste dans .NET Core?
György Kőszeg
@ GyörgyKőszeg: J'ai ajouté des tests pour Int64. Veuillez noter que les tests Int32et Int64génèrent différents ensembles de données, ce qui peut expliquer pourquoi ils Int64sont devenus plus rapides que Int32dans certains cas. Cependant, dans le Int32test et dans le Int64test, les ensembles de données ne sont pas modifiés lors du test des différentes méthodes de calcul. Maintenant en ce qui concerne .NET Core, je doute qu'il y ait une optimisation magique dans la bibliothèque Math qui changerait ces résultats, mais j'aimerais en savoir plus à ce sujet (ma réponse est déjà énorme, probablement l'une des plus importantes de SO ;-)
sɐunıɔ ןɐ qɐp
@ GyörgyKőszeg: De plus, les mesures de performance de bas niveau sont très délicates. Je préfère généralement garder le code aussi simple que possible (je préfère de simples forboucles sur enumerations, I ensembles de données aléatoires pré-processus, et éviter l'utilisation des médicaments génériques, les tâches Function<>, Action<>ou tout cadre de mesure noir boxed). En résumé, restez simple. Je tue également toutes les applications inutiles (Skype, Windows Defender, désactiver l'antivirus, Chrome, le cache Microsoft Office, etc.).
sɐunıɔ ןɐ qɐp
13
Pas directement C #, mais la formule est: n = floor(log10(x)+1)
@Klaus - log10 (0) n'est en fait pas défini. Mais vous avez raison dans la mesure où il s'agit d'un cas particulier qui doit être testé et traité séparément. Ceci est également vrai pour tout nombre entier non positif. Voir les commentaires sur la réponse de Steve.
ysap
@ysap: Log10 est assez difficile à faire fonctionner correctement. Avez-vous une idée sur la façon de l'implémenter correctement pour toutes les plages de valeurs d'entrée possibles?
sɐunıɔ ןɐ qɐp
@ sɐunıɔ ןɐ qɐp - log10est dans la plupart des cas une fonction de bibliothèque. Pourquoi voudriez-vous le mettre en œuvre vous-même et quels problèmes rencontrez-vous? log10(x) = log2(x) / log2(10), ou généralement logA(x) = logB(x) / logB(A).
ysap
Je ne voulais pas implémenter à nouveau Log10, je veux dire Log10(0)est -infinity. Log10 ne peut pas être utilisé pour calculer le nombre de chiffres de nombres négatifs à moins que vous Math.Abs()ne l'utilisiez avant de passer la valeur à Log10. Mais Math.Abs(int.MinValue)lance ensuite une exception ( long.MinValueaussi, dans le cas d'Int64). Si nous convertissons le nombre en double avant de le passer à Log10, cela fonctionne pour presque tous les nombres sauf pour -999999999999999999(dans le cas de Int64). Connaissez-vous une formule pour calculer le nombre de chiffres qui utilise log10 et accepte toute valeur int32 ou int64 comme entrée et ne produit que des valeurs valides?
sɐunıɔ ןɐ qɐp
9
Les réponses déjà ici fonctionnent pour les entiers non signés, mais je n'ai pas trouvé de bonnes solutions pour obtenir le nombre de chiffres à partir des décimales et des doubles.
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
Vous pouvez changer le type d'entrée de doubleà decimalsi la précision est importante, mais décimal a également une limite.
Voici une implémentation utilisant une recherche binaire. Semble être le plus rapide à ce jour sur int32.
L'implémentation Int64 est laissée comme un exercice pour le lecteur (!)
J'ai essayé d'utiliser Array.BinarySearch plutôt que de coder en dur l'arbre, mais c'était environ la moitié de la vitesse.
EDIT: Une table de recherche est beaucoup plus rapide que la recherche binaire, au détriment de l'utilisation de plus de mémoire. En réalité, j'utiliserais probablement la recherche binaire en production, la table de recherche est beaucoup plus complexe pour un gain de vitesse susceptible d'être éclipsé par d'autres parties du logiciel.
Lookup-Table:439 ms
Binary-Search:1069 ms
If-Chain:1409 ms
Log10:1145 ms
While:1768 ms
String:5153 ms
Version de la table de recherche:
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];}
Approche très intéressante. C'est en effet plus rapide que les méthodes "Log10", "string.Length" et "While" pour des valeurs entières uniformément distribuées. Dans les scénarios de cas réels, la distribution des valeurs entières doit toujours être prise en compte sur des solutions de type if-chain. +1
sɐunıɔ ןɐ qɐp
L'approche LookUpTable semble être très rapide pour les scénarios où l'accès à la mémoire n'est pas le goulot d'étranglement. Je crois fermement que pour les scénarios avec un accès mémoire fréquent, le LookUpTable devient plus lent que les méthodes de type if-chain, comme celle de BinSearch que vous avez suggérée. Au fait, avez-vous l' Int64implémentation de LookUpTable? Ou pensez-vous que c'est trop compliqué à mettre en œuvre? J'aimerais exécuter les tests de performances plus tard sur l'ensemble complet.
sɐunıɔ ןɐ qɐp
Hé, je ne suis pas allé aussi loin que le 64 bits. Le principe devrait être légèrement différent en ce sens que vous auriez besoin de 4x niveaux plutôt que de simplement hiword et loword. Tout à fait d'accord que dans le monde réel, le cache de votre processeur aura beaucoup d'autres besoins concurrents pour l'espace, et il y a beaucoup de place à l'amélioration pour réduire la taille de la recherche (>> 1 alors les nombres pairs ne viennent à l'esprit) . La recherche binaire pourrait être améliorée en biaisant vers 9,10,8 chiffres au lieu de 1,2,3,4 - étant donné la distribution de votre ensemble de données aléatoires.
Alan Singfield
1
diviser un nombre par 10 vous donnera le chiffre le plus à gauche puis faire un mod 10 sur le nombre donne le nombre sans le premier chiffre et répétez cela jusqu'à ce que vous ayez tous les chiffres
Cela me semblait être l'approche la plus intuitive pour aborder ce problème. J'ai d'abord essayé la Log10méthode en raison de son apparente simplicité, mais elle présente une quantité insensée de boîtiers d'angle et de problèmes de précision.
J'ai aussi trouvé le if chaîne proposée dans l'autre réponse un peu moche à regarder.
Je sais que ce n'est pas la méthode la plus efficace, mais elle vous donne l'autre extension pour renvoyer les chiffres également pour d'autres utilisations (vous pouvez simplement la marquer privatesi vous n'avez pas besoin de l'utiliser en dehors de la classe).
Gardez à l'esprit qu'il ne considère pas le signe négatif comme un chiffre.
Réponses:
Sans convertir en une chaîne, vous pouvez essayer:
Correction suite au commentaire d'Ysap:
la source
n
c'est0
peut simplement retourner1
:) Trop gérer les valeurs négatives, il suffit de les remplacern
parMath.Abs(n)
.Essaye ça:
Ça marche?
la source
int
, donc je suppose que ce n'est pas un problème.)La solution
L'une des méthodes d'extension suivantes fera l'affaire. Tous considèrent le signe moins comme un chiffre et fonctionnent correctement pour toutes les valeurs d'entrée possibles. Ils fonctionnent également pour .NET Framework et pour .NET Core. Il existe cependant des différences de performances pertinentes (décrites ci-dessous), en fonction de votre choix de plate-forme / cadre.
Version Int32:
Version Int64:
Discussion
Cette réponse comprend des tests effectués pour les deux types
Int32
etInt64
, en utilisant un tableau de nombres /100.000.000
échantillonnés au hasard . L'ensemble de données aléatoires est prétraité dans un tableau avant d'exécuter les tests.int
long
Des tests de cohérence entre les 4 méthodes différentes ont également été exécutées, pour
MinValue
, cas de frontières négatives,-1
,0
,1
, cas de frontière positifs,MaxValue
et aussi pour l'ensemble jeu de données aléatoire. Aucun test de cohérence n'échoue pour les méthodes fournies ci-dessus, SAUF pour la méthode LOG10 (cela sera discuté plus tard).Les tests ont été exécutés sur
.NET Framework 4.7.2
et.NET Core 2.2
; pourx86
etx64
plates - formes, sur une machine à processeur Intel 64 bits, avecWindows 10
et avecVS2017 v.15.9.17
. Les 4 cas suivants ont le même effet sur les résultats de performance:.NET Framework (x86)
Platform = x86
Platform = AnyCPU
,Prefer 32-bit
est cochée dans les paramètres du projet.NET Framework (x64)
Platform = x64
Platform = AnyCPU
,Prefer 32-bit
n'est pas cochée dans les paramètres du projet.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
Résultats
Les tests de performance ci-dessous produisent une distribution uniforme des valeurs parmi la large gamme de valeurs qu'un entier peut prendre. Cela signifie qu'il y a une chance beaucoup plus élevée de tester des valeurs avec un grand nombre de chiffres. Dans les scénarios réels, la plupart des valeurs peuvent être petites, donc l'IF-CHAIN devrait fonctionner encore mieux. De plus, le processeur mettra en cache et optimisera les décisions IF-CHAIN en fonction de votre ensemble de données.
Comme @AlanSingfield l'a souligné dans la section commentaire, la méthode LOG10 a dû être corrigée avec un casting vers l'
double
intérieurMath.Abs()
pour le cas où la valeur d'entrée estint.MinValue
oulong.MinValue
.En ce qui concerne les premiers tests de performances que j'ai mis en œuvre avant de modifier cette question (elle devait déjà être modifiée un million de fois), il y avait un cas spécifique signalé par @ GyörgyKőszeg , dans lequel la méthode IF-CHAIN fonctionne plus lentement que la méthode LOG10.
Cela se produit toujours, bien que l'ampleur de la différence soit devenue beaucoup plus faible après le correctif du problème signalé par @AlanSingfield . Ce correctif (ajouter un cast à
double
) provoque une erreur de calcul lorsque la valeur d'entrée est exactement-999999999999999999
: la méthode LOG10 renvoie à la20
place de19
. La méthode LOG10 doit également avoir uneif
garde pour le cas où la valeur d'entrée est zéro.La méthode LOG10 est assez délicate à utiliser pour toutes les valeurs, ce qui signifie que vous devez l'éviter. Si quelqu'un trouve un moyen de le faire fonctionner correctement pour tous les tests de cohérence ci-dessous, veuillez poster un commentaire!
La méthode WHILE a également obtenu une version refactorisée récente qui est plus rapide, mais elle est encore lente
Platform = x86
(je n'ai pas pu trouver la raison pour laquelle, jusqu'à présent).La méthode STRING est toujours lente: elle alloue avec gourmandise trop de mémoire pour rien. Fait intéressant, dans .NET Core, l'allocation de chaînes semble être beaucoup plus rapide que dans .NET Framework. Bon à savoir.
La méthode IF-CHAIN devrait surpasser toutes les autres méthodes dans 99,99% des cas; et, à mon avis personnel, est votre meilleur choix (compte tenu de tous les ajustements nécessaires pour que la méthode LOG10 fonctionne correctement, et des mauvaises performances des deux autres méthodes).
Enfin, les résultats sont:
Étant donné que ces résultats dépendent du matériel, je recommande quand même d'exécuter les tests de performances ci-dessous sur votre propre ordinateur si vous avez vraiment besoin d'être sûr à 100% dans votre cas spécifique.
Code de test
Vous trouverez ci-dessous le code du test de performance, ainsi que le test de cohérence. Le même code est utilisé pour .NET Framework et .NET Core.
la source
long.MaxValue
Log10, c'est nettement mieux. Ou est-ce juste dans .NET Core?Int32
etInt64
génèrent différents ensembles de données, ce qui peut expliquer pourquoi ilsInt64
sont devenus plus rapides queInt32
dans certains cas. Cependant, dans leInt32
test et dans leInt64
test, les ensembles de données ne sont pas modifiés lors du test des différentes méthodes de calcul. Maintenant en ce qui concerne .NET Core, je doute qu'il y ait une optimisation magique dans la bibliothèque Math qui changerait ces résultats, mais j'aimerais en savoir plus à ce sujet (ma réponse est déjà énorme, probablement l'une des plus importantes de SO ;-)for
boucles surenumerations
, I ensembles de données aléatoires pré-processus, et éviter l'utilisation des médicaments génériques, les tâchesFunction<>
,Action<>
ou tout cadre de mesure noir boxed). En résumé, restez simple. Je tue également toutes les applications inutiles (Skype, Windows Defender, désactiver l'antivirus, Chrome, le cache Microsoft Office, etc.).Pas directement C #, mais la formule est:
n = floor(log10(x)+1)
la source
log10
est dans la plupart des cas une fonction de bibliothèque. Pourquoi voudriez-vous le mettre en œuvre vous-même et quels problèmes rencontrez-vous?log10(x) = log2(x) / log2(10)
, ou généralementlogA(x) = logB(x) / logB(A)
.Log10(0)
est -infinity. Log10 ne peut pas être utilisé pour calculer le nombre de chiffres de nombres négatifs à moins que vousMath.Abs()
ne l'utilisiez avant de passer la valeur à Log10. MaisMath.Abs(int.MinValue)
lance ensuite une exception (long.MinValue
aussi, dans le cas d'Int64). Si nous convertissons le nombre en double avant de le passer à Log10, cela fonctionne pour presque tous les nombres sauf pour-999999999999999999
(dans le cas de Int64). Connaissez-vous une formule pour calculer le nombre de chiffres qui utilise log10 et accepte toute valeur int32 ou int64 comme entrée et ne produit que des valeurs valides?Les réponses déjà ici fonctionnent pour les entiers non signés, mais je n'ai pas trouvé de bonnes solutions pour obtenir le nombre de chiffres à partir des décimales et des doubles.
Vous pouvez changer le type d'entrée de
double
àdecimal
si la précision est importante, mais décimal a également une limite.la source
La réponse de Steve est correcte , mais cela ne fonctionne pas pour les entiers inférieurs à 1.
Voici une version mise à jour qui fonctionne pour les négatifs:
la source
digits = n == 0 ? 1 : (int)Math.Floor(Math.Log10(Math.Abs(n)) + 1);
n = int.MinValue
.Utilisation de la récursivité (parfois posée lors des entretiens)
la source
number = int.MinValue
.la source
-1
= 2Voici une implémentation utilisant une recherche binaire. Semble être le plus rapide à ce jour sur int32.
L'implémentation Int64 est laissée comme un exercice pour le lecteur (!)
J'ai essayé d'utiliser Array.BinarySearch plutôt que de coder en dur l'arbre, mais c'était environ la moitié de la vitesse.
EDIT: Une table de recherche est beaucoup plus rapide que la recherche binaire, au détriment de l'utilisation de plus de mémoire. En réalité, j'utiliserais probablement la recherche binaire en production, la table de recherche est beaucoup plus complexe pour un gain de vitesse susceptible d'être éclipsé par d'autres parties du logiciel.
Version de la table de recherche:
Version de recherche binaire
la source
Int64
implémentation de LookUpTable? Ou pensez-vous que c'est trop compliqué à mettre en œuvre? J'aimerais exécuter les tests de performances plus tard sur l'ensemble complet.diviser un nombre par 10 vous donnera le chiffre le plus à gauche puis faire un mod 10 sur le nombre donne le nombre sans le premier chiffre et répétez cela jusqu'à ce que vous ayez tous les chiffres
la source
la source
string.TrimStart('-')
mieuxCréez une méthode qui renvoie tous les chiffres et une autre qui les compte:
Cela me semblait être l'approche la plus intuitive pour aborder ce problème. J'ai d'abord essayé la
Log10
méthode en raison de son apparente simplicité, mais elle présente une quantité insensée de boîtiers d'angle et de problèmes de précision.J'ai aussi trouvé le
if
chaîne proposée dans l'autre réponse un peu moche à regarder.Je sais que ce n'est pas la méthode la plus efficace, mais elle vous donne l'autre extension pour renvoyer les chiffres également pour d'autres utilisations (vous pouvez simplement la marquer
private
si vous n'avez pas besoin de l'utiliser en dehors de la classe).Gardez à l'esprit qu'il ne considère pas le signe négatif comme un chiffre.
la source
convertir en chaîne et puis vous pouvez compter le nombre tatal de chiffre par la méthode .length. Comme:
la source
Cela dépend de ce que vous voulez faire exactement avec les chiffres. Vous pouvez parcourir les chiffres du dernier au premier comme ceci:
la source
%
pour obtenir le chiffre, puis/=
pour le réduire.Si ce n'est que pour valider, vous pouvez faire:
887979789 > 99999999
la source
En supposant que votre question se réfère à un entier, ce qui suit fonctionne pour négatif / positif et zéro également:
la source