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

У меня есть код, который делает много сравнений 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).

Update:

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

Ответ 1

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

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

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

Ответ 2

От Шона Андерсона Бит Tweedling 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 [т].

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

Ответ 3

Здесь выполняется бинарно-поисковая версия, которую я тестировал, которая работает с 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; }
}

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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

Ответ 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");  
}

Ответ 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.