Najszybszy sposób obliczania długości dziesiętnej liczby całkowitej? (.NET)

Question

Mam trochę kodu, który wykonuje wiele porównań z 64-bitowymi liczbami całkowitymi, jednak musi uwzględniać długość liczby, tak jakby była sformatowana jako ciąg znaków. Nie mogę zmienić kodu wywołującego, tylko funkcję.

Najprostszym sposobem (oprócz .ToString.() Długość) jest:

(int)Math.Truncate(Math.Log10(x)) + 1; 

jednak, że wykonuje raczej słabo. Ponieważ moja aplikacja wysyła tylko wartości dodatnie, a odcinki są dość równomiernie rozłożone pomiędzy 2 i 9 (z pewną tendencją do 9), ja precomputed wartości i mieć if:

static int getLen(long x) { 
    if (x < 1000000) { 
     if (x < 100) return 2; 
     if (x < 1000) return 3; 
     if (x < 10000) return 4; 
     if (x < 100000) return 5; 
     return 6; 
    } else { 
     if (x < 10000000) return 7; 
     if (x < 100000000) return 8; 
     if (x < 1000000000) return 9; 
     return (int)Math.Truncate(Math.Log10(x)) + 1; // Very uncommon 
    } 
} 

Dzięki temu długość być obliczone z średnio 4 porównuje.

Czy są zatem inne sztuczki, których mogę użyć, aby funkcja ta działała szybciej?

Edytuj: Będzie działać jako kod 32-bitowy (Silverlight).

Aktualizacja:

Wziąłem sugestię Normana i zmienił IFS się trochę skutkować średnio tylko 3 porównuje. Zgodnie z komentarzem Seana usunąłem Math.Truncate. Razem zwiększyło to rzeczy o 10%. Dzięki!

Answer 1

dwie sugestie:

1. profil i umieścić pierwszy wspólnych spraw.
2. Wykonaj wyszukiwanie binarne, aby zminimalizować liczbę porównań w najgorszym przypadku. Możesz wybrać spośród 8 alternatyw, używając dokładnie trzech porównań.

Ta kombinacja prawdopodobnie niewiele Ci nie kupi, chyba że dystrybucja jest bardzo przekrzywiona.

Answer 2

nie wiem, czy to jest szybsze czy nie .. ale zawsze można liczyć ...

static int getLen(long x) { 
    int len = 1; 
    while (x > 0) { 
     x = x/10; 
     len++ 
    }; 
    return len 
}

Answer 3

Co masz na myśli przez długość? Liczba zer lub wszystko? This robi cyfr znaczących, ale masz ogólnej idei

public static string SpecialFormat(int v, int sf) 
{ 
    int k = (int)Math.Pow(10, (int)(Math.Log10(v) + 1 - sf)); 
    int v2 = ((v + k/2)/k) * k; 
    return v2.ToString("0,0"); 
} 

Answer 4

Oto wersja binarna-search, które ja testowałem, który działa w 64-bitowych liczb całkowitych przy użyciu dokładnie pięć porównań każdym razem.

int base10len(uint64_t n) { 
    int len = 0; 
    /* n < 10^32 */ 
    if (n >= 10000000000000000ULL) { n /= 10000000000000000ULL; len += 16; } 
    /* n < 10^16 */ 
    if (n >= 100000000) { n /= 100000000; len += 8; } 
    /* n < 100000000 = 10^8 */ 
    if (n >= 10000) { n /= 10000; len += 4; } 
    /* n < 10000 */ 
    if (n >= 100) { n /= 100; len += 2; } 
    /* n < 100 */ 
    if (n >= 10) { return len + 2; } 
    else   { return len + 1; } 
} 

Wątpię, czy to będzie szybsze niż to, co już robisz. Ale jest przewidywalne.

Answer 5

Skomentowales w kodzie, że 10 lub więcej cyfr jest bardzo rzadkie, więc oryginalne rozwiązanie nie jest złe

Answer 6

Zrobiłem kilka testów, a to wydaje się być 2-4 razy szybciej niż kod, który trzeba teraz :

static int getLen(long x) { 
    int len = 1; 
    while (x > 9999) { 
     x /= 10000; 
     len += 4; 
    } 
    while (x > 99) { 
     x /= 100; 
     len += 2; 
    } 
    if (x > 9) len++; 
    return len; 
} 

Edit:
Oto wersja, która używa więcej operacji Int32, który powinien działać lepiej, jeśli nie masz aplikacji x64:

