Подсчитайте количество цифр - какой метод наиболее эффективен?

Question

Существует более одного решения для нахождения числа цифр в данном номере.

Например:

Метод-1:

int findn(int num)
{
    char snum[100];
    sprintf(snum, "%d", num);
    return strlen(snum);
}

Метод-2:

int findn(int num)
{
    if (num == 0) return 1;
    int n = 0;
    while(num) {
        num /= 10;
        n++;
    }
    return n;
}

Метод-3:

int findn(int num)
{
    /* math.h included */
    return (int) log10(num) + 1;
}

Вопрос в том, какой метод наиболее эффективен?Я знаю, что метод-2 O(n), но как насчет метода-1 и метода-3?Как найти сложность библиотечных функций во время выполнения?

Answer 1

Следующее еще более эффективно:

int findn(int num)
{
   if ( num < 10 )
      return 1;
   if ( num < 100 )
      return 2;
   //continue until max int
}

Вы можете оптимизировать это еще больше, выполнив бинарный поиск, но это будет излишним.

Answer 2

В нынешнем виде принятый и наиболее одобренный ответ ( все еще ) неверен для отрицательных чисел. Если бы ответчик нашел время, чтобы проверить его и выяснить,что он разбит на отрицательные числа, он, скорее всего, потратил бы больше времени, чем машина, просто используя snprintf, то есть

int count_digits(int arg) {
    return snprintf(NULL, 0, "%d", arg) - (arg < 0);
}

Мы больше не в 1980-х;прекратить кодировать, как будто мы.Я - фанат C-стандарта, и мой любимый ответ, данный здесь, был ответ Дао Фенга ... но даже это не вошло в , почему это самый эффективный ответ на данный момент;в этом ответе я намерен показать, что его ответ можно улучшить, рассмотрев следующее:

• Производительность программирования важнее, чем эффективность кода, , поскольку она почти наверняка будет стоить дорожевремя на написание и тестирование новых функций должным образом, чем на несколько микросекунд времени выполнения.
• Повторное использование тех же стандартных функций библиотеки, которые другие программы обычно используют (вероятно), сохраняет эти стандартные библиотеки в кэше ЦП. Пропуск кеша (например, когда ваш код должен быть скопирован из ОЗУ в ЦП) может стоить до 50 инструкций ЦП, не говоря уже о том, что другой код может закончиться тем, что из-за еще одного пропуска кеша snprintf вернетсяв любом случае в кэш.
• Отмена требований к хранилищу может привести к дополнительной оптимизации.

---

Ниже описывается микрооптимизация, которая препятствует вашейпроизводительность. Из-за недостатка информации, которую вы указали в своем ответе, нобOdy, который отвечает на вопрос в его нынешнем виде, может предоставить любое доказательство, не делая предположений о:

• Когда мы оптимизируем, нам нужно найти наиболее существенное узкое место в полном решении (проблема, которую вашПрограмма предназначена для решения) .Здесь есть две возможности: A) Вы хотите вычислить количество байтов для выделения, чтобы сохранить строку, содержащую эти цифры;Б) Вы просто хотите посчитать количество цифр или что-то еще для ударов.Подробнее об этом позже.На данный момент важно понять, что вы, вероятно, говорите о части решения , и эта часть может быть не самым существенным узким местом .
• Компилятор, который вы 'При использовании ОС, которую вы используете, и машины, которую вы используете (включая скорость ОЗУ, поскольку некоторые из нас вносят потенциальные ошибки в кеше, на которые больше влияет медленная память, чем быстрая память), могут возникнуть самые серьезные проблемы.Некоторые компиляторы отличаются от других и оптимизируют некоторые фрагменты кода для некоторых операционных систем, процессоров и т. Д. Лучше, чем другие.

Вы можете избежать микрооптимизации, измеряя узкие места, то есть профилируя ( «бенчмаркинг» ) каждого из этих решений в вашей системе , при условии, что они даже решают ваши проблемы должным образом.Если решение не решает проблему, это не решение, поэтому его не следует рассматривать ... Если все сделано правильно, это должно устранить микрооптимизацию.Некоторые компиляторы даже обеспечивают интеллектуальную оптимизацию по профилю , которая обычно экономит 20-30% за счет реорганизации ветвей и объектов для обеспечения кеширования и делает это автоматически .

