1. Длина строки
Довольно банальный способ это нахождение длины строки. Это не самый быстрый способ, но для очень простых задач подходит.
public int getCountsOfDigits(long number) {
return String.valueOf(Math.abs(number)).length();
}
2. Цикл с делением
Распространенный способ, скорость которого линейно зависит от длинный числа.
public int getCountsOfDigits(long number) {
int count = (number == 0) ? 1 : 0;
while (number != 0) {
count++;
number /= 10;
}
return count;
}
3. Десятичный логарифм и округление
Логарифм работает за константное время, преимущество которого на больших числах.
public static int getCountsOfDigits(long number) {
return(number == 0) ? 1 : (int) Math.ceil(Math.log10(Math.abs(number) + 0.5));
}
Можно использовать не только Math.ceil, это лишь один из вариантов использования логарифма.
4. Сравнение
Быстрый, но не практичный способ из-за количества кода только для int ушло 38 строк. Конечно найдутся умельцы которые смогут сделать красивее, и понятней. Не буду оставлять код для long, а оставлю для int, но думаю принцип ясен.
public static int getCountsOfDigits(int n) {
if (n < 100000) {
if (n < 100) {
if (n < 10) {
return 1;
} else {
return 2;
}
} else {
if (n < 1000) {
return 3;
} else {
if (n < 10000) {
return 4;
} else {
return 5;
}
}
}
} else {
if (n < 10000000) {
if (n < 1000000) {
return 6;
} else {
return 7;
}
} else {
if (n < 100000000) {
return 8;
} else {
if (n < 1000000000) {
return 9;
} else {
return 10;
}
}
}
}
}
Рейтинг выглядит так:
1. Сравнения (показывают лучший результат)
2. Логарифм
3. Деление
4. String (наихудший результат)
Комментарии (40)
lany
21.10.2015 13:18+6А для long — такой:
// Requires positive x static int stringSize(long x) { long p = 10; for (int i=1; i<19; i++) { if (x < p) return i; p = 10*p; } return 19; }
Заметьте, что можно изящно заменить деление умножением, которое работает быстрее.dkukushkin
21.10.2015 14:24-6заменить деление умножением, которое работает быстрее
Для целых чисел разве есть разница в скорости? Ведь и та и другая команда процессора выполняется за 1 такт.lany
21.10.2015 15:57+5Да, есть. В современных процессорах много чего выполняется быстрее, чем за такт.
dkukushkin
21.10.2015 19:45-1Если вы в курсе, то поясните насколько целочисленное (не с плавающей точкой) умножение выполняется быстрее деления.
На практике проверил несколько тестов — разницы не выявил.
В сети нашел данные: IDIV выполняется за время от от14 до 41 тактов, IMUL за время от от 9 до 41. Но это данные для Intel 80386. Но для этого процессора еще был математический сопроцессор (отдельно).
Интересуют не предрассудки, основаные на временах Intel 80386, а реальное положение дел.
qw1
24.10.2015 11:00На практике проверил несколько тестов — разницы не выявил.
Как проверяли? Деление на константу компиляторы заменяют умножением и сдвигом, habrahabr.ru/post/256827
barker
21.10.2015 19:44Ведь и та и другая команда процессора выполняется за 1 такт.
С чего вы взяли? В современных процессорах отношение «скорости» к кол-ву тактов, конечно, весьма условно, но само по себе деление выполняется за несколько десятков тактов, емнип.dkukushkin
21.10.2015 19:54С чего вы взяли?
На счет 1 такта, действительно ошибся.
себе деление выполняется за несколько десятков тактов
Точных данных для современных процессоров не нашел. Для 80386 от 14 до 41, и от 9 до 41 тактов на деление и умножение соответственно.
Думаю что разница если и есть, то на тестах она будет практически не заметна (для целых чисел).
По этому нужно делать выбор в пользу более понятного кода.michael_vostrikov
21.10.2015 20:52На 100 млн. раз разница более 1 секунды (C#, 3.00 ГГц). Для разовых действий роли не играет, но в движке базы данных или в обсчете статистики будет заметно.
// int a = 12345678, b = 10; // int count = 100000000; a / b: 00:00:01.7970217 a * b: 00:00:00.3328430 empty: 00:00:00.2414149
Скрытый текстnamespace test { class Program { static void Main(string[] args) { int a = 12345678, b = 10; int count = 100000000; Stopwatch sw; TimeSpan elapsed; sw = new Stopwatch(); sw.Start(); for (int i = 0; i < count; i++) { int x = a / b; } sw.Stop(); elapsed = sw.Elapsed; Console.WriteLine(elapsed.ToString()); sw = new Stopwatch(); sw.Start(); for (int i = 0; i < count; i++) { int x = a * b; } sw.Stop(); elapsed = sw.Elapsed; Console.WriteLine(elapsed.ToString()); sw = new Stopwatch(); sw.Start(); for (int i = 0; i < count; i++) {} sw.Stop(); elapsed = sw.Elapsed; Console.WriteLine(elapsed.ToString()); } } }dkukushkin
21.10.2015 21:17Ваш тест у меня дает такой результат:
a / b: 00:00:00.5373696
a * b: 00:00:00.4528938
00:00:00.4440999
Если поменять местами блок умножения и деления:
a * b: 00:00:00.4561308
a / b: 00:00:00.4959119
00:00:00.4439775
Добавил в код накопитель результата (для предотвращения оптимизации) и увеличил count до 1000000000.
Получил такие данные:
00:00:05.0382424
00:00:06.9657105
00:00:04.4456098
Получается умножение работает быстрее на 28%, т.е. не в разы. Процессор Core i3 2.5 ГГц.michael_vostrikov
22.10.2015 08:41Ок, мне стало интересно, и я решил вернуться к тому, с чего все началось — к определению длины числа. Способ с делением во всех случаях медленнее умножения. Число 12345678, 20 млн. раз.
Debug, оптимизация отключена a * b: 00:00:00.6641369 a / b: 00:00:02.0418462 empty: 00:00:00.0883897 Debug, оптимизация включена a * b: 00:00:00.2367661 a / b: 00:00:01.5960753 empty: 00:00:00.0660346 Release, оптимизация отключена a * b: 00:00:00.2784811 a / b: 00:00:01.8224548 empty: 00:00:00.0714300 Release, оптимизация включена a * b: 00:00:00.2012901 a / b: 00:00:01.5951311 empty: 00:00:00.0554228
Скрытый текстnamespace test { class Program { static uint getCount_Mul(uint x) { uint p = 10; uint count = 1; while (x >= p) { count++; p *= 10; } return count; } static uint getCount_Div(uint number) { uint count = (number == 0) ? (uint)1 : (uint)0; while (number > 0) { count++; number /= 10; } return count; } static void Main(string[] args) { uint a = 12345678; uint loopCount = 20000000; uint res = 0; Stopwatch sw; TimeSpan elapsed; Thread.Sleep(100); sw = new Stopwatch(); sw.Start(); for (int i = 0; i < loopCount; i++) { res += getCount_Mul(a); } sw.Stop(); elapsed = sw.Elapsed; Console.WriteLine("a * b: " + elapsed.ToString()); Thread.Sleep(100); sw = new Stopwatch(); sw.Start(); for (int i = 0; i < loopCount; i++) { res += getCount_Div(a); } sw.Stop(); elapsed = sw.Elapsed; Console.WriteLine("a / b: " + elapsed.ToString()); Thread.Sleep(100); sw = new Stopwatch(); sw.Start(); for (int i = 0; i < loopCount; i++) { } sw.Stop(); elapsed = sw.Elapsed; Console.WriteLine("empty: " + elapsed.ToString()); Console.WriteLine("res: " + res); } } }
monah_tuk
23.10.2015 03:20На Core i7 разница в 4.4 раза (кстати неплохо бы отношение выводить тоже):
a * b: 00:00:00.1260080 a / b: 00:00:00.5574522 empty: 00:00:00.0106549 res: 320000000
kzn
21.10.2015 13:29Использование логарифма — не самая лучшая идея с точки зрения производительности для такой задачи.
camelos
21.10.2015 14:14-1Если честно, не понял, почему длина строки — хуже всего :(
Zibx
21.10.2015 14:27По скорости.
camelos
21.10.2015 14:45-1Не «по чему», а «почему».
Почему операция «длина строки» занимает больше времени, чем например, деление или логарифм.
Про сравнение не спрашиваю. Ответ очевиден.
kolpeex
21.10.2015 14:59+1Это все то же деление только еще добавляется деление по модулю, чтобы цифру получить, и затем копирование цифры в строку.
camelos
21.10.2015 15:12-1Я был уверен, что после преобразования числа в строку будет хранится и длина строки — останется только получить это значение. Спасибо
zagayevskiy
21.10.2015 16:17+2Вы не поняли. Проблема не в том, чтобы получить длину строки — она-то хранится отдельно, числом. Проблема в преобразовании числа в строку. Его надо распарсить, выделить память под массив символов и тд. Основное время тратится именно на это.
camelos
21.10.2015 16:20Действительно не понял. Теперь всё точно встало на своим места. Спасибо, Денис, что разжевали.
lany
21.10.2015 17:14При этом для того, чтобы определить, сколько памяти выделить под массив символов, в самом начале вызывается один из методов, что я привёл выше.
zagayevskiy
21.10.2015 19:21С чего вы это взяли? Это адовые детали реализации.
int bufLen = 11; // Max number of chars in result char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen];lany
21.10.2015 19:29Где вы это взяли? Здесь смотрите.
zagayevskiy
21.10.2015 21:05Этим вы подтвердили мой тезис о деталях реализации. Мой кусок кода — из андроида.
lany
22.10.2015 07:45Я не говорил, что такое поведение специфицировано. Ну по тормознутости андроидовской джавы кто только не проходился.
zagayevskiy
22.10.2015 14:36Вы указали способ определения длины строки в этом комменте. Я указал кусок кода, где это не так, а вы мне — где это так. И после этого утверждаете, что не говорили о том, что это специфицировано.
Ну по тормознутости андроидовской джавы кто только не проходился.
Это вообще не в тему. Мы тут вроде не бенчмарками разных реализаций джавы занимаемся.lany
22.10.2015 15:15-1Вы указали способ определения длины строки в этом комменте. Я указал кусок кода, где это не так, а вы мне — где это так. И после этого утверждаете, что не говорили о том, что это специфицировано.
Всё верно. Всё так и было. Не вижу противоречий.
Zibx
21.10.2015 16:52Мало того что память выделить, так ещё попутно воспользоваться алгоритмом деления представленным выше (там использовать остальные прям без вариантов), к полученному добавлять на каждом шаге аски код нуля и вот это уже писать в массив.
zagayevskiy
21.10.2015 17:15Я бы советовал почитать джавовские исходники преобразования инта в строку. Не буду копипастить сюда все 68 строк метода, но, например, там есть такой цикл
// Calculate digits two-at-a-time till remaining digits fit in 16 bits while (i >= (1 << 16)) { // Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8 int q = (int) ((0x51EB851FL * i) >>> 37); int r = i - 100*q; buf[--cursor] = ONES[r]; buf[--cursor] = TENS[r]; i = q; }lany
21.10.2015 18:34Насколько я понимаю, такой изыск сейчас излишен: даже в Java-7 его способен сделать сам JIT-компилятор. Поэтому смело пишите
/100.
Utter_step
21.10.2015 14:58Есть ещё вот такой способ
некрасиво, но максимально быстро:public static int NumLeadingZeroes(int x) { int y, m, n; y = -(x >> 16); m = (y >> 16) & 16; n = 16 - m; x >>= m; y = x - 0x100; m = (y >> 16) & 8; n += m; x <<= m; y = x - 0x1000; m = (y >> 16) & 4; n += m; x <<= m; y = x - 0x4000; m = (y >> 16) & 2; n += m; x <<= m; y = x >> 14; m = y & ~(y >> 1); return n + 2 - m; } private static int[] _binaryApproximation = { 9, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0 }; private static int[] _fixApproximation = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; public static int IntLog10(int x) { int y; y = _binaryApproximation[NumLeadingZeroes(x)]; if (x < _fixApproximation[y]) { y = y - 1; } return y; } public static int DigitsCount(int x) { return IntLog10(x) + 1; }lany
21.10.2015 16:03+1«Константное время», «без ветвлений», а сами заняли минимум три кэш-линии (а скорее четыре) в L1. Вы можете хвастаться скоростью в изолированном бенчмарке, не подозревая, что увеличили рабочий набор, оставив меньше места в кэше для данных самого приложения и увеличили вероятность кэш-миссов. «Максимально быстро» — понятие очень и очень относительное.
Либа, написанная на С/С++ выдаст существенный провал в скорости из-за переключения в нейтив. Алгоритмический Java-код часто JIT-ится не хуже, чем скомпилировался бы C/C++. Самое быстрое — это интринсик наколбасить на IR прямо внутри виртуальной машины =)
Doomsday_nxt
21.10.2015 15:09public static int GetCountOfDigit(ulong n) { return n < 10000000000 ? (n < 100000 ? (n < 100 ? (n < 10 ? 1 : 2) : (n < 1000 ? 3 : (n < 10000 ? 4 : 5))) : (n < 10000000 ? (n < 1000000 ? 6 : 7) : (n < 100000000 ? 8 : (n < 1000000000 ? 9 : 10)))) : (n < 1000000000000000 ? (n < 1000000000000 ? (n < 100000000000 ? 11 : 12) : (n < 10000000000000 ? 13 : (n < 100000000000000 ? 14 : 15))) : (n < 100000000000000000 ? (n < 10000000000000000 ? 16 : 17) : (n < 1000000000000000000 ? 18 : (n < 10000000000000000000 ? 19 : 20)))); }
Не то чтобы красиво и читаемо, но зато в одну строчку (ну или пятнадцать) :-)
DigitalSmile
21.10.2015 15:35+1Может все таки поделитесь кодом как Вы измеряли скорость и что показали замеры в числах? Пока выглядит очень голословно.
И по сути заметки: первый же результат в гугле выдал ответ на stackoverflow, с которым я полностью солидарен. В 99% случаев String.valueOf подойдет на ура.
JIghtuse
21.10.2015 16:45+2Рейтинг выглядит так:
1. Сравнения (показывают лучший результат)
2. Логарифм
3. Деление
4. String (наихудший результат)
Рейтинг чего? По какому критерию оценивается? По скорости? У вас расчёт этой величины оказался узким горлышком, или вы от делать нечего решили соптимизировать что-нибудь?
String (или String.valueOf, упомянутый DigitalSmile) даёт наилучший результат с точки зрения читаемости. Иного здесь скорее всего и не требуется. Слабо верится, что производительность может упереться в подобную функцию.
Пример по «Сравнению» ничерта не читаем. Как следствие — не поддерживаем. А ещёу вас молоко убежалоне учтены отрицательные значения. Вот менее страшная, но всё равно никуда не годная версия: gist.github.com/JIghtuse/012f2f6989a47a903727.
stychos
22.10.2015 05:29Извращения ради, могу предложить ещё один вариант — делить не на 10, а на 100, сохраняя остаток, и если остаток меньше 10 но больше нуля, декрементировать результат. Это чуть быстрее тупого деления, но чуть медленнее условий (и отвратительнее на вид). На миллионе проверок:
if: 4580518 ticks;
div: 5279778 ticks;
div_2: 4891365 ticks.
ChapayHabr
22.10.2015 10:38С битовыми операциями никто не искал решения?
MichaelBorisov
23.10.2015 01:02Битовые операции хороши при работе в двоичной, восьмеричной и шестнадцатеричной системах счисления. В десятичной системе от них мало толку. Можно получить разве только первое приближение, которое впоследствии улучшать другими методами.
xXxVano
23.10.2015 12:42Насколько помню Log10(x)/Log2(x) = const. Так что можно найти в двоичной системе исчисления, и домножить на константу (предварительно её вычислив).
xiWera
24.10.2015 02:07+1Если брать целочисленый логарифм, то ничего не получится, так как потеряная дробная часть будет вносить ошибку. А вариант с плавающей точкой фактически эквивалентен тому, чтобы сразу взять десятичный логарифм.
lany
В JDK такой способ: