Antall sifre i et heltall i Java

1. Introduksjon

I denne raske opplæringen vil vi utforske forskjellige måter å få antall sifre i et Heltall i Java.

Vi vil også analysere de forskjellige metodene og finne ut hvilken algoritme som passer best i vår situasjon.

2. Antall sifre i et Heltall

For metodene som er diskutert her, vurderer vi bare positive heltall. Hvis vi forventer noen negative innspill, kan vi først gjøre bruk av Math.abs (antall) før du bruker noen av disse metodene.

2.1. String-Basert løsning

Kanskje den enkleste måten å få antall sifre i et Heltall er ved å konvertere den til String, og kaller lengde() metode. Dette vil returnere lengden på String representasjon av vårt nummer:

int length = String.valueOf (number) .length ();

Men dette kan være en suboptimal tilnærming, da denne påstanden innebærer minnetildeling for en Streng, for hver evaluering. JVM må først analysere nummeret vårt og kopiere sifrene til et eget String og utføre en rekke forskjellige operasjoner også (som å holde midlertidige kopier, håndtere Unicode-konverteringer osv.).

Hvis vi bare har noen få tall å evaluere, så kan vi tydelig gå med denne løsningen - fordi forskjellen mellom denne og enhver annen tilnærming vil være neglisjert selv for store tall.

2.2. Logaritmisk tilnærming

For tallene som er representert i desimalform, hvis vi tar loggen deres i base 10 og avrunder den opp, så får vi antall sifre i det tallet:

int lengde = (int) (Math.log10 (nummer) + 1);

Noter det Logg100 av noe tall er ikke definert. Så hvis vi forventer noen innspill med verdi 0, så kan vi også sjekke det.

Den logaritmiske tilnærmingen er betydelig raskere enn String basert tilnærming da den ikke trenger å gå gjennom prosessen med datakonvertering. Det innebærer bare en enkel, grei beregning uten ekstra objektinitialisering eller løkker.

2.3. Gjentatt multiplikasjon

I denne metoden tar vi en midlertidig variabel (initialisert til 1) og multipliserer den kontinuerlig med 10 til den blir større enn vårt antall. I løpet av denne prosessen vil vi også bruke en lengde variabel som vil holde oversikt over tallets lengde:

int lengde = 0; lang temp = 1; mens (temp <= nummer) {lengde ++; temp * = 10; } returlengde;

I denne koden, linjen temp * = 10 er det samme som å skrive temp = (temp << 3) + (temp << 1). Siden multiplikasjon vanligvis er dyrere å bruke på noen prosessorer sammenlignet med skiftoperatører, kan sistnevnte være litt mer effektive.

2.4. Å dele med makter av to

Hvis vi vet om rekkevidden til tallet vårt, så kan vi bruke en variasjon som ytterligere vil redusere sammenligningene våre. Denne metoden deler tallet med krefter på to (f.eks. 1, 2, 4, 8 osv.):

Denne metoden deler tallet med krefter på to (f.eks. 1, 2, 4, 8 osv.):

int lengde = 1; hvis (nummer> = 100000000) {lengde + = 8; nummer / = 100000000; } hvis (tall> = 10000) {lengde + = 4; antall / = 10000; } hvis (tall> = 100) {lengde + = 2; antall / = 100; } hvis (nummer> = 10) {lengde + = 1; } returlengde;

Det utnytter det faktum at et hvilket som helst tall kan representeres ved å legge til krefter på 2. For eksempel kan 15 bli representert som 8 + 4 + 2 + 1, som alle er krefter på 2.

For et 15-sifret nummer, ville vi gjort 15 sammenligninger i vår forrige tilnærming, som vi har redusert til bare 4 i denne metoden.

2.5. Splitt og hersk

Dette er kanskje den største tilnærmingen sammenlignet med alt annet beskrevet her, men det er unødvendig å si, denne er den raskeste fordi vi ikke utfører noen form for konvertering, multiplikasjon, tillegg eller initialisering av objekt.

Vi får svaret vårt på bare tre eller fire enkle hvis uttalelser:

if (number <100000) {if (number <100) {if (number <10) {return 1; } annet {retur 2; }} annet {if (nummer <1000) {retur 3; } annet {if (nummer <10000) {retur 4; } annet {retur 5; }}}} annet {if (nummer <10000000) {if (nummer <1000000) {retur 6; } annet {retur 7; }} annet {if (nummer <100000000) {retur 8; } annet {if (nummer <1000000000) {retur 9; } annet {retur 10; }}}}

I likhet med forrige tilnærming kan vi bare bruke denne metoden hvis vi vet om rekkevidden til nummeret vårt.

3. Benchmarking

Nå som vi har god forståelse av de potensielle løsningene, la oss nå gjøre noen enkle benchmarking av alle metodene våre ved hjelp av Java Microbenchmark Harness (JMH).

Følgende tabell viser gjennomsnittlig behandlingstid for hver operasjon (i nanosekunder):

Benchmark Mode Cnt Score Error Units Benchmarking.stringBasedSolution avgt 200 32.736 ± 0.589 ns / op Benchmarking.logarithmicApproach avgt 200 26.123 ± 0.064 ns / op Benchmarking.repeatedMultiplication avgt 200 7.494 ± 0.207 ns / op Benchmarking.dividingWithPowersOf Benchmarking.divideAndConquer avgt 200 0,956 ± 0,011 ns / op

De String-basert løsning, som er den enkleste, er også den mest kostbare operasjonen - da dette er den eneste som krever datakonvertering og initialisering av nye objekter.

Den logaritmiske tilnærmingen er betydelig mer effektiv, sammenlignet med den forrige løsningen - siden den ikke innebærer noen datakonvertering. Og som en enkeltlinjeløsning, kan det være et godt alternativ til Streng-basert tilnærming.

Gjentatt multiplikasjon innebærer enkel multiplikasjon, proporsjonalt med talllengden; for eksempel, hvis et tall er femten sifre langt, vil denne metoden innebære femten multiplikasjoner.

Den neste metoden utnytter imidlertid det faktum at hvert tall kan representeres av krefter av to (tilnærmingen som ligner på BCD), og reduserer det samme til fire divisjonsoperasjoner, så det er enda mer effektivt enn det tidligere.

Til slutt, som vi kan utlede, den mest effektive algoritmen er den detaljerte Divide and Conquer implementeringen - som leverer svaret i bare tre eller fire enkle hvis uttalelser. Vi kan bruke det hvis vi har et stort datasett med tall vi trenger å analysere.

4. Konklusjon

I denne korte artikkelen skisserte vi noen av måtene å finne antall sifre i et Heltall og vi sammenlignet effektiviteten til hver tilnærming.

Og som alltid kan du finne den fullstendige koden på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found