streamalism.org

1. Uvod

U ovom ćemo brzom vodiču istražiti različiti načini dobivanja broja znamenki u Cijeli broj na Javi.

Također ćemo analizirati te različite metode i shvatit ćemo koji bi algoritam najbolje odgovarao našoj situaciji.

2. Broj znamenki u Cijeli broj

Za ovdje raspravljene metode razmatramo samo pozitivne cijele brojeve. Ako očekujemo bilo kakav negativan input, onda ga prvo možemo iskoristiti Math.abs (broj) prije korištenja bilo koje od ovih metoda.

2.1. Niz-Otvoreno rješenje

Možda najlakši način za dobivanje broja znamenki u Cijeli broj je pretvaranjem u Niz, i pozivanje duljina () metoda. To će vratiti duljinu Niz prikaz našeg broja:

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

Ali, ovo može biti neoptimalni pristup, jer ova izjava uključuje dodjelu memorije za a Niz, za svaku ocjenu. JVM prvo mora raščlaniti naš broj i kopirati njegove znamenke u zaseban Niz i izvoditi niz različitih operacija (poput zadržavanja privremenih kopija, obrade Unicode pretvorbi itd.).

Ako imamo samo nekoliko brojeva za procjenu, onda možemo jasno ići s ovim rješenjem - jer će razlika između ovog i bilo kojeg drugog pristupa biti zanemariva čak i za velike brojeve.

2.2. Logaritamski pristup

Za brojeve predstavljene u decimalnom obliku, ako uzmemo njihov zapis u bazu 10 i zaokružimo ga, dobit ćemo broj znamenki u tom broju:

int dužina = (int) (Math.log10 (broj) + 1);

Imajte na umu da zapisnik₁₀0 bilo kojeg broja nije definirano. Dakle, ako očekujemo bilo koji ulaz s vrijednošću 0, onda možemo staviti provjeru i za to.

Logaritamski pristup je znatno brži od Niz zasnovan na pristupu jer ne mora proći kroz proces pretvorbe podataka. To uključuje samo jednostavan, izračun bez dodatnih inicijalizacija ili petlji objekta.

2.3. Ponovljeno množenje

U ovoj ćemo metodi uzeti privremenu varijablu (inicijaliziranu na 1) i kontinuirano ćemo je množiti s 10 dok ne postane veća od našeg broja. Tijekom ovog postupka koristit ćemo i duljina varijabla koja će pratiti trajanje duljine broja:

dužina int = 0; duga temp = 1; while (temp <= broj) {length ++; temp * = 10; } dužina vraćanja;

U ovom kodu redak temp * = 10 isto je što i pisanje temp = (temp << 3) + (temp << 1). Budući da je množenje obično skuplji rad na nekim procesorima u usporedbi s operatorima pomaka, potonji mogu biti malo učinkovitiji.

2.4. Podjela s ovlastima dvoje

Ako znamo za raspon našeg broja, tada možemo koristiti varijaciju koja će dodatno smanjiti naše usporedbe. Ova metoda dijeli broj sa potencijama dvoje (npr. 1, 2, 4, 8 itd.):

Ova metoda dijeli broj sa potencijama dvoje (npr. 1, 2, 4, 8 itd.):

dužina int = 1; if (broj> = 100000000) {duljina + = 8; broj / = 100000000; } if (broj> = 10000) {duljina + = 4; broj / = 10000; } if (broj> = 100) {duljina + = 2; broj / = 100; } if (broj> = 10) {duljina + = 1; } dužina vraćanja;

To iskorištava činjenicu da bilo koji broj može biti predstavljen dodavanjem potencijala 2. Na primjer, 15 može biti predstavljeno kao 8 + 4 + 2 + 1, što su sve potencije broja 2.

Za 15-znamenkasti broj radili bismo 15 usporedbi u našem prethodnom pristupu, koje smo ovom metodom sveli na samo 4.

2.5. Podijeli i osvoji

Ovo je možda najdeblji pristup u usporedbi sa svim ostalim ovdje opisanim, ali suvišno je reći, ovaj je najbrži jer ne vršimo bilo koju vrstu pretvorbe, množenja, zbrajanja ili inicijalizacije objekta.

Odgovor dobivamo u samo tri ili četiri jednostavna ako izjave:

if (broj <100000) {if (broj <100) {if (broj <10) {return 1; } else {povratak 2; }} else {if (broj <1000) {return 3; } else {if (broj <10000) {return 4; } else {povratak 5; }}}} else {if (broj <10000000) {if (broj <1000000) {return 6; } else {povratak 7; }} else {if (broj <100000000) {return 8; } else {if (broj <1000000000) {return 9; } else {povratak 10; }}}}

Slično prethodnom pristupu, ovu metodu možemo koristiti samo ako znamo za raspon našeg broja.

3. Benchmarking

Sad kad dobro razumijemo potencijalna rješenja, napravimo nekoliko jednostavnih referentnih analiza svih naših metoda pomoću Java Microbenchmark Harness (JMH).

Sljedeća tablica prikazuje prosječno vrijeme obrade svake operacije (u nanosekundama):

Benchmarking.stringBasedSolution prosj. 200 32,736 ± 0,589 ns / op Benchmarking.logarithmicApproach avg 200 26,123 ± 0,064 ns / op Benchmarking.pepeatedMultiplication avgt 200 7,494 ± 0,207 ns / op Benchmarking.divideAndConquer prosjek 200 0,956 ± 0,011 ns / op

The NizRješenje koje je najjednostavnije ujedno je i najskuplja operacija - jer je ovo jedino koje zahtijeva pretvorbu podataka i inicijalizaciju novih objekata.

Logaritamski pristup je znatno učinkovitiji u usporedbi s prethodnim rješenjem - jer ne uključuje pretvorbu podataka. I kao rješenje s jednom linijom, može biti dobra alternativa Niz-zasnovan pristup.

Ponovljeno množenje uključuje jednostavno množenje, proporcionalno duljini broja; na primjer, ako je broj dugačak petnaest znamenki, tada će ova metoda uključivati ​​petnaest množenja.

Međutim, već sljedeća metoda iskorištava činjenicu da svaki broj može biti predstavljen s dva stupnja (pristup sličan BCD-u) i smanjuje istu na 4 podjele, pa je čak i učinkovitija od prethodne.

Konačno, kao što možemo zaključiti, najučinkovitiji algoritam je opsežna implementacija Divide and Conquer - koji daje odgovor u samo tri ili četiri jednostavne izjave if. Možemo ga koristiti ako imamo velik skup brojeva koje moramo analizirati.

4. Zaključak

U ovom kratkom članku iznijeli smo neke od načina kako pronaći broj znamenki u Cijeli broj i usporedili smo učinkovitost svakog pristupa.

Kao i uvijek, cjelovit kod možete pronaći na GitHubu.