Самый быстрый способ рассчитать десятичную длину целого числа? (.СЕТЬ)

Question

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

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

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

Однако это работает довольно плохо. Поскольку мое приложение отправляет только положительные значения, а длины довольно равномерно распределяются между 2 и 9 (с некоторым смещением в сторону 9), я предварительно вычислил значения и получил операторы 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
    }
}

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

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

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

Обновление:

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

Answer 1

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

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

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

Answer 2

От Шона Андерсона Бит Тиддлинг Хаки :

Найти целочисленную логарифмическую базу 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 [т].

Этот метод требует еще 6 операций чем IntegerLogBase2. Это может быть ускорено вверх (на машинах с быстрой памятью доступ) путем изменения базы журнала 2 метод поиска в таблице выше, так что записи содержат то, что рассчитывается для т (то есть, предварительно добавить, -mulitply, и -сдвиг). Для этого потребуется всего 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% входов поймал первое сравнение, 21% поймал второе сравнение, 2% пойман третьим и тд (рубить оставшиеся на 90% с каждым сравнением). В следствии, требуется менее 2,6 операций на средний.

Answer 3

Я провел некоторое тестирование, и это кажется в 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 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

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

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

    number = Math.Abs(number);

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

    return digit - 1;
}

Если число не подписано в 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.

Answer 6

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 7

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

Log10 (x) = Log2 (x) / Log2 (10)

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

Answer 8

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

Answer 9

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

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 10

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

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