Самый быстрый способ вычисления десятичной длины целого числа? (.NET)

Question

У меня есть код, который делает много сравнений с 64-битными целыми числами, однако он должен учитывать длину числа, как если бы он был отформатирован как строка. Я не могу изменить код вызова, только функцию.

Самый простой способ (кроме того. .ToString() Length) является:

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

Однако это выполняет весьма слабо. Так как мое приложение отправляет только положительные значения, а длины достаточно равномерно распределены между 2 и 9 (с некоторым уклоном в сторону 9), я предварительно вычислены значения и имеют ли заявления:

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 
    } 
} 

Это позволяет длина вычисляется с в среднем 4 сравнения.

Итак, есть ли другие трюки, которые я могу использовать для ускорения этой функции?

Редактировать: Это будет работать как 32-разрядный код (Silverlight).

Update:

Я принял предложение Нормана и изменил сослагательное наклонение вокруг немного, чтобы привести в среднем только 3 сравнивает. Согласно комментарию Шона, я удалил Math.Truncate. Вместе это увеличило примерно 10%. Благодаря!

Answer 1

Два предложения:

1. Профиль и поставить общие случаи первым.
2. Сделайте двойной поиск, чтобы свести к минимуму количество сравнений в худшем случае. Вы можете выбрать среди 8 альтернатив, используя ровно три сравнения.

Эта комбинация, вероятно, не покупает вас, если распределение не очень искажено.

Answer 2

не уверен, если это быстрее или нет .. но вы всегда можете рассчитывать ...

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

Answer 3

Что вы имеете в виду по длине? Количество нулей или всего остального? This делает значащие цифры, но получить общее представление

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

Вот двоичный поиск версии, которую я испытал, который работает на 64-битных целых числах, используя ровно пять сравнений каждый раз.

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; } 
} 

Я сомневаюсь, что это произойдет быстрее, чем вы уже делаете. Но это предсказуемо.

Answer 5

Вы прокомментировали в коде, 10 цифр или более очень редко, поэтому ваше оригинальное решение не плохо

Answer 6

Я сделал некоторые испытания, и это, кажется, в 2-4 раза быстрее, чем код, который у вас есть сейчас :

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:
Вот версия, которая использует больше операций Int32, которые должны работать лучше, если у вас нет приложения 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

Я не проверял это, но изменение базового закона гласит:

log10 (х) = log2 (х)/Log2 (10)

Log2 должен быть немного быстрее, чем log10, если он реализован правильно.

Answer 8

От Шон Андерсон Bit Twiddling Hacks:

Найти целое бревно основание 10 целого числа

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]); 

Основание 10 целое число, журнал вычисленного сначала с помощью одного из методов выше для нахождение логарифмической базы 2. К отношение log10 (v) = log2 (v)/ log2 (10), нам нужно умножить его на 1/log2 (10), что составляет приблизительно 1233/4096 или 1233, за которым следует правая сменная 12. Для этого необходимо добавить один , потому что раунды IntegerLogBase2 вниз. Наконец, поскольку значение t равно , это может быть только , точное значение найдено по , вычитая результат v < PowersOf10 [t].

Этот метод принимает еще 6 операций , чем IntegerLogBase2. Это может быть вызвано up (на машинах с быстрой памятью доступ) путем изменения базы регистрации 2 3 метод поиска таблиц выше, так что в записях выполняется то, что вычислено для t (то есть предварительно добавьте, -mulitply, и -shift). Для этого потребуется всего 9 операций, чтобы найти базу данных 10, предполагая, что 4 таблицы были использованы (по одному для каждого байта v).

Что касается вычисления IntegerLogBase2, на этой странице представлено несколько альтернатив. Это отличная ссылка для всех видов высоко оптимизированных целых операций.

Вариант версии также есть, за исключением того, что принимает значения (а не логарифм 10 значений) равномерно распределены, и поэтому делает экспоненциально упорядоченный поиск:

Найти число журналов базы 10 из целого числа очевидный способ

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; 

Этот метод хорошо работает, когда входной равномерно распределена по 32-битной значения, потому что 76% вводит re , пойманный первым сравнением, 21% - , пойманным вторым сравнением, 2% - , пойманным третьим и т. д. (измельчение оставшегося вниз на 90% с каждым сравнением). В результате требуется менее 2,6 операций на в среднем.

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

Это простой способ.

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

    number = Math.Abs(number); 

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

    return digit - 1; 
} 

Если number is unsigned int, то «Math.Abs ​​(number)» необязательно.

Я сделал метод расширения со всеми числовыми типами.

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); 
    } 

, то вы используете это.

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