Găsirea numărului de cifre ale unui număr întreg (Programare, Algoritm, Cifre, Numărare)

daniel.sedlacek a intrebat.

Care este cea mai bună metodă pentru a găsi numărul de cifre al unui număr întreg pozitiv?

Am găsit această 3 metode de bază:

  • conversia în șir de caractere

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

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

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

unde se poate calcula log10(x) = ln(x) / ln(10) în majoritatea limbajelor.

Prima dată am crezut că metoda cu șirul de caractere este cea mai murdară, dar cu cât mă gândesc mai mult la ea cu atât cred că este cea mai rapidă metodă. Sau nu este așa?

Comentarii

    15

  • Definiți „cel mai bun”, mai întâi. Apoi, alegerea „celui mai bun” algoritm este ușoară. –  > Por S.Lott.
  • Folosește sursa, Luke: docjar.com/html/api/java/lang/Integer.java.html –  > Por Blrfl.
  • Această întrebare aparține probabil la codegolf. –  > Por Macneil Shonle.
  • Se pare că nimeni de aici nu are nicio considerație pentru numerele întregi care nu sunt de bază 10. Nu se utilizează Integer.toString(t, radix), temp /= radix; (și în mod corespunzător, numDigits++;, deoarece se generalizează de la zecimale), sau ln(x) / ln(radix)… –  > Por JAB.
  • @Joey Adams: Bună observație… Ei bine, sunt încrezător în punctul de plutire ln(e). –  > Por Jean-François Corbett.
17 răspunsuri
Mike Dunlavey

Există întotdeauna această metodă:

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

Comentarii

  • Dacă știți ceva despre intervalul de numere întregi care trebuie să fie suportate, aceasta poate fi foarte eficientă. –  > Por jimreed.
  • @jimreed: Corect. Trebuie să știți ceil(log2(log10(MAXINT))). Apoi, face cel mult acel număr de diviziuni trunchiate. –  > Por Mike Dunlavey.
  • Sau, dacă aceasta este o problemă reală de codare și nu doar un puzzle, și dacă știți că numărul întreg este întotdeauna mai mic de 10.000, atunci nici măcar nu aveți nevoie de primele două instrucțiuni if. –  > Por jimreed.
Martin Beckett

Ei bine, răspunsul corect ar fi să îl măsurați – dar ar trebui să puteți face o presupunere despre numărul de pași ai procesorului implicați în convertirea șirurilor de caractere și în parcurgerea lor în căutarea unui marker final

Apoi gândește-te la câte operații FPU/s poate face procesorul tău și cât de ușor este să calculezi un singur log.

edit: pierzând ceva mai mult timp într-o dimineață de luni 🙂

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

Una dintre problemele cu limbajele de nivel înalt este să ghicești câtă muncă face sistemul în spatele scenei unei declarații aparent simple. Obligatoriu Link Joel

Această instrucțiune implică alocarea de memorie pentru un șir de caractere și, eventual, câteva copii temporare ale unui șir de caractere. Trebuie să analizeze numărul întreg și să copieze cifrele acestuia într-un șir de caractere, fiind posibil să trebuiască să realoce și să mute memoria existentă dacă numărul este mare. S-ar putea să trebuiască să verifice o serie de setări locale pentru a decide dacă țara dumneavoastră folosește „,” sau „.”, s-ar putea să trebuiască să facă o serie de conversii unicode.
Apoi, pentru a afla lungimea trebuie să scaneze întregul șir, luând din nou în considerare unicode și orice setări locale specifice, cum ar fi – sunteți într-o limbă de dreapta și de stânga?

Alternativ:

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

Doar pentru că ți-ar fi mai greu să faci acest lucru pe hârtie, nu înseamnă că este greu pentru un computer! De fapt, o regulă bună în calculul de înaltă performanță pare să fi fost: dacă ceva este greu pentru un om (dinamica fluidelor, redarea 3D) este ușor pentru un computer, iar dacă este ușor pentru un om (recunoașterea feței, detectarea unei voci într-o cameră zgomotoasă) este greu pentru un computer!

În general, se poate presupune că funcțiile matematice integrate log/sin/cos etc. reprezintă o parte importantă a proiectării calculatoarelor de 50 de ani. Astfel, chiar dacă acestea nu sunt direct legate de o funcție hardware din FPU, puteți fi siguri că implementarea alternativă este destul de eficientă.

Comentarii

  • @PMF …sau ValueError sau demoni nazali. Deci, răspunsul este floor(log10(number || 1)) + 1 sau, mai explicit: (number == 0) ? 1 : (floor(log10(number)) + 1) –  > Por oi zburătoare..
  • de ce să nu folosim ceil() în loc de floor() + 1? –  > Por Josie Thompson.
  • @JosieThompson ceil(0) = 0 în timp ce floor(0)+1 = 1. –  > Por Martin Beckett.
  • Am creat un mic script în OCaml pentru a testa diferite metode (șir de caractere, recursivitate, buclă, jurnal) și a reieșit că log este cea mai rapidă. În ordine de la cel mai rapid la cel mai lent: (1) log, (2) string, (3) recursion, (4) loop. –  > Por gogoașă.
BlairHippo

Nu știu, iar răspunsul ar putea fi diferit în funcție de modul în care este implementat limbajul tău individual.

Așa că, testați-l la stres! Implementați toate cele trei soluții. Rulați-le pe 1 până la 1.000.000 (sau pe un alt set imens de numere care să fie reprezentativ pentru numerele pe care soluția va fi rulată) și cronometrați cât timp durează fiecare dintre ele.

Puneți soluțiile una împotriva celeilalte și lăsați-le să se lupte între ele. Ca niște gladiatori intelectuali. Trei algoritmi se înscriu! Un algoritm pleacă!

Valera Kolupaev

Acest algoritm ar putea fi bun și el, presupunând că:

  • Numărul este întreg și codificat binar (<< operația este ieftină).
  • Nu cunoaștem limitele numerelor

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

Acest algoritm, ar trebui să aibă o viteză comparabilă cu bucla for-loop (2) prevăzută, dar un pic mai rapidă datorită (2 bit-shifts, adăugare și scădere, în loc de divizare).

În ceea ce privește algoritmul Log10, acesta vă va oferi doar un răspuns aproximativ (apropiat de cel real, dar totuși), deoarece formula analitică pentru calcularea funcției Log are o buclă infinită și nu poate fi calculată cu precizie. Wiki.

Comentarii

  • Aici avem nevoie doar de partea întreagă a logaritmului, ceea ce face ca „bucla infinită” să fie nulă. –  > Por Paŭlo Ebermann.
  • Da, aveți dreptate, face calculul finit, dar totuși pare costisitor pentru numere mici. –  > Por Valera Kolupaev.
  • Nu ar trebui să fie așa: tmp += (tmp << 3) + (tmp << 1); ? –  > Por wildplasser.
  • De fapt, acest lucru nu se calculează corect dacă numărul de intrare este divizibil cu 10. Pentru a remedia problema, ar trebui să incrementați lungimea cifrei cu 1 dacă numărul este divizibil cu 10. – user3704639
  • Dacă cineva se întreabă în legătură cu << shifts, acesta este similar cu tmp = tmp * 8 + tmp * 2. Înmulțirea obișnuia să coste de câteva ori mai mult decât operațiile de bază, dar pe procesoarele moderne poate dura aproximativ același timp, deci tmp *= 10; s-ar putea să fie un pic mai rapidă lemire.me/blog/2010/07/19/… –  > Por Slai.
daniel.sedlacek

Condiții de testare

  • Sistem numeric zecimal
  • Numere întregi pozitive
  • Până la 10 cifre
  • Limba: ActionScript 3

Rezultate

cifre: [1,10],

nr. de execuții: 1,000,000

random sample: 8777509,40442298,477894,329950,513,91751410,313,3159,131309,2

rezultat: 7,8,6,6,6,3,8,8,3,4,6,1

CONVERSIE ÎN STRING: 724ms

CALCUL LOGARITMIC: 349ms

ITERAȚIE DIV 10: 229ms

CONDIȚIONARE MANUALĂ: 136ms

Notă: Autorul se abține să facă concluzii pentru numere cu mai mult de 10 cifre.


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('
CONVERSION 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('
LOGARITMIC 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('
DIV 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('
MANUAL CONDITIONING: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));
        }
    }
}

Comentarii

  • Vă mulțumim pentru efectuarea tuturor acestor teste; a fost foarte util! Bineînțeles că viteza exactă va varia în funcție de medii, dar aceasta este o imagine de ansamblu excelentă a ceea ce trebuie să ne așteptăm și cum să procedăm. –  > Por Beejor.
  • Îți lipsește opțiunea de a calcula cifrele folosind o buclă de schimburi de biți în loc de diviziune. – user3704639
FrustratedWithFormsDesigner
  • conversia în șir de caractere: Aceasta va trebui să parcurgă fiecare cifră, să găsească caracterul care se potrivește cu cifra curentă, să adauge un caracter la o colecție de caractere. Apoi să obțină lungimea obiectului String rezultat. Se va executa în O(n) pentru n=#digite.

  • for-loop: va efectua două operații matematice: împărțirea numărului la 10 și creșterea unui contor. Se va executa în O(n) pentru n=#digite.

  • logaritmic: Va apela log10 și floor și va adăuga 1. Pare a fi O(1), dar nu sunt sigur cât de rapide sunt funcțiile log10 sau floor. Cunoștințele mele despre acest tip de lucruri s-au atrofiat din cauza lipsei de utilizare, așa că ar putea exista ascunse complexitate ascunsă în aceste funcții.

Deci, cred că totul se reduce la întrebarea: este mai rapidă căutarea de corespondențe de cifre decât mai multe operații matematice sau orice altceva se întâmplă în log10? Răspunsul va varia probabil. Ar putea exista platforme unde cartografierea caracterelor este mai rapidă, iar altele unde efectuarea calculelor este mai rapidă. De asemenea, trebuie să rețineți că prima metodă va crea un nou obiect String care există doar pentru a obține lungimea. Aceasta va utiliza probabil mai multă memorie decât celelalte două metode, dar acest lucru poate să conteze sau nu.

Comentarii

  • Conversia în șir de caractere va face, de asemenea, probabil, ceva asemănător celei de-a doua bucle în mod intern. –  > Por Paŭlo Ebermann.
user240515

Evident, puteți elimina metoda 1 din concurs, deoarece algoritmul atoi/toString pe care îl folosește ar fi similar cu metoda 2.

Viteza metodei 3 depinde de faptul dacă codul este compilat pentru un sistem al cărui set de instrucțiuni include baza 10 de logaritmi.

Joey Adams

Folosiți cea mai simplă soluție în orice limbaj de programare pe care îl folosiți. Nu mă pot gândi la un caz în care numărarea cifrelor într-un număr întreg ar fi gâtul de gâtul de la capătul de gât în orice program (util).

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 (netestat):

length = Len(str(123456789)) - 1

Comentarii

  • Dacă numărul de cifre este cunoscut și relativ mic, atunci nu pot decât să fiu de acord cu dumneavoastră. –  > Por daniel.sedlacek.
  • R: nchar(123456789) –  > Por oi zburătoare.
Brian Minton

Pentru numere întregi foarte mari, metoda log este mult mai rapidă. De exemplu, cu un număr de 2491327 cifre (al 11920928-lea număr Fibonacci, dacă vă interesează), Python are nevoie de câteva minute pentru a executa algoritmul de împărțire la 10 și de milisecunde pentru a executa 1+floor(log(n,10)).

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

Comentarii

  • vrei să spui int(math.floor(math.log10(n or 1))) + 1, ca log10(0) ridică ValueError și ceil(log10(1)), ceil(log10(10)), ... este 0, 1, ... în timp ce floor(...) + 1 este valoarea corectă. –  > Por oaie zburătoare.
  • Nu funcționează pentru pentru 999999999999999999999 (15 cifre), returnează 16 –  > Por PADYMKO.
