Нахождение количества цифр целого числа - PullRequest
Новая
       63

Нахождение количества цифр целого числа

54 голосов
/ 11 июля 2011

Каков наилучший метод для определения количества цифр положительного целого числа?

Я нашел 3 основных метода:

  • преобразование в строку 

    String s = new Integer(t).toString(); 
int len = s.length();

  • для цикла 

    for(long long int temp = number; temp >= 1;)
{
    temp/=10;
    decimalPlaces++;
}

  • логарифмический расчет 

    digits = floor( log10( number ) ) + 1;

, где вы можете вычислить log10 (x) = ln (x) / ln (10) на большинстве языков.

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

Ответы [ 16 ]

53 голосов
/ 11 июля 2011

Всегда есть этот метод: 

n = 1;
if ( i >= 100000000 ) { n += 8; i /= 100000000; }
if ( i >= 10000     ) { n += 4; i /= 10000; }
if ( i >= 100       ) { n += 2; i /= 100; }
if ( i >= 10        ) { n += 1; }
22 голосов
/ 11 июля 2011

Я не знаю, и ответ может отличаться в зависимости от того, как реализован ваш язык.

Итак, стресс-тест! Реализуйте все три решения. Запустите их от 1 до 1 000 000 (или какой-либо другой огромный набор чисел, представляющих числа, с которыми будет работать решение) и времени, которое займет каждый из них.

Противопоставьте свои решения друг другу и дайте им сразиться. Как интеллектуальные гладиаторы. Три алгоритма входят! Один алгоритм уходит!

21 голосов
/ 11 июля 2011

Что ж, правильный ответ будет состоять в том, чтобы измерить его, но вы должны быть в состоянии угадать количество шагов ЦП, связанных с преобразованием строк и их прохождением, в поисках конечного маркера

Затем подумайте, каксколько операций FPU может выполнить ваш процессор, и насколько просто вычислить один журнал.

edit: тратить больше времени на утро понедельника: -) 

String s = new Integer(t).toString(); 
int len = s.length();

Один изпроблема с языками высокого уровня состоит в том, чтобы угадать, сколько работы система делает за кулисами очевидного простого утверждения.Обязательный Joel link

Этот оператор включает выделение памяти для строки и, возможно, пару временных копий строки.Он должен проанализировать целое число и скопировать его цифры в строку, возможно, придется перераспределить и переместить существующую память, если число большое.Возможно, придется проверить кучу настроек локали, чтобы решить, использует ли ваша страна «,» или «.», Возможно, придется выполнить несколько юникодных преобразований.
Затем, чтобы найти длину, нужно снова просканировать всю строкуучитывая юникод и любые местные специфические настройки, такие как - вы говорите на правом-> левом языке?.

В качестве альтернативы: 

digits = floor( log10( number ) ) + 1;

Только потому, что вам будет сложнее сделать это на бумагене значит, что это сложно для компьютера!На самом деле хорошее правило в высокопроизводительных вычислениях, по-видимому, таково: если что-то трудно для человека (динамическая динамика, 3D-рендеринг), это легко для компьютера, и если это легко для человека (распознавание лица, обнаружение голоса вшумная комната) это тяжело для компьютера!

Как правило, можно предположить, что встроенные математические функции log / sin / cos и т. д. - важная часть компьютерного дизайна на протяжении 50 лет.Поэтому, даже если они не отображаются непосредственно в аппаратную функцию в FPU, вы можете поспорить, что альтернативная реализация довольно эффективна.

8 голосов
/ 11 июля 2011

Этот алгоритм также может быть хорош, если предположить, что:

  • Число целое и двоичное кодирование (<< операция дешевая) </li>

  • Мы не знаем числограницы 

    var num = 123456789L;
var len = 0;
var tmp = 1L;
while(tmp < num)
{
    len++;
    tmp = (tmp << 3) + (tmp << 1);
}

Этот алгоритм должен иметь скорость, сравнимую с предоставленной for-loop (2), но немного быстрее из-за (2 сдвига битов, сложение и вычитание вместоделение).

Что касается алгоритма Log10, он даст вам только приблизительный ответ (который близок к реальному, но все же), поскольку аналитическая формула для вычисления функции Log имеет бесконечный цикл и не может быть точно рассчитана Wiki .

6 голосов
/ 12 июля 2011

Условия тестирования

  • Десятичная система счисления
  • Положительные целые числа
  • До 10 цифр
  • Язык: ActionScript3

Результаты

цифры: [1,10],

нет.прогонов: 1,000,000

случайная выборка: 8777509,40442298,477894,329950,513,91751410,313,3159,131309,2

результат: 7,8,6,6,3,8,3,4,6,1

ОБРАТНАЯ СВЯЗЬ: 724мс

ЛОГАРИТИЧЕСКИЙ РАСЧЕТ: 349мс

DIV 10 ITERATION: 229 мс

РУЧНОЕ СОСТОЯНИЕ: 136 мс

Примечание.10 цифр.

Сценарий 

