Wie kann ich die Gesamtzahl der Ziffern in einer Zahl zählen?

114

Wie kann ich die Gesamtzahl der Ziffern einer Zahl in C # zählen? Beispielsweise hat die Nummer 887979789 9 Ziffern.

Arash
quelle
6
Versuchen Sie es mit .Length, wenn es nicht funktioniert. Konvertieren Sie es zuerst in einen String
Breezer
Angenommen, x = 887979789; x.ToString (). Count (); werde dir das geben.
nPcomp

Antworten:

174

Ohne in eine Zeichenfolge zu konvertieren, können Sie Folgendes versuchen:

Math.Ceiling(Math.Log10(n));

Korrektur nach dem Kommentar von ysap:

Math.Floor(Math.Log10(n) + 1);
Steve
quelle
10
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.
stack247
83

Versuche dies:

myint.ToString().Length

Funktioniert es ?

Andiih
quelle
25
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).

Int32-Version:

public static class Int32Extensions
{
    // IF-CHAIN:
    public static int Digits_IfChain(this int n)
    {
        if (n >= 0)
        {
            if (n < 10) return 1;
            if (n < 100) return 2;
            if (n < 1000) return 3;
            if (n < 10000) return 4;
            if (n < 100000) return 5;
            if (n < 1000000) return 6;
            if (n < 10000000) return 7;
            if (n < 100000000) return 8;
            if (n < 1000000000) return 9;
            return 10;
        }
        else
        {
            if (n > -10) return 2;
            if (n > -100) return 3;
            if (n > -1000) return 4;
            if (n > -10000) return 5;
            if (n > -100000) return 6;
            if (n > -1000000) return 7;
            if (n > -10000000) return 8;
            if (n > -100000000) return 9;
            if (n > -1000000000) return 10;
            return 11;
        }
    }

    // USING LOG10:
    public static int Digits_Log10(this int n) =>
        n == 0 ? 1 : (n > 0 ? 1 : 2) + (int)Math.Log10(Math.Abs((double)n));

    // WHILE LOOP:
    public static int Digits_While(this int n)
    {
        int digits = n < 0 ? 2 : 1;
        while ((n /= 10) != 0) ++digits;
        return digits;
    }

    // STRING CONVERSION:
    public static int Digits_String(this int n) =>
        n.ToString().Length;
}

Int64-Version:

public static class Int64Extensions
{
    // IF-CHAIN:
    public static int Digits_IfChain(this long n)
    {
        if (n >= 0)
        {
            if (n < 10L) return 1;
            if (n < 100L) return 2;
            if (n < 1000L) return 3;
            if (n < 10000L) return 4;
            if (n < 100000L) return 5;
            if (n < 1000000L) return 6;
            if (n < 10000000L) return 7;
            if (n < 100000000L) return 8;
            if (n < 1000000000L) return 9;
            if (n < 10000000000L) return 10;
            if (n < 100000000000L) return 11;
            if (n < 1000000000000L) return 12;
            if (n < 10000000000000L) return 13;
            if (n < 100000000000000L) return 14;
            if (n < 1000000000000000L) return 15;
            if (n < 10000000000000000L) return 16;
            if (n < 100000000000000000L) return 17;
            if (n < 1000000000000000000L) return 18;
            return 19;
        }
        else
        {
            if (n > -10L) return 2;
            if (n > -100L) return 3;
            if (n > -1000L) return 4;
            if (n > -10000L) return 5;
            if (n > -100000L) return 6;
            if (n > -1000000L) return 7;
            if (n > -10000000L) return 8;
            if (n > -100000000L) return 9;
            if (n > -1000000000L) return 10;
            if (n > -10000000000L) return 11;
            if (n > -100000000000L) return 12;
            if (n > -1000000000000L) return 13;
            if (n > -10000000000000L) return 14;
            if (n > -100000000000000L) return 15;
            if (n > -1000000000000000L) return 16;
            if (n > -10000000000000000L) return 17;
            if (n > -100000000000000000L) return 18;
            if (n > -1000000000000000000L) return 19;
            return 20;
        }
    }

    // USING LOG10:
    public static int Digits_Log10(this long n) =>
        n == 0L ? 1 : (n > 0L ? 1 : 2) + (int)Math.Log10(Math.Abs((double)n));

    // WHILE LOOP:
    public static int Digits_While(this long n)
    {
        int digits = n < 0 ? 2 : 1;
        while ((n /= 10L) != 0L) ++digits;
        return digits;
    }