Robbie Hatley

În ceea ce privește cele trei metode pe care le propuneți pentru „determinarea numărului de cifre necesare pentru a reprezenta un anumit număr într-o anumită bază”, nu-mi place niciuna dintre ele, de fapt; prefer în schimb metoda pe care o prezint mai jos.

Referitor la metoda dvs. nr. 1 (șiruri): Orice lucru care implică conversia între șiruri de caractere și numere este de obicei foarte lent.

Referitor la metoda dvs. nr. 2 (temp/=10): Aceasta este fatalmente greșită deoarece presupune că x/10 înseamnă întotdeauna „x împărțit la 10”. Dar în multe limbaje de programare (de exemplu: C, C++), dacă „x” este un tip întreg, atunci „x/10” înseamnă „împărțire întregi”, care nu este același lucru cu împărțirea în virgulă mobilă, și introduce erori de rotunjire la fiecare iterație, iar acestea se acumulează într-o formulă recursivă, cum este cea pe care o folosește soluția dvs. nr. 2.

În ceea ce privește metoda dvs. nr. 3 (jurnale): este o eroare pentru numere mari (cel puțin în C și probabil și în alte limbaje), deoarece tipurile de date în virgulă mobilă tind să nu fie la fel de precise ca și cele întregi pe 64 de biți.

Prin urmare, nu-mi plac toate cele 3 metode respective: #1 funcționează, dar este lent, #2 este defectă, iar #3 este eronată pentru numere mari. În schimb, prefer această metodă, care funcționează pentru numere de la 0 până la aproximativ 18,44 chintilioane:

unsigned NumberOfDigits (uint64_t Number, unsigned Base)
{
   unsigned Digits = 1;
   uint64_t Power  = 1;
   while ( Number / Power >=  Base )
   {
      ++Digits;
      Power *= Base;
   }
   return Digits;
}

Gary Willoughby

Păstrați-o simplă:

long long int a = 223452355415634664;

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

printf("%d", x);

utilizator necunoscut

Puteți folosi o soluție recursivă în loc de o buclă, dar cumva similară:

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

digits (8345012978643L)

Cu numere lungi, imaginea s-ar putea schimba – măsurați numerele mici și lungi în mod independent în raport cu diferiți algoritmi și alegeți-l pe cel potrivit, în funcție de datele de intrare tipice. 🙂

Bineînțeles că nimic nu bate un comutator:

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
}

cu excepția unui simplu tablou:

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

Unii oameni vă vor spune să optimizați dimensiunea codului, dar știți, optimizarea prematură …

Ivan Smetanin

Aici este măsurarea în Swift 4.

Codul algoritmilor:

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
    }

}

Cod de măsurare:

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))")

Ieșire

timeInterval0: 1.92149806022644

timeInterval1: 0.557608008384705

timeInterval2: 2.83262193202972

Pe această bază de măsurare, conversia String este cea mai bună opțiune pentru limbajul Swift.

twodayslate

Am fost curios după ce am văzut rezultatele lui @daniel.sedlacek, așa că am făcut câteva teste folosind Swift pentru numere care au mai mult de 10 cifre. Am rulat următorul script în locul de joacă.

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)

Rezultate pentru 80 de elemente

0.105069875717163 for floor(log10(x))
0.867973804473877 pentru div 10 iterații

Tom

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

Unde x este o baza și n este numărul.

Comentarii

  • Am folosit această formulă în experimentul meu „Math.floor( Math.log( numbers[i] ) / Math.log(10) ) + 1” și au existat metode mult mai rapide. –  > Por daniel.sedlacek.
NomenNescio
let numDigits num =
    let num = abs(num)
    let rec numDigitsInner num =
        match num with
        | num when num < 10 -> 1
        | _ -> 1 + numDigitsInner (num / 10)
    numDigitsInner num

Versiunea F#, fără casting la un șir de caractere.