streamalism.org

1. Bemutatkozás

Ebben a gyors bemutatóban felfedezzük a számjegyek számának lekérdezésének különféle módjai Egész szám Java-ban.

Elemezzük ezeket a különböző módszereket is, és kitaláljuk, melyik algoritmus illene a legjobban a helyzetünkhöz.

2. Számjegyek száma egy Egész szám

Az itt tárgyalt módszerek esetében csak pozitív egész számokat veszünk figyelembe. Ha bármilyen negatív bemenetre számítunk, akkor először felhasználhatjuk Math.abs (szám) mielőtt e módszerek bármelyikét alkalmazná.

2.1. Húr-Alapú megoldás

Talán a legegyszerűbb módja annak, hogy megszerezzük a számjegyek számát Egész szám azáltal, hogy átalakítja Húr, és felhívja a hossz() módszer. Ez visszaadja a Húr számunk ábrázolása:

int hossz = String.valueOf (szám) .length ();

De ez lehet egy optimálisnál alacsonyabb megközelítés, mivel ez az állítás magában foglalja a Karakterlánc, minden értékeléshez. A JVM-nek először elemeznie kell a számunkat, és külön kell másolnia a számjegyeit Húr és végezzen számos különféle műveletet is (például ideiglenes másolatok megőrzése, Unicode-konverziók kezelése stb.).

Ha csak néhány számot kell értékelnünk, akkor egyértelműen választhatunk ezzel a megoldással - mert a különbség ennek és bármely más megközelítésnek még nagy számok esetén is elhanyagolható lesz.

2.2. Logaritmikus megközelítés

A tizedes alakban ábrázolt számok esetében, ha a naplójukat a 10 alapba vesszük, és felfelé kerekítjük, akkor megkapjuk az ebben a számban lévő számjegyek számát:

int hossza = (int) (Math.log10 (szám) + 1);

Vegye figyelembe, hogy napló₁₀0 bármelyik szám nincs meghatározva. Tehát, ha bármilyen értékű bevitelt várunk 0, akkor ezt is ellenőrizhetjük.

A logaritmikus megközelítés lényegesen gyorsabb, mint Húr alapú megközelítés, mivel ennek nem kell semmilyen adatkonverziót végigvinnie. Csak egy egyszerű, egyértelmű számítást igényel, objektum inicializálás és hurkok nélkül.

2.3. Ismételt szorzás

Ebben a módszerben ideiglenes változót veszünk fel (inicializálva 1-re), és folyamatosan megszorozzuk 10-szel, amíg nagyobb lesz a számunkra. E folyamat során a hossz változó, amely nyomon követi a szám hosszát:

int hossza = 0; hosszú hőmérséklet = 1; while (temp <= szám) {hossz ++; hőmérséklet * = 10; } visszatérési hossz;

Ebben a kódban a sor hőmérséklet * = 10 ugyanaz, mint az írás temp = (temp << 3) + (temp << 1). Mivel a szorzás általában költségesebb művelet egyes processzorokon, összehasonlítva a váltó operátorokkal, az utóbbi kissé hatékonyabb lehet.

2.4. Osztás kettő hatalmával

Ha tudunk a számunk tartományáról, akkor használhatunk olyan variációt, amely tovább csökkenti az összehasonlításokat. Ez a módszer elosztja a számot kettő hatványával (például 1, 2, 4, 8 stb.):

Ez a módszer kettő (például 1, 2, 4, 8 stb.) Hatványaival osztja el a számot:

int hossza = 1; if (szám> = 100000000) {hossz + = 8; szám / = 100000000; } if (szám> = 10000) {hossz + = 4; szám / = 10000; } if (szám> = 100) {hossz + = 2; szám / = 100; } if (szám> = 10) {hossz + = 1; } visszatérési hossz;

Kihasználja azt a tényt, hogy tetszőleges szám képviselhető a 2-es hatványok összeadásával. Például a 15-et 8 + 4 + 2 + 1-ként lehet ábrázolni, amelyek mindegyike a 2-es hatványa.

15 számjegyű szám esetén 15 összehasonlítást végeznénk az előző megközelítésünkben, amelyet ebben a módszerben csak 4-re csökkentettünk.

2.5. Oszd meg és uralkodj

Ez talán a legnehezebb megközelítés összehasonlítva az itt leírtakkal, de mondanom sem kell, ez a leggyorsabb mert semmiféle átalakítást, szorzást, összeadást vagy objektum inicializálást nem hajtunk végre.

Csak három-négy egyszerű válaszban kapjuk meg a választ ha nyilatkozatok:

if (szám <100000) {if (szám <100) {if (szám <10) {visszatér 1; } else {return 2; }} else {if (szám <1000) {return 3; } else {if (szám <10000) {return 4; } else {return 5; }}}} else {if (szám <10000000) {if (szám <1000000) {return 6; } else {return 7; }} else {if (szám <100000000) {return 8; } else {if (szám <1000000000) {return 9; } else {return 10; }}}}

Az előző megközelítéshez hasonlóan ezt a módszert is csak akkor használhatjuk, ha tudunk a számunk tartományáról.

3. Benchmarking

Most, hogy jól megértettük a lehetséges megoldásokat, végezzünk néhány egyszerű összehasonlítást minden módszerünkkel a Java Microbenchmark Harness (JMH) segítségével.

Az alábbi táblázat az egyes műveletek átlagos feldolgozási idejét mutatja (nanoszekundumban):

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

A Húr-alapú megoldás, amely a legegyszerűbb, egyben a legköltségesebb művelet is - mivel csak ez igényel adatkonvertálást és új objektumok inicializálását.

A logaritmikus megközelítés lényegesen hatékonyabb, mint az előző megoldás - mivel nem jár adatkonvertálással. És mivel egysoros megoldás, jó alternatíva lehet Húr-alapú megközelítés.

Az ismételt szorzás egyszerű szorzást foglal magában, a szám hosszával arányosan; Például, ha egy szám tizenöt számjegy hosszú, akkor ez a módszer tizenöt szorzást tartalmaz.

A legközelebbi módszer azonban kihasználja azt a tényt, hogy minden számot kettő hatványa képviselhet (a megközelítés hasonló a BCD-hez), és ugyanezt 4 osztási műveletre redukálja, így még hatékonyabb, mint az előbbi.

Végül, amint arra következtethetünk, a leghatékonyabb algoritmus a sokoldalú Divide and Conquer megvalósítás - amely mindössze három vagy négy egyszerű if állítással adja meg a választ. Akkor használhatjuk, ha nagy számadatkészlettel rendelkezünk, amelyet elemeznünk kell.

4. Következtetés

Ebben a rövid cikkben felvázoltunk néhány módot az an számjegyeinek számának megkeresésére Egész szám és összehasonlítottuk az egyes megközelítések hatékonyságát.

És mint mindig, a teljes kódot a GitHubon találja meg.