    // STRING CONVERSION:
    public static int Digits_String(this long n) =>
        n.ToString().Length;
}

Diskussion

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

.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 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:

Geben Sie hier die Bildbeschreibung ein

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:
    class Program
    {
        private static void Main(string[] args)
        {
            Console.WriteLine("\r\n.NET Core");

            RunTests_Int32();
            RunTests_Int64();
        }

        // Int32 Performance Tests:
        private static void RunTests_Int32()
        {
            Console.WriteLine("\r\nInt32");

            const int size = 100000000;
            int[] samples = new int[size];
            Random random = new Random((int)DateTime.Now.Ticks);
            for (int i = 0; i < size; ++i)
                samples[i] = random.Next(int.MinValue, int.MaxValue);

            Stopwatch sw1 = new Stopwatch();
            sw1.Start();
            for (int i = 0; i < size; ++i) samples[i].Digits_IfChain();
            sw1.Stop();
            Console.WriteLine($"IfChain: {sw1.ElapsedMilliseconds} ms");

            Stopwatch sw2 = new Stopwatch();
            sw2.Start();
            for (int i = 0; i < size; ++i) samples[i].Digits_Log10();
            sw2.Stop();
            Console.WriteLine($"Log10: {sw2.ElapsedMilliseconds} ms");

            Stopwatch sw3 = new Stopwatch();
            sw3.Start();
            for (int i = 0; i < size; ++i) samples[i].Digits_While();
            sw3.Stop();
            Console.WriteLine($"While: {sw3.ElapsedMilliseconds} ms");

            Stopwatch sw4 = new Stopwatch();
            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 = new int[]
            {
                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:
        private static void RunTests_Int64()
        {
            Console.WriteLine("\r\nInt64");

            const int size = 100000000;
            long[] samples = new long[size];
            Random random = new Random((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 = new Stopwatch();
            sw1.Start();
            for (int i = 0; i < size; ++i) samples[i].Digits_IfChain();
            sw1.Stop();
            Console.WriteLine($"IfChain: {sw1.ElapsedMilliseconds} ms");

            Stopwatch sw2 = new Stopwatch();
            sw2.Start();
            for (int i = 0; i < size; ++i) samples[i].Digits_Log10();
            sw2.Stop();
            Console.WriteLine($"Log10: {sw2.ElapsedMilliseconds} ms");

            Stopwatch sw3 = new Stopwatch();
            sw3.Start();
            for (int i = 0; i < size; ++i) samples[i].Digits_While();
            sw3.Stop();
            Console.WriteLine($"While: {sw3.ElapsedMilliseconds} ms");

            Stopwatch sw4 = new Stopwatch();
            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 = new long[] 
            {
                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");
        }
    }
}
sɐunıɔ ןɐ qɐp
quelle
4
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)

ysap
quelle
2
log10 (0) ist -infinity
Alex Klaus
2
@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.

public static int Length(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.

nawfal
quelle
7

Die Antwort von Steve ist richtig , funktioniert aber nicht für ganze Zahlen unter 1.

Hier eine aktualisierte Version, die für Negative funktioniert:

int digits = n == 0 ? 1 : Math.Floor(Math.Log10(Math.Abs(n)) + 1)
Patrick Hofman
quelle
Sie vermissen ein Castingto int:digits = n == 0 ? 1 : (int)Math.Floor(Math.Log10(Math.Abs(n)) + 1);
sɐunıɔ ןɐ qɐp
Ich habe es ohne if-Anweisung gemacht: digits = (int) Math.Floor (Math.Abs ​​(Math.Log10 (Math.Abs ​​(n))) + 1)
KOLRH
Dies löst eine Ausnahme aus, wenn n = int.MinValue.
sɐunıɔ ןɐ qɐp
5

Rekursion verwenden (manchmal in Interviews gefragt)

public int CountDigits(int number)
{
    // In case of negative numbers
    number = Math.Abs(number);

    if (number >= 10)
        return CountDigits(number / 10) + 1;
    return 1;
 }

quelle
1
Dies löst eine Ausnahme aus, wenn number = int.MinValue.
sɐunıɔ ןɐ qɐp
4
static void Main(string[] args)
{
    long blah = 20948230498204;
    Console.WriteLine(blah.ToString().Length);
}
weloytty
quelle
1
Vorsicht vor Negativen: -1= 2
MrLore
2

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:

static byte[] _0000llll = new byte[0x10000];
static byte[] _FFFFllll = new byte[0x10001];
static sbyte[] _hhhhXXXXdigits = new sbyte[0x10000];

// Special cases where the high DWORD is not enough information to find out how
// many digits.
static ushort[] _lowordSplits = new ushort[12];
static sbyte[] _lowordSplitDigitsLT = new sbyte[12];
static sbyte[] _lowordSplitDigitsGE = new sbyte[12];

static Int32Extensions()
{
    // 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();
}

private static void 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 negatives
        int 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 etc
            int 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++;
        }
    }
}

private static void 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;
}

