streamalism.org

1. Úvod

V tomto rýchlom výučbe to preskúmame rôzne spôsoby získania počtu číslic v Celé číslo v Jave.

Budeme tiež analyzovať tieto rôzne metódy a zistíme, ktorý algoritmus by sa do našej situácie najlepšie hodil.

2. Počet číslic v Celé číslo

Pre metódy tu diskutované, uvažujeme iba s kladnými celými číslami. Ak očakávame akýkoľvek negatívny vstup, potom môžeme najskôr využiť Math.abs (number) pred použitím ktorejkoľvek z týchto metód.

2.1. String-Based Solution

Možno najjednoduchší spôsob, ako získať počet číslic v Celé číslo je prevedením na Stringa volanie na číslo dĺžka () metóda. Týmto sa vráti dĺžka súboru String reprezentácia nášho čísla:

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

Môže to však byť neoptimálny prístup, pretože toto vyhlásenie zahŕňa alokáciu pamäte pre a Reťazec, pre každé hodnotenie. JVM musí najskôr analyzovať naše číslo a skopírovať jeho číslice do samostatného String a tiež vykonať množstvo rôznych operácií (napríklad uchovanie dočasných kópií, spracovanie prevodov Unicode atď.).

Ak máme na vyhodnotenie iba pár čísel, môžeme jednoznačne ísť s týmto riešením - pretože rozdiel medzi týmto a akýmkoľvek iným prístupom bude zanedbateľný aj pre veľké počty.

2.2. Logaritmický prístup

Pre čísla predstavované v desatinnej podobe, ak vezmeme ich prihlásenie v základni 10 a zaokrúhlime to hore, dostaneme počet číslic v tomto počte:

int dĺžka = (int) (Math.log10 (číslo) + 1);

Poznač si to log₁₀0 ľubovoľného počtu nie je definované. Takže ak očakávame akýkoľvek vstup s hodnotou 0, potom môžeme skontrolovať aj to.

Logaritmický prístup je podstatne rýchlejší ako String založený na prístupe, pretože nemusí prechádzať procesom akejkoľvek konverzie údajov. Zahŕňa to iba jednoduchý a priamy výpočet bez akejkoľvek ďalšej inicializácie objektu alebo cyklov.

2.3. Opakované násobenie

V tejto metóde vezmeme dočasnú premennú (inicializovanú na 1) a budeme ju neustále vynásobiť číslom 10, kým sa nezvýši na náš počet. Počas tohto procesu tiež použijeme a dĺžka premenná, ktorá bude sledovať dĺžku čísla:

int dĺžka = 0; dlhá teplota = 1; while (teplota <= číslo) {dĺžka ++; teplota * = 10; } dĺžka návratu;

V tomto kóde riadok teplota * = 10 je to isté ako písanie teplota = (teplota << 3) + (teplota << 1). Pretože násobenie je pre niektoré procesory zvyčajne nákladnejšia operácia v porovnaní s operátormi na zmeny, môžu byť operátory o niečo efektívnejšie.

2.4. Rozdelenie s mocami dvoch

Ak vieme o rozsahu nášho počtu, môžeme použiť variáciu, ktorá ešte viac zníži naše porovnania. Táto metóda vydelí počet mocninami dvoch (napr. 1, 2, 4, 8 atď.):

Táto metóda vydelí počet mocninami dvoch (napr. 1, 2, 4, 8 atď.):

int dĺžka = 1; if (number> = 100000000) {length + = 8; číslo / = 100000000; } if (počet> = 10 000) {dĺžka + = 4; číslo / = 10 000; } if (počet> = 100) {dĺžka + = 2; číslo / = 100; } if (počet> = 10) {dĺžka + = 1; } dĺžka návratu;

Využíva skutočnosť, že ľubovoľné číslo môže byť reprezentované pridaním právomocí 2. Napríklad 15 môže byť reprezentovaných ako 8 + 4 + 2 + 1, ktoré sú všetky mocninami 2.

Pre 15-miestne číslo by sme v našom predchádzajúcom prístupe robili 15 porovnaní, ktoré sme v tejto metóde znížili iba na 4.

2.5. Rozdeľ a panuj

Toto je možno najobjemnejší prístup v porovnaní so všetkými ostatnými tu opísanými, ale netreba dodávať, tento je najrýchlejší pretože nevykonávame žiadny typ konverzie, násobenia, sčítania alebo inicializácie objektu.

Odpoveď dostaneme iba v troch alebo štyroch jednoduchých ak Vyhlásenia:

if (number <100000) {if (number <100) {if (number <10) {return 1; } else {návrat 2; }} else {if (number <1000) {return 3; } else {if (number <10 000) {return 4; } else {návrat 5; }}}} else {if (number <10 000 000) {if (number <10 000 000) {return 6; } else {návrat 7; }} else {if (number <100000000) {return 8; } else {if (number <1000000000) {return 9; } else {return 10; }}}}

Podobne ako v predchádzajúcom prístupe, aj túto metódu môžeme použiť, iba ak vieme o rozsahu nášho čísla.

3. Benchmarking

Teraz, keď dobre rozumieme potenciálnym riešeniam, urobme teraz jednoduché porovnávanie všetkých našich metód pomocou Java Microbenchmark Harness (JMH).

Nasledujúca tabuľka zobrazuje priemerný čas spracovania každej operácie (v nanosekundách):

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.dividing Benchmarking.divideAndConquer priem. 200 0,956 ± 0,011 ns / op

The String- najjednoduchšie riešenie na báze je zároveň najnákladnejšou operáciou - pretože je jediné, ktoré si vyžaduje prevod údajov a inicializáciu nových objektov.

Logaritmický prístup je v porovnaní s predchádzajúcim riešením výrazne efektívnejší - nezahŕňa totiž žiadnu konverziu údajov. A keďže je to jednoriadkové riešenie, môže to byť dobrá alternatíva k Reťazec-založený prístup.

Opakované násobenie zahŕňa jednoduché násobenie, proporcionálne k dĺžke čísla; napríklad ak má číslo pätnásť číslic, potom táto metóda bude zahŕňať pätnásť násobení.

Hneď nasledujúca metóda však využíva skutočnosť, že každé číslo môže byť reprezentované mocninami dvoch (prístup podobný BCD), a redukuje rovnaké operácie na 4 divízie, takže je ešte efektívnejšia ako prvá.

Nakoniec, ako môžeme odvodiť, najefektívnejším algoritmom je podrobná implementácia Divide and Conquer - ktorý poskytuje odpoveď iba v troch alebo štyroch jednoduchých výrokoch typu if. Môžeme ho použiť, ak máme veľký súbor čísel, ktorý musíme analyzovať.

4. Záver

V tomto stručnom článku sme načrtli niektoré zo spôsobov, ako zistiť počet číslic v Celé číslo a porovnali sme efektívnosť každého prístupu.

A ako vždy, celý kód nájdete na GitHub.