Подтвердить что ты не робот

Поиск числа цифр целого числа

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

Я нашел это 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) в большинстве языков.

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Ответ 2

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

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

Используйте свои решения друг против друга и позволяйте им бороться с этим. Как интеллектуальные гладиаторы. Вступают три алгоритма! Один алгоритм уходит!

Ответ 3

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

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

изменить: тратить еще некоторое время на покое утром: -)

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

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

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

Альтернативно:

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

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

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

Ответ 4

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

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

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

    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.

Ответ 5

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

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

Результаты

цифры: [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 Итерация: 229 мс

РУЧНОЕ КОНДИЦИОНИРОВАНИЕ: 136 мс

Примечание. Автор воздерживается от каких-либо выводов для чисел с более чем 10 цифрами.

Script

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

Ответ 6

  • преобразование в строку: это должно будет проходить через каждую цифру, найти символ, который сопоставляется с текущей цифрой, добавить символ в коллекцию символов. Затем получите длину результирующего объекта String. Будет работать в O (n) для n = # цифр.

  • for-loop: выполняет 2 математических операции: деление числа на 10 и увеличение счетчика. Будет работать в O (n) для n = # цифр.

  • Логарифмический: вызовет log10 и пол и добавит 1. Выглядит как O (1), но я не уверен, насколько быстро работают функции log10 или floor. Мое знание подобных вещей было атрофировано с отсутствием использования, поэтому в этих функциях может быть скрытая сложность.

Итак, я догадываюсь, что это сводится к: ищет цифровые сопоставления быстрее, чем несколько математических операций или что-то еще в log10? Ответ, вероятно, изменится. Могут быть платформы, где сопоставление символов происходит быстрее, а другие, где выполняют вычисления, быстрее. Также следует иметь в виду, что первый метод создаст новый объект String, который существует только с целью получения длины. Это, вероятно, будет использовать больше памяти, чем два других метода, но это может быть или не иметь значения.

Ответ 7

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

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

Ответ 8

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

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

Ответ 9

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

Ответ 10

import math
def numdigits(n):
    return ( int(math.floor(math.log10(n))) + 1 )

Ответ 11

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

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

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

Вспомните ваш метод № 3 (logs): он глючит для больших чисел (по крайней мере, в 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;
}

Ответ 12

Держите его простым:

long long int a = 223452355415634664;

int x;
for (x = 1; a >= 10; x++)
{
   a = a / 10;
}

printf("%d", x);

Ответ 13

Вы можете использовать рекурсивное решение вместо цикла, но как-то подобное:

@tailrec
def digits (i: Long, carry: Int=1) : Int =  if (i < 10) carry else digits (i/10, carry+1)

digits (8345012978643L)

С длинными изображениями картина может измениться - измерять малые и длинные числа независимо от разных алгоритмов и выбирать подходящую, в зависимости от вашего типичного ввода.:)

Конечно, ничто не сравнится с переключателем:

switch (x) {
  case 0:  case 1:  case 2:  case 3:  case 4:  case 5:  case 6:  case 7:  case 8:  case 9: return 1;
  case 10: case 11: // ...
  case 99: return 2;
  case 100: // you get the point :) 
  default: return 10; // switch only over int
}

за исключением простого-массива:

   int [] size = {1,1,1,1,1,1,1,1,1,2,2,2,2,2,... };
   int x = 234561798;
   return size [x];

Некоторые люди расскажут вам об оптимизации размера кода, но я знаю, преждевременная оптимизация...

Ответ 14

Вот измерение в Swift 4.

Код алгоритмов:

extension Int {
    var numberOfDigits0: Int {
        var currentNumber = self
        var n = 1
        if (currentNumber >= 100000000) {
            n += 8
            currentNumber /= 100000000
        }
        if (currentNumber >= 10000) {
            n += 4
            currentNumber /= 10000
        }
        if (currentNumber >= 100) {
            n += 2
            currentNumber /= 100
        }
        if (currentNumber >= 10) {
            n += 1
        }
        return n
    }

    var numberOfDigits1: Int {
        return String(self).count
    }

    var numberOfDigits2: Int {
        var n = 1
        var currentNumber = self
        while currentNumber > 9 {
            n += 1
            currentNumber /= 10
        }
        return n
    }

}

Код измерения:

var timeInterval0 = Date()
for i in 0...10000 {
    i.numberOfDigits0
}
print("timeInterval0: \(Date().timeIntervalSince(timeInterval0))")

var timeInterval1 = Date()
for i in 0...10000 {
    i.numberOfDigits1
}
print("timeInterval1: \(Date().timeIntervalSince(timeInterval1))")

var timeInterval2 = Date()
for i in 0...10000 {
    i.numberOfDigits2
}
print("timeInterval2: \(Date().timeIntervalSince(timeInterval2))")

Выход

timeInterval0: 1.92149806022644

timeInterval1: 0.557608008384705

timeInterval2: 2.83262193202972

На этой основе измерения Преобразование строк является лучшим вариантом для языка Swift.

Ответ 15

Мне было любопытно узнать результаты @daniel.sedlacek, поэтому я провел некоторое тестирование с использованием Swift для чисел, имеющих более 10 цифр. Я запустил следующую script на игровой площадке.

let base = [Double(100090000000), Double(100050000), Double(100050000), Double(100000200)]
var rar = [Double]()
for i in 1...10 {
    for d in base {
        let v = d*Double(arc4random_uniform(UInt32(1000000000)))
        rar.append(v*Double(arc4random_uniform(UInt32(1000000000))))
        rar.append(Double(1)*pow(1,Double(i)))
    }
}

print(rar)

var timeInterval = NSDate().timeIntervalSince1970

for d in rar {
    floor(log10(d))
}

var newTimeInterval = NSDate().timeIntervalSince1970

print(newTimeInterval-timeInterval)


timeInterval = NSDate().timeIntervalSince1970
for d in rar {
    var c = d
    while c > 10 {
        c = c/10
    }
}

newTimeInterval = NSDate().timeIntervalSince1970

print(newTimeInterval-timeInterval)

Результаты из 80 элементов

0.105069875717163 для пола (log10 (x))
0.867973804473877 для итераций div 10

Ответ 16

log(x,n)-mod(log(x,n),1)+1

Где x - база, а n - число.