streamalism.org

1. Inleiding

In deze korte tutorial zullen we verkennen verschillende manieren om het aantal cijfers in een Geheel getal in Java.

We analyseren ook die verschillende methoden en kijken welk algoritme het beste in onze situatie past.

2. Aantal cijfers in een Geheel getal

Voor de hier besproken methoden beschouwen we alleen positieve gehele getallen. Als we negatieve input verwachten, kunnen we daar eerst gebruik van maken Math.abs (getal) voordat u een van deze methoden gebruikt.

2.1. Draad-Gebaseerde oplossing

Misschien wel de gemakkelijkste manier om het aantal cijfers in een Geheel getal is door het te converteren naar Draad, en het aanroepen van de lengte() methode. Dit retourneert de lengte van de Draad vertegenwoordiging van ons nummer:

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

Maar dit kan een suboptimale benadering zijn, aangezien deze verklaring geheugentoewijzing voor een String, voor elke evaluatie. De JVM moet eerst ons nummer ontleden en de cijfers naar een apart nummer kopiëren Draad en voer ook een aantal verschillende bewerkingen uit (zoals het bewaren van tijdelijke kopieën, het afhandelen van Unicode-conversies, enz.).

Als we maar een paar cijfers hebben om te evalueren, dan kunnen we duidelijk voor deze oplossing gaan - omdat het verschil tussen deze en elke andere benadering zelfs voor grote aantallen te verwaarlozen zal zijn.

2.2. Logaritmische benadering

Voor de getallen weergegeven in decimale vorm, als we hun log in basis 10 nemen en het naar boven afronden, krijgen we het aantal cijfers in dat nummer:

int lengte = (int) (Math.log10 (getal) + 1);

Let daar op logboek₁₀0 van een willekeurig aantal is niet gedefinieerd. Dus als we enige input met waarde verwachten 0, dan kunnen we dat ook controleren.

De logaritmische benadering is aanzienlijk sneller dan Draad gebaseerde aanpak omdat het niet door het proces van enige dataconversie hoeft te gaan. Het gaat gewoon om een ​​eenvoudige, ongecompliceerde berekening zonder enige extra objectinitialisatie of lussen.

2.3. Herhaalde vermenigvuldiging

Bij deze methode nemen we een tijdelijke variabele (geïnitialiseerd op 1) en vermenigvuldigen we deze continu met 10 totdat deze groter wordt dan ons getal. Tijdens dit proces gebruiken we ook een lengte variabele die de lengte van het nummer bijhoudt:

int lengte = 0; lange temperatuur = 1; while (temp <= nummer) {lengte ++; temp * = 10; } retourlengte;

In deze code staat de regel temp * = 10 is hetzelfde als schrijven temp = (temp << 3) + (temp << 1). Aangezien vermenigvuldiging meestal duurder is op sommige processors in vergelijking met shift-operators, kan de laatste iets efficiënter zijn.

2.4. Delen met machten van twee

Als we het bereik van ons nummer kennen, kunnen we een variatie gebruiken die onze vergelijkingen verder zal verkleinen. Deze methode deelt het getal door machten van twee (bijvoorbeeld 1, 2, 4, 8 etc.):

Deze methode deelt het getal door machten van twee (bijvoorbeeld 1, 2, 4, 8 etc.):

int lengte = 1; if (getal> = 100000000) {lengte + = 8; aantal / = 100000000; } if (getal> = 10000) {lengte + = 4; aantal / = 10000; } if (getal> = 100) {lengte + = 2; aantal / = 100; } if (getal> = 10) {lengte + = 1; } retour lengte;

Het maakt gebruik van het feit dat elk getal kan worden weergegeven door de toevoeging van machten van 2. 15 kan bijvoorbeeld worden weergegeven als 8 + 4 + 2 + 1, die allemaal machten van 2 zijn.

Voor een getal van 15 cijfers zouden we 15 vergelijkingen maken in onze vorige benadering, die we in deze methode hebben teruggebracht tot slechts 4.

2.5. Verdeel en heers

Dit is misschien de meest omvangrijke benadering in vergelijking met alle andere die hier worden beschreven, maar het is onnodig te zeggen, deze is de snelste omdat we geen enkele vorm van conversie, vermenigvuldiging, optelling of objectinitialisatie uitvoeren.

We krijgen ons antwoord in slechts drie of vier simpele als uitspraken:

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

Net als bij de vorige benadering, kunnen we deze methode alleen gebruiken als we het bereik van ons nummer kennen.

3. Benchmarking

Nu we een goed begrip hebben van de mogelijke oplossingen, gaan we nu al onze methoden eenvoudig benchmarken met behulp van de Java Microbenchmark Harness (JMH).

De volgende tabel toont de gemiddelde verwerkingstijd van elke bewerking (in nanoseconden):

Benchmarkmodus Cnt Score Fout Eenheden Benchmarking.stringBasedSolution gem. 200 32.736 ± 0.589 ns / op Benchmarking.logarithmicApproach gemiddelde 200 26.123 ± 0.064 ns / op Benchmarking.repeatedMultiplicatie gemiddelde 200 7.494 ± 0,207 ns / op Benchmarking.dividingWithPowers Benchmarking.divideAndConquer gem. 200 0,956 ± 0,011 ns / op

De Draad-gebaseerde oplossing, die de eenvoudigste is, is ook de duurste operatie - aangezien dit de enige is die dataconversie en initialisatie van nieuwe objecten vereist.

De logaritmische benadering is aanzienlijk efficiënter in vergelijking met de vorige oplossing, aangezien er geen dataconversie nodig is. En omdat het een oplossing met één lijn is, kan het een goed alternatief zijn voor Draad-gebaseerde aanpak.

Herhaalde vermenigvuldiging houdt een eenvoudige vermenigvuldiging in, evenredig met de lengte van het getal; Als een getal bijvoorbeeld vijftien cijfers lang is, omvat deze methode vijftien vermenigvuldigingen.

De volgende methode maakt echter gebruik van het feit dat elk getal kan worden weergegeven door machten van twee (de benadering vergelijkbaar met BCD), en herleidt hetzelfde tot 4 deelbewerkingen, dus het is zelfs efficiënter dan de eerste.

Eindelijk, zoals we kunnen concluderen, het meest efficiënte algoritme is de uitgebreide Divide and Conquer-implementatie - die het antwoord in slechts drie of vier eenvoudige if-uitspraken levert. We kunnen het gebruiken als we een grote dataset met getallen hebben die we moeten analyseren.

4. Conclusie

In dit korte artikel hebben we enkele manieren beschreven om het aantal cijfers in een Geheel getal en we vergeleken de efficiëntie van elke benadering.

En, zoals altijd, kun je de volledige code vinden op GitHub.