private static void 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;
}



public static int Digits_LookupTable(this int 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];
    }
    else if(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];
    else
        return _lowordSplitDigitsGE[splitIndex];
}

Binäre Suchversion

        public static int Digits_BinarySearch(this int n)
        {
            if(n >= 0)
            {
                if(n <= 9999) // 0 .. 9999
                {
                    if(n <= 99) // 0 .. 99
                    {
                        return (n <= 9) ? 1 : 2;
                    }
                    else // 100 .. 9999
                    {
                        return (n <= 999) ? 3 : 4;
                    }
                }
                else // 10000 .. int.MaxValue
                {
                    if(n <= 9_999_999) // 10000 .. 9,999,999
                    {
                        if(n <= 99_999)
                            return 5;
                        else if(n <= 999_999)
                            return 6;
                        else
                            return 7;
                    }
                    else // 10,000,000 .. int.MaxValue
                    {
                        if(n <= 99_999_999)
                            return 8;
                        else if(n <= 999_999_999)
                            return 9;
                        else
                            return 10;
                    }
                }
            }
            else
            {
                if(n >= -9999) // -9999 .. -1
                {
                    if(n >= -99) // -99 .. -1
                    {
                        return (n >= -9) ? 1 : 2;
                    }
                    else // -9999 .. -100
                    {
                        return (n >= -999) ? 3 : 4;
                    }
                }
                else // int.MinValue .. -10000
                {
                    if(n >= -9_999_999) // -9,999,999 .. -10000
                    {
                        if(n >= -99_999)
                            return 5;
                        else if(n >= -999_999)
                            return 6;
                        else
                            return 7;
                    }
                    else // int.MinValue .. -10,000,000 
                    {
                        if(n >= -99_999_999)
                            return 8;
                        else if(n >= -999_999_999)
                            return 9;
                        else
                            return 10;
                    }
                }
            }
        }

        Stopwatch sw0 = new Stopwatch();
        sw0.Start();
        for(int i = 0; i < size; ++i) samples[i].Digits_BinarySearch();
        sw0.Stop();
        Console.WriteLine($"Binary-Search: {sw0.ElapsedMilliseconds} ms");
Alan Singfield
quelle
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

Romejoe
quelle
0
int i = 855865264;
int NumLen = i.ToString().Length;
Javed Akram
quelle
1
schlägt für negatives int und für Zahlen wie 23.00 fehl. Mach es string.TrimStart('-')besser
nawfal
0

Erstellen Sie eine Methode, die alle Ziffern zurückgibt, und eine andere, die sie zählt:

public static int GetNumberOfDigits(this long value)
{
    return value.GetDigits().Count();
}

public static IEnumerable<int> GetDigits(this long value)
{
    do
    {
        yield return (int)(value % 10);
        value /= 10;
    } while (value != 0);
}

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.

julealgon
quelle
-2

In eine Zeichenfolge konvertieren und dann können Sie die Gesamtzahl der Ziffern nach der Methode .length zählen. Mögen:

String numberString = "855865264".toString();
int NumLen = numberString .Length;

quelle
1
Das Zuweisen einer Zeichenfolge ist völlig unnötig.
Krythic
-2

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:

int tmp = number;
int lastDigit = 0;
do
{
    lastDigit = tmp / 10;
    doSomethingWithDigit(lastDigit);
    tmp %= 10;
} while (tmp != 0);
Mihran Hovsepyan
quelle
1
Ihre Logik ist umgekehrt. Sie müssen verwenden %, um die Ziffer zu erhalten und sie dann /=zu kürzen.
Julealgon
-3

Wenn es nur zur Validierung ist, könnten Sie Folgendes tun: 887979789 > 99999999

Johan van der Slikke
quelle
-3

Angenommen, Ihre Frage bezieht sich auf ein int, funktioniert das Folgende auch für negativ / positiv und null:

Math.Floor((decimal) Math.Abs(n)).ToString().Length
Petru Zaharia
quelle