I 'Мы уже рассмотрели счетные цифры, которые, я думаю, наверняка отвечают на ваш вопрос, но есть случаи, когда вы могли бы думать , вам нужно считать цифры, когда вы не , и способностьСнять накладные расходы на подсчет цифр может быть очень желательной оптимизацией, как в человеко-часах , так и в машинных часах.

Например, если вы хотите вычислить количество байтов, выделяемых для хранения строки, содержащей эти цифры, вы не должны использовать какое-либо время выполнения, поскольку макрос препроцессора может использоваться для вычисления максимального количества цифр (илисимволы, включая знак), а также любые драгоценные байты временного хранилища, которые вы пытаетесь сохранить, будут значительно превосходить по численности байты машинного кода, добавленные в логику, что для меня кажется чрезмерной ценой.Для программиста также полезно использовать макрос препроцессора;один и тот же макрос можно использовать для любого целочисленного типа. См. мой ответ на этот вопрос для решения этой проблемы ;в конце концов, нет смысла повторяться ...

Answer 3

Встроенные функции GCC / Clang __builtin_clz() или Microsoft Visual C _BitScanReverse() объединены в одну машинную инструкцию на многих машинах.Вы можете использовать это в качестве основы для решения O (1).Вот 32-битная реализация:

#include <limits.h>
#include <stdint.h>

/* Return the number of digits in the decimal representation of n. */
unsigned digits(uint32_t n) {
    static uint32_t powers[10] = {
        0, 10, 100, 1000, 10000, 100000, 1000000,
        10000000, 100000000, 1000000000,
    };
    static unsigned maxdigits[33] = {
        1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5,
        5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 
    };
    unsigned bits = sizeof(n) * CHAR_BIT - __builtin_clz(n);
    unsigned digits = maxdigits[bits];
    if (n < powers[digits - 1]) {
        -- digits;
    }
    return digits;
}

Answer 4

Я думаю, что вы можете написать первый метод как

int findn(int num)
{
    char snum[100];    
    return  sprintf(snum, "%d", num);
}

потому что sprintf вернет количество записанных символов, и вы можете сохранить вызов в strlen.

Что касается эффективности, я думаю, что это зависит от реализации sprintf, вам может понадобиться найти источник sprintf и посмотреть, насколько это эффективно.

Answer 5

Один лайнер: for(digits = 0; num > 0; digits++) num /= 10;

Answer 6

Эти функции дают совершенно разные результаты для неположительных чисел (наихудший - метод 3), поэтому сравнение их временных сложностей имеет сомнительную ценность.Я бы использовал тот, который дает ответ, требуемый во всех случаях;без контекста мы не можем знать, что это такое (это, вероятно, не метод 3).

Для метода 1 findn(0) == 1 и findn(-n) == digits in n + 1 (из-за отрицательного знака).

Для метода 2 findn(0) == 0 и findn(-n) == digits in n.

Для метода 3 findn(0) == INT_MIN и findn(-n) == INT_MIN также.

Answer 7

Попробуйте бинарный поиск. Для ясности, давайте предположим, 32-разрядные целые числа со знаком. Сначала проверьте, если x < 10000. Далее в зависимости от ответа, если x < 100 или x < 1000000, и т. Д.

Это O(log n), где n - количество цифр.

Answer 8

Я думаю, sprintf() будет использовать ваш метод 2 , чтобы напечатать число (определить длину строки для печати, а затем напечатать каждый символ строки), так что это будет по своей природемедленнее.

Число 3, вероятно, потребует некоторой полиномиальной аппроксимации ln(), которая будет включать более 1 деления, поэтому я думаю, что это также будет медленнее ( здесь a fastРеализация ln (), все еще включающая деление на числа с плавающей точкой ... так что НАМНОГО медленнее).

Так что мое предварительное предположение состоит в том, что метод 2 - это путь.

Обратите внимание, что это довольно либеральный способ решения этой проблемы.Я предполагаю, что тестирование старой доброй миллионной итерации с каждой функцией покажет вам результат.Но это было бы слишком bruteforce , не так ли?

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

Answer 9

Функция printf возвращает количество успешно напечатанных цифр.

int digits,n=898392;

digits=printf("%d",n);
printf("Number of digits:%d",digits);

Выход:

898392

Количество цифр: 6

Answer 10

Это мое решение ... оно будет считать до 100 цифр, или вы знаете, что хотите, чтобы оно считало до.

max_digits = 100

int numdigits(int x) {
  for (int i = 1; i < max_digits; i++) {
    if (x < pow(10, i)) {
      return i;
    }
  }
  return 0;
}