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

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

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 ]

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

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

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

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

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

1 голос
/ 31 января 2018

Вот измерение в 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.

1 голос
/ 12 июля 2011

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

@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];

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

1 голос
/ 11 июля 2011

Сохраняйте это простым: 

long long int a = 223452355415634664;

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

printf("%d", x);
0 голосов
/ 08 апреля 2017

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

Где x - это основание, а n - это число.

0 голосов
/ 03 июня 2016

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

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 для деления 10 итераций

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