Подсчет количества цифр в числе - какое из этих двух решений быстрее?

Question

Недавно в одном из интервью меня спросили, как мне написать алгоритм для подсчета количества цифр в данном числе. Так, например, если бы мне дали число 500, результатом было бы 3. Если бы мне дали число 15345, результатом было бы 5.

Я придумал 2 возможных решения:

1. Рекурсивно делите число на 10, пока результат не станет меньше 1, а затем верните количество выполненных рекурсий.

2. Преобразуйте число в строку, а затем посчитайте количество элементов в этой строке.

Затем меня спросили, какая операция более эффективна при работе с очень большими числами, и я не смог дать хороший ответ. Итак, мой вопрос: какой правильный ответ здесь - какой алгоритм быстрее и почему?

Answer 1

Ну, чтобы преобразовать целое число в строку, основной itoa (целое число в строку) функция работает примерно так:

result = ""
while (number > 0)
{
    digit = number % 10
    append digit to result
    number = number / 10
}

Таким образом, между первым и вторым решением не так уж много различий. Первое решение будет принимать O(n) итераций, где n - количество цифр в целом числе. Второе решение будет иметь такую ​​же сложность, и дополнительно будет подсчитывать n цифр в строке за O(n) время, для общей сложности O (2n) = O(n).

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

Answer 2

Я рассчитал три варианта:

• повторное деление
• логарифм
• длина строки

для длин, кратных 10. Я пробежал 10000 прогонов каждого.

Результаты в микросекундах:

length     division     logarithm     string length
---------------------------------------------------
  10           7           10            16
  20          14           14            26
  30          28           14            41
  40          46           14            59
  50          73           14            80
  60          91           14            80
  70         113           14            98
  80         136           14           106
  90         170           14           116
 100         197           14           129

В этих данных есть артефакты различного происхождения, но я думаю, вы поняли.

Answer 3

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

Оба ваших ответа работают в линейном времени, поэтому их следует считать эквивалентными.

Answer 4

Для краткости, это самый быстрый способ сделать это, предполагая, что входные данные имеют тип unsigned long или int некоторого вида:

int count_digits( unsigned long n ){
   unsigned long long quotient;
   unsigned int ctDigits = 1;
   while( n > 9 ){
      ctDigits++;
      quotient = (n >> 1) + (n >> 2);
      quotient += (quotient >> 4);   
      quotient += (quotient >> 8);   
      quotient += (quotient >> 16);   
      quotient = quotient >> 3;   
      n -= ((quotient << 2) + quotient) << 1; // computes the remainder
   }
   return ctDigits;
}

Любое решение, которое использует деление (которое включает в себя любое преобразование itoa / string), будет намного медленнее, потому что деление является дорогой операцией. В мире высокоскоростных вычислений деление это плохо, плохо.