Ответы, которые вам дают люди, верны ... они дают вам длину вашего целого без преобразования его в строку ... но почему вы не хотите преобразовать его в строку? Это скорость? Если это так, я не уверен, что эти методы будут быстрее ... вы можете провести некоторые тесты (или решить, если это вообще имеет значение.)
Беска
3
Шестнадцатеричные цифры @ptomli - это все еще цифры, только в другой базовой системе.
Марк Пим
2
@Ptomli Конечно, но как в функции Integer.toString, так и в общем разговоре, по умолчанию используется десятичная дробь. Когда банк говорит мне: «Напишите сумму вашего чека в этом поле», я не спрашиваю их, следует ли мне писать его в десятичном, шестнадцатеричном или восьмеричном виде. Мы принимаем десятичную, если иное не указано или не требуется в контексте.
Джей
Ответы:
349
Ваше решение на основе строк отлично, ничего «аккуратного» в этом нет. Вы должны понимать, что математически числа не имеют ни длины, ни цифр. Длина и цифры являются свойствами физического представления числа в конкретной базе, то есть строки.
Решение на основе логарифма делает (некоторые из) то же самое, что решение на основе строк, делает внутренне, и, вероятно, делает это (незначительно) быстрее, потому что оно только выдает длину и игнорирует цифры. Но я бы на самом деле не считал это более понятным в намерениях - и это самый важный фактор.
+1 для рассмотрения намерений кода при выборе способа решения проблемы
pupeno
5
Datapoint: На моем компьютере метод log, кажется, работает чуть менее чем в два раза быстрее, чем методы длины строки. Я бы не назвал это незначительным, если бы метод вызывался много раз или в критической по времени части кода.
CPerkins
1
Смотрите мой тестовый модуль ниже (который может быть ошибочным, я не эксперт по тестам). При большом количестве запусков (100 000 000) скорость на моей машине составляет от 11 до 8 секунд, едва ли в два раза быстрее.
Жан
5
@CPerkins. Преждевременная оптимизация. Вы знаете шпиль.
Майкл Боргвардт
11
Некоторое (довольно позднее) дополнение: оно может не работать должным образом для отрицательных значений, в зависимости от того, ожидаете ли вы, что цифра «-» или нет. Добавление Math.abs()будет исправить это, хотя.
И это быстрее или лучше, чем использовать мой вариант?
fnst
+1 Ты избил меня на секунду, и твой ответ был верным, где мой был слегка выключен. Обратите внимание, однако, что компилятор будет жаловаться из-за отсутствующего приведения к int
Dirk
2
@ Tom Почему вы предполагаете, что это дорого? Можно предположить, что математический сопроцессор выполнит его, поэтому он может быть близок к скорости сложения. Даже если сейчас java не использует сопроцессор, можно предположить, что он может ... (Мы просто проигнорируем ваше еще более необразованное предположение, что Java работает медленно, потому что вы, вероятно, не заинтересованы в доказательствах - или если бы вы были, вы бы пошли на shootout.alioth.debian.org и выяснили это сами)
Билл К
8
Работает ... если только проверяемое вами значение не равно 0, что даст вам странные результаты (-2147483647). Math.log10 API: «Если аргумент имеет положительный ноль или отрицательный ноль, то результатом будет отрицательная бесконечность».
Мудзиму
2
+1 Представление метода, который не требует выделения памяти объектам, что необходимо для максимального повторного использования, чтобы избежать сборов GC.
Майкл Войчик
159
Самый быстрый подход: разделяй и властвуй.
Предполагая, что ваш диапазон от 0 до MAX_INT, тогда у вас есть от 1 до 10 цифр. Вы можете приблизиться к этому интервалу, используя разделяй и властвуй, до 4 сравнений на каждый вход. Сначала вы делите [1..10] на [1..5] и [6..10] с одним сравнением, а затем каждый интервал длины 5 делите, используя одно сравнение на один интервал длины 3 и один интервал длины 2. Интервал длины 2 требует еще одного сравнения (всего 3 сравнения), интервал длины 3 можно разделить на интервал длины 1 (решение) и интервал длины 2. Итак, вам нужно 3 или 4 сравнения.
Нет делений, операций с плавающей запятой, дорогих логарифмов, только целочисленные сравнения.
Код (длинный, но быстрый):
if(n <100000){// 5 or lessif(n <100){// 1 or 2if(n <10)return1;elsereturn2;}else{// 3 or 4 or 5if(n <1000)return3;else{// 4 or 5if(n <10000)return4;elsereturn5;}}}else{// 6 or moreif(n <10000000){// 6 or 7if(n <1000000)return6;elsereturn7;}else{// 8 to 10if(n <100000000)return8;else{// 9 or 10if(n <1000000000)return9;elsereturn10;}}}
Тест (после прогрева JVM) - посмотрите код ниже, чтобы увидеть, как тест проводился:
базовый метод (с длиной строки): 2145 мс
метод log10: 711 мс = в 3,02 раза быстрее базовой линии
повторное деление: 2797 мс = 0,77 раза быстрее, чем базовый уровень
разделяй и властвуй: 74 мс = 28,99
раз быстрее базовой линии
Полный код:
publicstaticvoid main(String[] args)throwsException{// validate methods:for(int i =0; i <1000; i++)if(method1(i)!= method2(i))System.out.println(i);for(int i =0; i <1000; i++)if(method1(i)!= method3(i))System.out.println(i +" "+ method1(i)+" "+ method3(i));for(int i =333; i <2000000000; i +=1000)if(method1(i)!= method3(i))System.out.println(i +" "+ method1(i)+" "+ method3(i));for(int i =0; i <1000; i++)if(method1(i)!= method4(i))System.out.println(i +" "+ method1(i)+" "+ method4(i));for(int i =333; i <2000000000; i +=1000)if(method1(i)!= method4(i))System.out.println(i +" "+ method1(i)+" "+ method4(i));// work-up the JVM - make sure everything will be run in hot-spot mode
allMethod1();
allMethod2();
allMethod3();
allMethod4();// run benchmarkChronometer c;
c =newChronometer(true);
allMethod1();
c.stop();long baseline = c.getValue();System.out.println(c);
c =newChronometer(true);
allMethod2();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");
c =newChronometer(true);
allMethod3();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");
c =newChronometer(true);
allMethod4();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");}privatestaticint method1(int n){returnInteger.toString(n).length();}privatestaticint method2(int n){if(n ==0)return1;return(int)(Math.log10(n)+1);}privatestaticint method3(int n){if(n ==0)return1;int l;for(l =0; n >0;++l)
n /=10;return l;}privatestaticint method4(int n){if(n <100000){// 5 or lessif(n <100){// 1 or 2if(n <10)return1;elsereturn2;}else{// 3 or 4 or 5if(n <1000)return3;else{// 4 or 5if(n <10000)return4;elsereturn5;}}}else{// 6 or moreif(n <10000000){// 6 or 7if(n <1000000)return6;elsereturn7;}else{// 8 to 10if(n <100000000)return8;else{// 9 or 10if(n <1000000000)return9;elsereturn10;}}}}privatestaticint allMethod1(){int x =0;for(int i =0; i <1000; i++)
x = method1(i);for(int i =1000; i <100000; i +=10)
x = method1(i);for(int i =100000; i <1000000; i +=100)
x = method1(i);for(int i =1000000; i <2000000000; i +=200)
x = method1(i);return x;}privatestaticint allMethod2(){int x =0;for(int i =0; i <1000; i++)
x = method2(i);for(int i =1000; i <100000; i +=10)
x = method2(i);for(int i =100000; i <1000000; i +=100)
x = method2(i);for(int i =1000000; i <2000000000; i +=200)
x = method2(i);return x;}privatestaticint allMethod3(){int x =0;for(int i =0; i <1000; i++)
x = method3(i);for(int i =1000; i <100000; i +=10)
x = method3(i);for(int i =100000; i <1000000; i +=100)
x = method3(i);for(int i =1000000; i <2000000000; i +=200)
x = method3(i);return x;}privatestaticint allMethod4(){int x =0;for(int i =0; i <1000; i++)
x = method4(i);for(int i =1000; i <100000; i +=10)
x = method4(i);for(int i =100000; i <1000000; i +=100)
x = method4(i);for(int i =1000000; i <2000000000; i +=200)
x = method4(i);return x;}
Опять же, ориентир:
базовый метод (с длиной строки): 2145 мс
метод log10: 711 мс = в 3,02 раза быстрее базовой линии
повторное деление: 2797 мс = 0,77 раза быстрее, чем базовый уровень
разделяй и властвуй: 74 мс = 28,99
раз быстрее базовой линии
Изменить:
После того, как я написал тест, я взял краткий обзор Integer.toString из Java 6 и обнаружил, что он использует:
это выглядит великолепно. Вы могли бы написать это немного более компактно, используя оператор?:, чтобы получить больше одобрения
Андре Парейс
88
поговорим о преждевременной оптимизации: D
Гордон Густафсон
2
Мне это нравится! Как насчет блока переключателей вместо вложенных if-elseses?
Кебман
2
Я не осознавал все это, если операторы else были бы НАСТОЛЬКО быстрее, чем преобразовывать int в String, а затем вызывать .length. +1
Оген
15
Использование троичного оператора сводит его к 101 символу: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
Джонатан Гаврих
13
Два комментария по поводу вашего теста: Java - это сложная среда, которая включает в себя своевременную компиляцию, сборку мусора и так далее, поэтому, чтобы получить справедливое сравнение, всякий раз, когда я запускаю тест, я всегда: (a) заключаю два теста в цикле, который запускает их в последовательности 5 или 10 раз. Довольно часто время выполнения на втором проходе цикла сильно отличается от первого. И (б) После каждого «подхода» я делаю System.gc (), чтобы попытаться запустить сборку мусора. В противном случае первый подход может сгенерировать кучу объектов, но этого недостаточно, чтобы вызвать сборку мусора, затем второй подход создает несколько объектов, куча исчерпывается и выполняется сбор мусора. Затем второй подход «взимается» за сбор мусора, оставленного первым подходом. Очень несправедливо!
Тем не менее, ни один из вышеперечисленных не имеет существенного значения в этом примере.
С этими модификациями или без них я получил совсем другие результаты, чем вы. Когда я запускал это, да, подход toString давал времена выполнения от 6400 до 6600 миллисекунд, в то время как подход с логарифмированием занимал от 20 000 до 20 400 миллисекунд. Вместо того, чтобы быть немного быстрее, лог-подход был в 3 раза медленнее для меня.
Обратите внимание, что эти два подхода сопряжены с очень разными затратами, поэтому это не является совершенно шокирующим: подход toString создаст много временных объектов, которые необходимо очистить, в то время как подход с использованием журнала требует более интенсивных вычислений. Так что, возможно, разница в том, что на машине с меньшим объемом памяти toString требует больше циклов сборки мусора, в то время как на машине с более медленным процессором дополнительное вычисление журнала будет более болезненным.
Я также попробовал третий подход. Я написал эту маленькую функцию:
Это длилось от 1600 до 1900 миллисекунд - менее 1/3 от подхода toString и 1/10 от лог-подхода на моей машине.
Если бы у вас был широкий диапазон чисел, вы могли бы ускорить его, начав делить на 1000 или 1000000, чтобы уменьшить количество циклов. Я не играл с этим.
Вы пытались изменить вход? В противном случае виртуальная машина горячей точки может оптимизировать этот график, что приведет к неверным оценкам, поскольку каждый раз он возвращает одно и то же предварительно вычисленное значение.
Эрик
11
Использование Java
int nDigits =Math.floor(Math.log10(Math.abs(the_integer)))+1;
Круто. но я думаю, что нужно абс (число), а также "0" это тоже особый случай?
DmitryK
Да. Если вам нужно учесть знак, вам нужно будет сделать что-то вроде 1 + (int) Math.floor (Math.log10 (Math.abs (number))) + ((number <0)? 1: 0)
Дирк
5
Это Math.floorнемного избыточно, не так ли? Кастинг intбудет округлять его в любом случае.
CompuChip
5
Решение Мариана адаптировано для длинных номеров (до 9,223,372,036,854,775,807), на случай, если кто-то захочет скопировать и вставить его. В программе, которую я написал, для чисел до 10000 было гораздо более вероятным, поэтому я сделал для них специальную ветку. Во всяком случае, это не будет иметь существенного значения.
publicstaticint numberOfDigits (long n){// Guessing 4 digit numbers will be more probable.// They are set in the first branch.if(n <10000L){// from 1 to 4if(n <100L){// 1 or 2if(n <10L){return1;}else{return2;}}else{// 3 or 4if(n <1000L){return3;}else{return4;}}}else{// from 5 a 20 (albeit longs can't have more than 18 or 19)if(n <1000000000000L){// from 5 to 12if(n <100000000L){// from 5 to 8if(n <1000000L){// 5 or 6if(n <100000L){return5;}else{return6;}}else{// 7 u 8if(n <10000000L){return7;}else{return8;}}}else{// from 9 to 12if(n <10000000000L){// 9 or 10if(n <1000000000L){return9;}else{return10;}}else{// 11 or 12if(n <100000000000L){return11;}else{return12;}}}}else{// from 13 to ... (18 or 20)if(n <10000000000000000L){// from 13 to 16if(n <100000000000000L){// 13 or 14if(n <10000000000000L){return13;}else{return14;}}else{// 15 or 16if(n <1000000000000000L){return15;}else{return16;}}}else{// from 17 to ...¿20?if(n <1000000000000000000L){// 17 or 18if(n <100000000000000000L){return17;}else{return18;}}else{// 19? Can it be?// 10000000000000000000L is'nt a valid long.return19;}}}}}
Вы проверяли это? Вы знаете, что, даже если это имеет смысл для человеческой точки зрения, на самом деле это не работает так же, как «образ мышления» машины, верно? --- Позвольте мне предложить одну вещь: создайте массив из двух миллионов чисел, предпочтительно Long.MAX_VALUE, который является наихудшим вариантом сложности вашего кода, и используйте его System.nanoTime()для тестирования синхронизации с наихудшими случаями сложности другого решения. ++ На самом деле, попробуйте это массив , заполненный набором рандомизер в диапазоне 0до Long.MAX_VALUEтоже, только для «средней сложности» тестирования ++ Вы можете найти результаты ... очень шокирует.
XenoRo
@thelima Это не работает правильно для нуля или негатива, но это небольшая ошибка. Принцип выглядит правильным для меня. О каком «шокирующем» результате вы говорите?
Джей
Давайте просто скажем, что компьютеры ... Ну ... Они не любят делиться. И в тех случаях, когда нужно обрабатывать большие «очереди» из больших чисел, и каждая цифра в каждом обработанном числе будет нуждаться в делении ... Что ж ... Вещи "начинают становиться очень медленными, очень быстрыми" ... Если вы поймаете мою значение ... --- Вот почему вы видите здесь многие ответы, используя коды, основанные на тестах и сравнении с каждой десятичной цифрой, используя 'если вместо, а не деления: если это не быстрее, по крайней мере, он поддерживает большую часть своей скорости независимо из худших случаев. ---
Проведите
@TheLima, о чем ты говоришь? Для int,этого цикла выполняется максимум 11 раз. У вас есть доказательства ваших утверждений?
Маркиз Лорн
@EJP С аппаратной точки зрения деление - это итеративный процесс. Самый быстрый алгоритм деления, который я знаю, это radix4, который генерирует 4 бита за итерацию; поэтому для 32-битного деления требуется не менее 8 итераций. Например, умножения можно выполнять параллельно, а также разбивать на более простые умножения; либо до уровня битов (требующего только 5 операций), либо с частичным разбивкой плюс справочная таблица в конце (компромисс между классическим размером и скоростью). Дело не только в том, «сколько итераций»; проблема с делениями связана с тем, «что подразумевает / делает каждая итерация на аппаратном уровне»
Время выполнения 1: 6765
с: 400000000
Время выполнения 2: 6000
с: 400000000
Теперь мне остается только задаться вопросом, действительно ли мой эталон что-то значит, но я получаю согласованные результаты (вариации в течение мс) за несколько прогонов самого эталона ... :) Похоже, бесполезно пытаться оптимизировать это ...
edit: после комментария ptomli я заменил «число» на «i» в вышеприведенном коде и получил следующие результаты за 5 прогонов:
Время выполнения 1: 11500
s: 788888890
Время выполнения 2: 8547
s: 788888890
Время выполнения 1: 11485
s: 788888890
Время выполнения 2: 8547
s: 788888890
Время выполнения 1: 11469
s: 788888890
Время выполнения 2: 8547
s: 788888890
Время выполнения 1: 11500
s: 788888890
Время выполнения 2: 8547
s: 788888890
Время выполнения 1: 11484
s: 788888890
Время выполнения 2: 8547
s: 788888890
Я бы не назвал одну строку для цикла с пустым телом простой. Кроме того, по модулю 10 можно увидеть, вернули ли вы то же самое (вы не можете просто использовать сравнение?).
Teepeemm
0
Или вместо длины вы можете проверить, больше или меньше число, чем желаемое число.
publicvoid createCard(int cardNumber,int cardStatus,int customerId)throwsSQLException{if(cardDao.checkIfCardExists(cardNumber)==false){if(cardDao.createCard(cardNumber, cardStatus, customerId)==true){System.out.println("Card created successfully");}else{}}else{System.out.println("Card already exists, try with another Card Number");do{System.out.println("Enter your new Card Number: ");
scan =newScanner(System.in);int inputCardNumber = scan.nextInt();
cardNumber = inputCardNumber;}while(cardNumber <95000000);
cardDao.createCard(cardNumber, cardStatus, customerId);}}
Я не понимаю Кажется, ты отвечаешь на другой вопрос.
Teepeemm
0
Я еще не видел решения на основе умножения. Логарифмические, разделительные и строковые решения станут довольно громоздкими против миллионов тестовых случаев, поэтому вот один для ints:
/**
* Returns the number of digits needed to represents an {@code int} value in
* the given radix, disregarding any sign.
*/publicstaticint len(int n,int radix){
radixCheck(radix);// if you want to establish some limitation other than radix > 2
n =Math.abs(n);int len =1;long min = radix -1;while(n > min){
n -= min;
min *= radix;
len++;}return len;}
В базе 10 это работает, потому что n по существу сравнивается с 9, 99, 999 ... как минимум 9, 90, 900 ... и n вычитается из 9, 90, 900 ...
К сожалению, это невозможно перенести, longпросто заменив каждый экземпляр из- intза переполнения. С другой стороны, так получилось, что он будет работать для баз 2 и 10 (но плохо работает для большинства других баз). Вам понадобится таблица соответствия для точек переполнения (или тест деления ... ов)
/**
* For radices 2 &le r &le Character.MAX_VALUE (36)
*/privatestaticlong[] overflowpt ={-1,-1,4611686018427387904L,8105110306037952534L,3458764513820540928L,5960464477539062500L,3948651115268014080L,3351275184499704042L,8070450532247928832L,1200757082375992968L,9000000000000000000L,5054470284992937710L,2033726847845400576L,7984999310198158092L,2022385242251558912L,6130514465332031250L,1080863910568919040L,2694045224950414864L,6371827248895377408L,756953702320627062L,1556480000000000000L,3089447554782389220L,5939011215544737792L,482121737504447062L,839967991029301248L,1430511474609375000L,2385723916542054400L,3902460517721977146L,6269893157408735232L,341614273439763212L,513726300000000000L,762254306892144930L,1116892707587883008L,1617347408439258144L,2316231840055068672L,3282671350683593750L,4606759634479349760L};publicstaticint len(long n,int radix){
radixCheck(radix);
n = abs(n);int len =1;long min = radix -1;while(n > min){
len++;if(min == overflowpt[radix])break;
n -= min;
min *= radix;}return len;}
С дизайном (на основе проблемы). Это альтернатива разделяй и властвуй. Сначала мы определим перечисление (учитывая, что это только для беззнакового целого).
«Разделяй и властвуй» начинается с середины и делит пополам оставшуюся область поиска. Это имеет линейное время выполнения. Но это не имеет значения только для 9 сравнений. Но не испортит ли это, если num>=Nine.getValue()?
Teepeemm
0
Кто-то хочет сделать это главным образом потому, что он / она хочет «представить» это, что, в основном, означает, что в конце концов он должен быть «toString-ed» (или преобразован другим способом) в явном или неявном виде в любом случае; прежде чем он может быть представлен (напечатан, например).
Если это так, то просто попытайтесь сделать необходимое «toString» явным и сосчитайте биты.
Я вижу людей, использующих библиотеки String или даже использующих класс Integer. Ничего плохого в этом нет, но алгоритм получения количества цифр не так уж и сложен. Я использую long в этом примере, но он работает так же хорошо с int.
privatestaticint getLength(long num){int count =1;while(num >=10){
num = num /10;
count++;}return count;}
нет String API, нет утилит, нет преобразования типов, просто чистая Java-итерация ->
publicstaticint getNumberOfDigits(int input){int numOfDigits =1;int base =1;while(input >= base *10){
base = base *10;
numOfDigits++;}return numOfDigits;}
Вы можете долго идти на большие значения, если хотите.
Вам, вероятно, следует протестировать его (и убедиться, что он действителен в Java и правильно отформатирован). Но рекурсивный подход «делись на 10» был опубликован Джедаем Дулой 3 года назад.
Teepeemm
-2
Вы могли бы цифры, используя последовательное деление на десять:
int a=0;if(no <0){
no =-no;}elseif(no ==0){
no =1;}while(no >0){
no = no /10;
a++;}System.out.println("Number of digits in given number is: "+a);
Подход «делим на 10» был впервые опубликован Sinista 3 года назад. Это единственная причина, по которой я могу думать, что ты получил отрицательный голос.
Teepeemm
-2
Введите число и создайте Arraylist, и цикл while запишет все цифры в Arraylist. Затем мы можем вывести размер массива, который будет длиной целочисленного значения, которое вы ввели.
ArrayList<Integer> a=newArrayList<>();while(number >0){
remainder = num %10;
a.add(remainder);
number = number /10;}int m=a.size();
Это работает с переменной счетчика чисел, что 10 = 1 разрядное пространство. Например .1 = 1 десятая => 1 разрядный пробел. Поэтому, если у вас есть, int number = 103342;вы получите 6, потому что это эквивалентно .000001 пробелов назад. Кроме того, у кого-нибудь есть лучшее имя переменной дляnumberCounter ? Я не могу придумать ничего лучшего.
Изменить: Просто подумал о лучшем объяснении. По сути, этот цикл while делает так, что вы делите свое число на 10, пока оно не станет меньше единицы. По сути, когда вы делите что-то на 10, вы перемещаете его назад на один номер, поэтому вы просто делите это на 10, пока не достигнете <1 для количества цифр в вашем номере.
Вот еще одна версия, которая может считать количество чисел в десятичном виде:
Ответы:
Ваше решение на основе строк отлично, ничего «аккуратного» в этом нет. Вы должны понимать, что математически числа не имеют ни длины, ни цифр. Длина и цифры являются свойствами физического представления числа в конкретной базе, то есть строки.
Решение на основе логарифма делает (некоторые из) то же самое, что решение на основе строк, делает внутренне, и, вероятно, делает это (незначительно) быстрее, потому что оно только выдает длину и игнорирует цифры. Но я бы на самом деле не считал это более понятным в намерениях - и это самый важный фактор.
источник
Math.abs()
будет исправить это, хотя.Логарифм твой друг:
Примечание: действует только при n> 0.
источник
Самый быстрый подход: разделяй и властвуй.
Предполагая, что ваш диапазон от 0 до MAX_INT, тогда у вас есть от 1 до 10 цифр. Вы можете приблизиться к этому интервалу, используя разделяй и властвуй, до 4 сравнений на каждый вход. Сначала вы делите [1..10] на [1..5] и [6..10] с одним сравнением, а затем каждый интервал длины 5 делите, используя одно сравнение на один интервал длины 3 и один интервал длины 2. Интервал длины 2 требует еще одного сравнения (всего 3 сравнения), интервал длины 3 можно разделить на интервал длины 1 (решение) и интервал длины 2. Итак, вам нужно 3 или 4 сравнения.
Нет делений, операций с плавающей запятой, дорогих логарифмов, только целочисленные сравнения.
Код (длинный, но быстрый):
Тест (после прогрева JVM) - посмотрите код ниже, чтобы увидеть, как тест проводился:
раз быстрее базовой линии
Полный код:
Опять же, ориентир:
раз быстрее базовой линии
Изменить: После того, как я написал тест, я взял краткий обзор Integer.toString из Java 6 и обнаружил, что он использует:
Я сравнил его с моим решением «разделяй и властвуй»:
Мой примерно в 4 раза быстрее, чем решение Java 6.
источник
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
Два комментария по поводу вашего теста: Java - это сложная среда, которая включает в себя своевременную компиляцию, сборку мусора и так далее, поэтому, чтобы получить справедливое сравнение, всякий раз, когда я запускаю тест, я всегда: (a) заключаю два теста в цикле, который запускает их в последовательности 5 или 10 раз. Довольно часто время выполнения на втором проходе цикла сильно отличается от первого. И (б) После каждого «подхода» я делаю System.gc (), чтобы попытаться запустить сборку мусора. В противном случае первый подход может сгенерировать кучу объектов, но этого недостаточно, чтобы вызвать сборку мусора, затем второй подход создает несколько объектов, куча исчерпывается и выполняется сбор мусора. Затем второй подход «взимается» за сбор мусора, оставленного первым подходом. Очень несправедливо!
Тем не менее, ни один из вышеперечисленных не имеет существенного значения в этом примере.
С этими модификациями или без них я получил совсем другие результаты, чем вы. Когда я запускал это, да, подход toString давал времена выполнения от 6400 до 6600 миллисекунд, в то время как подход с логарифмированием занимал от 20 000 до 20 400 миллисекунд. Вместо того, чтобы быть немного быстрее, лог-подход был в 3 раза медленнее для меня.
Обратите внимание, что эти два подхода сопряжены с очень разными затратами, поэтому это не является совершенно шокирующим: подход toString создаст много временных объектов, которые необходимо очистить, в то время как подход с использованием журнала требует более интенсивных вычислений. Так что, возможно, разница в том, что на машине с меньшим объемом памяти toString требует больше циклов сборки мусора, в то время как на машине с более медленным процессором дополнительное вычисление журнала будет более болезненным.
Я также попробовал третий подход. Я написал эту маленькую функцию:
Это длилось от 1600 до 1900 миллисекунд - менее 1/3 от подхода toString и 1/10 от лог-подхода на моей машине.
Если бы у вас был широкий диапазон чисел, вы могли бы ускорить его, начав делить на 1000 или 1000000, чтобы уменьшить количество циклов. Я не играл с этим.
источник
Использование Java
использовать
import java.lang.Math.*;
в началеИспользуя C
использовать
inclue math.h
в началеисточник
the_integer
есть0
, поэтому проверьте , что.Оставить комментарий пока не могу, поэтому выложу отдельным ответом.
Решение на основе логарифма не рассчитывает правильное количество цифр для очень больших длинных целых чисел, например:
Логарифмическое решение вычисляет неверное количество цифр в больших целых числах
источник
Так как количество цифр в базе 10 целого числа просто 1 + усечение (log10 (число)) , вы можете сделать:
Отредактировано, потому что мое последнее редактирование исправило пример кода, но не описание.
источник
Math.floor
немного избыточно, не так ли? Кастингint
будет округлять его в любом случае.Решение Мариана адаптировано для длинных номеров (до 9,223,372,036,854,775,807), на случай, если кто-то захочет скопировать и вставить его. В программе, которую я написал, для чисел до 10000 было гораздо более вероятным, поэтому я сделал для них специальную ветку. Во всяком случае, это не будет иметь существенного значения.
источник
Еще один струнный подход. Коротко и сладко - для любого целого числа
n
.источник
n
и нуля. Можно использовать("" + Math.abs(n)).length()
для получения длины отрицательного целого числа.Можно попробовать? ;)
основанный на решении Дирка
источник
Как насчет простой старой математики? Разделите на 10, пока не достигнете 0.
источник
Long.MAX_VALUE
, который является наихудшим вариантом сложности вашего кода, и используйте егоSystem.nanoTime()
для тестирования синхронизации с наихудшими случаями сложности другого решения. ++ На самом деле, попробуйте это массив , заполненный набором рандомизер в диапазоне0
доLong.MAX_VALUE
тоже, только для «средней сложности» тестирования ++ Вы можете найти результаты ... очень шокирует.int,
этого цикла выполняется максимум 11 раз. У вас есть доказательства ваших утверждений?Решение Мариана, теперь с Тернарием:
Потому что мы можем.
источник
Любопытно, я пытался это сравнить ...
результаты:
Теперь мне остается только задаться вопросом, действительно ли мой эталон что-то значит, но я получаю согласованные результаты (вариации в течение мс) за несколько прогонов самого эталона ... :) Похоже, бесполезно пытаться оптимизировать это ...
edit: после комментария ptomli я заменил «число» на «i» в вышеприведенном коде и получил следующие результаты за 5 прогонов:
источник
Как насчет этого рекурсивного метода?
источник
простое решение:
источник
Действительно простое решение:
источник
Или вместо длины вы можете проверить, больше или меньше число, чем желаемое число.
}
источник
Я еще не видел решения на основе умножения. Логарифмические, разделительные и строковые решения станут довольно громоздкими против миллионов тестовых случаев, поэтому вот один для
ints
:В базе 10 это работает, потому что n по существу сравнивается с 9, 99, 999 ... как минимум 9, 90, 900 ... и n вычитается из 9, 90, 900 ...
К сожалению, это невозможно перенести,
long
просто заменив каждый экземпляр из-int
за переполнения. С другой стороны, так получилось, что он будет работать для баз 2 и 10 (но плохо работает для большинства других баз). Вам понадобится таблица соответствия для точек переполнения (или тест деления ... ов)источник
С дизайном (на основе проблемы). Это альтернатива разделяй и властвуй. Сначала мы определим перечисление (учитывая, что это только для беззнакового целого).
Теперь мы определим класс, который проходит через значения перечисления, сравнивает и возвращает соответствующую длину.
Время выполнения этого решения совпадает с подходом «разделяй и властвуй».
источник
num>=Nine.getValue()
?Кто-то хочет сделать это главным образом потому, что он / она хочет «представить» это, что, в основном, означает, что в конце концов он должен быть «toString-ed» (или преобразован другим способом) в явном или неявном виде в любом случае; прежде чем он может быть представлен (напечатан, например).
Если это так, то просто попытайтесь сделать необходимое «toString» явным и сосчитайте биты.
источник
Мы можем добиться этого с помощью рекурсивного цикла
источник
Я написал эту функцию после просмотра
Integer.java
исходного кода.источник
Я вижу людей, использующих библиотеки String или даже использующих класс Integer. Ничего плохого в этом нет, но алгоритм получения количества цифр не так уж и сложен. Я использую long в этом примере, но он работает так же хорошо с int.
источник
нет String API, нет утилит, нет преобразования типов, просто чистая Java-итерация ->
Вы можете долго идти на большие значения, если хотите.
источник
источник
Простой рекурсивный способ
не проверено
источник
Вы могли бы цифры, используя последовательное деление на десять:
источник
Введите число и создайте
Arraylist
, и цикл while запишет все цифры вArraylist
. Затем мы можем вывести размер массива, который будет длиной целочисленного значения, которое вы ввели.источник
Вот действительно простой метод, который я сделал, который работает для любого числа:
Это работает с переменной счетчика чисел, что 10 = 1 разрядное пространство. Например .1 = 1 десятая => 1 разрядный пробел. Поэтому, если у вас есть,
int number = 103342;
вы получите 6, потому что это эквивалентно .000001 пробелов назад. Кроме того, у кого-нибудь есть лучшее имя переменной дляnumberCounter
? Я не могу придумать ничего лучшего.Изменить: Просто подумал о лучшем объяснении. По сути, этот цикл while делает так, что вы делите свое число на 10, пока оно не станет меньше единицы. По сути, когда вы делите что-то на 10, вы перемещаете его назад на один номер, поэтому вы просто делите это на 10, пока не достигнете <1 для количества цифр в вашем номере.
Вот еще одна версия, которая может считать количество чисел в десятичном виде:
источник
Попробуйте преобразовать int в строку, а затем получите длину строки . Это должно получить длину Int .
источник
number
отрицательно.