1. Въведение
В този бърз урок ще изследваме различни начини за получаване на броя на цифрите в цяло число в Java.
Също така ще анализираме тези различни методи и ще разберем кой алгоритъм би бил най-подходящ за нашата ситуация.
2. Брой цифри в цяло число
За дискутираните тук методи разглеждаме само положителни цели числа. Ако очакваме някакъв отрицателен вход, тогава първо можем да използваме Math.abs (число), преди да използваме някой от тези методи.
2.1. String базирани решения
Може би най-лесният начин да получите броя на цифрите в цяло число е като го преобразувате в String и извикате метода length () . Това ще върне дължината на низовото представяне на нашия номер:
int length = String.valueOf(number).length();Но това може да е неоптимален подход, тъй като това изявление включва разпределение на паметта за низ за всяка оценка . JVM първо трябва да анализира нашия номер и да копира цифрите му в отделен низ и да извърши редица различни операции (като запазване на временни копия, обработка на Unicode преобразувания и т.н.).
Ако имаме само няколко числа за оценка, тогава можем ясно да се съгласим с това решение - защото разликата между този и всеки друг подход ще бъде пренебрежима дори при големи числа.
2.2. Логаритмичен подход
За числата, представени в десетична форма, ако вземем техния дневник в база 10 и го закръглим, ще получим броя на цифрите в това число:
int length = (int) (Math.log10(number) + 1);Имайте предвид, че дневник 10 0 на всяко число не е дефиниран. Така че, ако очакваме някакъв вход със стойност 0 , тогава можем да поставим проверка и за това.
Логаритмичният подход е значително по-бърз от String- базиран подход, тъй като не е необходимо да преминава през процеса на преобразуване на данни. Той просто включва просто и просто изчисление без допълнителна инициализация на обект или цикли.
2.3. Повторно умножение
В този метод ще вземем временна променлива (инициализирана на 1) и непрекъснато ще я умножаваме с 10, докато тя стане по-голяма от нашето число. По време на този процес ще използваме и променлива за дължина, която ще проследява дължината на числото:
int length = 0; long temp = 1; while (temp <= number) { length++; temp *= 10; } return length;В този код редът temp * = 10 е същият като писането temp = (temp << 3) + (temp << 1) . Тъй като умножението обикновено е по-скъпа операция на някои процесори в сравнение с операторите на смяна, последните могат да бъдат малко по-ефективни.
2.4. Разделяне с правомощия на две
Ако знаем за обхвата на нашия номер, тогава можем да използваме вариация, която допълнително ще намали нашите сравнения. Този метод разделя броя на степен на две (например 1, 2, 4, 8 и т.н.):
Този метод разделя броя на степен на две (например 1, 2, 4, 8 и т.н.):
int length = 1; if (number >= 100000000) { length += 8; number /= 100000000; } if (number >= 10000) { length += 4; number /= 10000; } if (number >= 100) { length += 2; number /= 100; } if (number >= 10) { length += 1; } return length;Възползва се от факта, че всяко число може да бъде представено чрез добавяне на степени на 2. Например, 15 могат да бъдат представени като 8 + 4 + 2 + 1, които всички са степени на 2.
За 15-цифрено число бихме направили 15 сравнения в предишния ни подход, които сме намалили до само 4 при този метод.
2.5. Разделяй и владей
Това е може би най-обемният подход в сравнение с всички други, описани тук, но излишно е да казвам, че този е най-бързият, защото не извършваме никакъв вид преобразуване, умножение, добавяне или инициализация на обект.
Получаваме отговора си само с три или четири прости if твърдения:
if (number < 100000) { if (number < 100) { if (number < 10) { return 1; } else { return 2; } } else { if (number < 1000) { return 3; } else { if (number < 10000) { return 4; } else { return 5; } } } } else { if (number < 10000000) { if (number < 1000000) { return 6; } else { return 7; } } else { if (number < 100000000) { return 8; } else { if (number < 1000000000) { return 9; } else { return 10; } } } }Подобно на предишния подход, ние можем да използваме този метод само ако знаем за обхвата на нашия номер.
3. Бенчмаркинг
Сега, след като имаме добро разбиране на потенциалните решения, нека сега направим малко просто сравнение на всички наши методи, използвайки Java Microbenchmark Harness (JMH).
Следващата таблица показва средното време за обработка на всяка операция (в наносекунди):
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.dividingWithPowersOf2 avgt 200 1.264 ± 0.030 ns/op Benchmarking.divideAndConquer avgt 200 0.956 ± 0.011 ns/opРешението, базирано на String , което е най-простото, е и най-скъпата операция - тъй като това е единственото, което изисква преобразуване на данни и инициализация на нови обекти.
Логаритмичният подход е значително по-ефективен в сравнение с предишното решение - тъй като не включва преобразуване на данни. И като еднолинейно решение, може да бъде добра алтернатива на String- базиран подход.
Повторното умножение включва просто умножение, пропорционално на дължината на числото; например, ако числото е дълго петнадесет цифри, тогава този метод ще включва петнадесет умножения.
Обаче следващият метод се възползва от факта, че всяко число може да бъде представено чрез степени на две (подходът, подобен на BCD), и намалява същото до 4 операции за разделяне, така че е дори по-ефективно от първото.
И накрая, както можем да заключим, най-ефективният алгоритъм е многословната реализация Divide and Conquer - която предоставя отговора само с три или четири прости if твърдения. Можем да го използваме, ако разполагаме с голям набор от числа, които трябва да анализираме.
4. Заключение
В тази кратка статия посочихме някои от начините за намиране на броя на цифрите в цяло число и сравнихме ефективността на всеки подход.
И както винаги, можете да намерите пълния код на GitHub.