package {
    import flash.display.MovieClip;
    import flash.utils.getTimer;
    /**
     * @author Daniel
     */
    public class Digits extends MovieClip {
        private const NUMBERS : uint = 1000000;
        private const DIGITS : uint = 10;

        private var numbers : Array;
        private var digits : Array;

        public function Digits() {
            // ************* NUMBERS *************
            numbers = [];
            for (var i : int = 0; i < NUMBERS; i++) {
                var number : Number = Math.floor(Math.pow(10, Math.random()*DIGITS));
                numbers.push(number);
            }   
            trace('Max digits: ' + DIGITS + ', count of numbers: ' + NUMBERS);
            trace('sample: ' + numbers.slice(0, 10));

            // ************* CONVERSION TO STRING *************
            digits = [];
            var time : Number = getTimer();

            for (var i : int = 0; i < numbers.length; i++) {
                digits.push(String(numbers[i]).length);
            }

            trace('\nCONVERSION TO STRING - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* LOGARITMIC CALCULATION *************
            digits = [];
            time = getTimer();

            for (var i : int = 0; i < numbers.length; i++) {
                digits.push(Math.floor( Math.log( numbers[i] ) / Math.log(10) ) + 1);
            }

            trace('\nLOGARITMIC CALCULATION - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* DIV 10 ITERATION *************
            digits = [];
            time = getTimer();

            var digit : uint = 0;
            for (var i : int = 0; i < numbers.length; i++) {
                digit = 0;
                for(var temp : Number = numbers[i]; temp >= 1;)
                {
                    temp/=10;
                    digit++;
                } 
                digits.push(digit);
            }

            trace('\nDIV 10 ITERATION - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* MANUAL CONDITIONING *************
            digits = [];
            time = getTimer();

            var digit : uint;
            for (var i : int = 0; i < numbers.length; i++) {
                var number : Number = numbers[i];
                if (number < 10) digit = 1;
                else if (number < 100) digit = 2;  
                else if (number < 1000) digit = 3;  
                else if (number < 10000) digit = 4;  
                else if (number < 100000) digit = 5;  
                else if (number < 1000000) digit = 6;  
                else if (number < 10000000) digit = 7;  
                else if (number < 100000000) digit = 8;  
                else if (number < 1000000000) digit = 9;  
                else if (number < 10000000000) digit = 10;  
                digits.push(digit);
            }

            trace('\nMANUAL CONDITIONING: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));
        }
    }
}
2 голосов
/ 24 апреля 2018

Что касается трех методов, которые вы предлагаете для «определения количества цифр, необходимого для представления заданного числа в заданной базе», мне не нравится ни один из них, на самом деле; Я предпочитаю метод, который я даю ниже.

Ваш метод № 1 (строки): Все, что связано с преобразованием туда и обратно между строками и числами, обычно очень медленное.

Re ваш метод # 2 (temp / = 10): Это фатальный недостаток, потому что предполагает, что x / 10 всегда означает «x делится на 10». Но во многих языках программирования (например, C, C ++), если «x» является целочисленным типом, то «x / 10» означает «целочисленное деление», которое не то же самое, что и деление с плавающей запятой, и оно вводит ошибки округления на каждой итерации, и они накапливаются в рекурсивной формуле, такой как ваше решение №2.

Повторяйте ваш метод № 3 (журналы): он глючит для больших чисел (по крайней мере, в C и, возможно, в других языках), потому что типы данных с плавающей точкой имеют тенденцию быть не такими точными, как 64-битные целые числа.

Поэтому мне не нравятся все 3 из этих методов: # 1 работает, но работает медленно, # 2 не работает, а # 3 глючит для больших чисел. Вместо этого я предпочитаю это, которое работает для чисел от 0 до 18.44 квинтиллионов: 

unsigned NumberOfDigits (uint64_t Number, unsigned Base)
{
   unsigned Digits = 1;
   uint64_t Power  = 1;
   while ( Number / Power >=  Base )
   {
      ++Digits;
      Power *= Base;
   }
   return Digits;
}
2 голосов
/ 29 марта 2013 
import math
def numdigits(n):
    return ( int(math.floor(math.log10(n))) + 1 )
2 голосов
/ 31 августа 2012

Для очень больших целых чисел метод log намного быстрее. Например, с 2491327-значным числом (11920928-е число Фибоначчи, если вам нужно), Python занимает несколько минут, чтобы выполнить алгоритм деления на 10, и миллисекунды, чтобы выполнить 1+floor(log(n,10)).

2 голосов
/ 11 июля 2011

Используйте самое простое решение на любом языке программирования, который вы используете. Я не могу вспомнить случай, когда подсчет цифр в целом числе был бы узким местом в любой (полезной) программе.

C, C ++: 

char buffer[32];
int length = sprintf(buffer, "%ld", (long)123456789);

Haskell: 

len = (length . show) 123456789

JavaScript: 

length = String(123456789).length;

PHP: 

$length = strlen(123456789);

Visual Basic (не проверено): 

length = Len(str(123456789)) - 1
2 голосов
/ 11 июля 2011

Очевидно, что вы можете исключить метод 1 из соревнования, потому что используемый им алгоритм atoi / toString будет аналогичен методу 2.

Скорость метода 3 зависит от того, компилируется ли код для системы, чей набор инструкций включает базу журнала 10.

Страница:
...