static int getLen(long x) { 
    int len = 1; 
    while (x > 99999999) { 
     x /= 100000000; 
     len += 8; 
    } 
    int y = (int)x; 
    while (y > 999) { 
     y /= 1000; 
     len += 3; 
    } 
    while (y > 9) { 
     y /= 10; 
     len ++; 
    } 
    return len; 
} 

Answer 7

nie testowałem, ale zmiana prawa podstawowego mówi:

log10 (x) = log2 (x)/log2 (10)

Log2 powinno być nieco szybciej niż log10 jeśli jest realizowany dobrze.

Answer 8

Od Sean Anderson Bit Twiddling Hacks:

baza Find dziennika całkowita 10 liczby całkowitej

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;   // result goes here 
int t;   // temporary 

static unsigned int const PowersOf10[] = 
    {1, 10, 100, 1000, 10000, 100000, 
    1000000, 10000000, 100000000, 1000000000}; 

t = (IntegerLogBase2(v) + 1) * 1233 >> 12; // (use a lg2 method from above) 
r = t - (v < PowersOf10[t]); 

Podstawa dziennika całkowita 10 jest obliczany przez pierwszym użyciu jednej z technik powyżej dla znalezienie logarytmu 2. Przez log relacji 10 (v) = log2 (v)/ log2 (10), musimy pomnożyć przez 1/log2 (10), czyli około 1233/4096, lub 1233, po którym następuje zmiana przesunięcie 12. Dodawanie jest potrzebne , ponieważ IntegerLogBase2 zaokrągla w dół. Wreszcie, ponieważ wartość t wynosi tylko przybliżenie, które może być wyłączone przez , dokładną wartość można znaleźć od odejmując wynik v PowersOf10 [t].

Ta metoda pobiera jeszcze 6 operacji niż IntegerLogBase2. To może być sped górę (na maszynach z szybkiej pamięci dostępu) poprzez modyfikację bazy dziennika metoda 2 tabeli odnośników powyżej tak, że wpisy posiadać co jest obliczane dla t (czyli sprzed dodać, -mulitply, i -przesunięcie). Wykonanie tego wymagałoby w sumie tylko 9 operacji, aby znaleźć bazę logów 10 , przy założeniu użycia 4 tabel: (po jednym dla każdego bajtu v).

Jeśli chodzi o obliczanie IntegerLogBase2, na tej stronie dostępnych jest kilka alternatyw. Jest to doskonałe odniesienie dla wszystkich wysoce zoptymalizowanych operacji na liczbach całkowitych.

Wariant wersji jest również tam, oprócz tego, że przyjmuje wartości (zamiast podstawy log10 wartości) są rozmieszczone równomiernie, a zatem nie wykładniczo nakazał wyszukiwania:

Find baza dziennika całkowitą 10 o całkowitej oczywisty sposób

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;   // result goes here 

r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 : 
    (v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 : 
    (v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0; 

sposób ten działa dobrze, kiedy wejście równomiernie rozłożone na 32-bitowy wartości 76% ze względu na Wprowadza ponownie złapany przez pierwszy porównań, 21% to złapany przez drugi wynik porównania, 2% to złapany przez trzeciego, i tak na (siekanie pozostałych w dół o 90% z każdym porównaniem). W rezultacie średnio mniej niż 2,6 operacji jest potrzebnych na .

Answer 9

static int getDigitCount(int x) 
    { 
    int digits = (x < 0) ? 2 : 1; // '0' has one digit,negative needs space for sign 
    while(x > 9) // after '9' need more 
     { 
     x /= 10; // divide and conquer 
     digits++; 
     } 
    return digits; 
    } 

Answer 10

Jest to prosty sposób.

private static int GetDigitCount(int number) 
{ 
    int digit = 0; 

    number = Math.Abs(number); 

    while ((int)Math.Pow(10, digit++) <= number); 

    return digit - 1; 
} 

Jeśli liczba jest niepodpisana, wówczas "Math.Abs ​​(liczba)" nie jest konieczna.

Zrobiłem metodę rozszerzenia z wszystkimi typami liczbowymi.

private static int GetDigitCount(dynamic number) 
    { 
     dynamic digit = 0; 

     number = Math.Abs(number); 

     while ((dynamic)Math.Pow(10, digit++) <= number) 
      ; 

     return digit - 1; 
    } 

    public static int GetDigit(this int number) 
    { 
     return GetDigitCount(number); 
    } 

    public static int GetDigit(this long number) 
    { 
     return GetDigitCount(number); 
    } 

to używasz tego.

int x = 100; 
int digit = x.GetDigit(); // 3 expected.