Помогите оптимизировать. Код отрабатывает правильно с числами до 10 разрядов,дальше зависон машины. С нулями еще пока не работал. Логика такая. Сначала генерирую список чисел с неубываемыми цифрами и добавляю их в list1. После чего перебираю list и суммирую степени через двумерный массив func, чтобы не считать лишний раз степени ,формирую list2. После чего проверяю еще раз ,есть ли в этом списке числа армстронга. Делал чисто по этому шаблону https://acmp.ru/article.asp?id_text=198. Может кто подсказать,гдн тратиться времени много
import java.util.Iterator;
import java.util.TreeSet;
public class Solution {
public static long [][] mass;
static{
mass=new long [10][20];
for(int i=1;i<10;i++){
for(int j=1;j<20;j++){
mass[i][j]=(long)Math.pow(i,j);
}
}
}
public static void main(String[] args) {
TreeSet<Long> list=new TreeSet<>();
TreeSet<Long> list2=new TreeSet<>();
TreeSet<Long> list3=new TreeSet<>();
long N=Long.MAX_VALUE;
long numb=0;
while (numb<N){
numb++;
int k=1;
long buf=0;
int count=0;
if (numb%10!=0) list.add(numb);
else{
while((numb)%(k*10)==0){
k=k*10;
buf=numb/k;
count++;
}
long end=buf%10;
buf=buf*(int)Math.pow(10,count);
for (int i=1;i<count+1;i++){
buf=buf +end*(int)Math.pow(10,count-i);
}
list.add(buf);
numb=buf;
}
} //формируем list с неубывающими числами
for(long s:list) {
long temp=s;
long sum=0;
long ost=0;
int deg = (int)Math.log10(temp)+1;
int i=0;
while(i<deg){
ost=temp%10;
sum=sum+func((int)ost,deg);
temp=temp/10;
i++;
}
list2.add(sum);
} //формируем list2 со всеми числами из list (потенциальные числа армстронга)
for(long s:list2) {
long temp=s;
long sum=0;
long ost=0;
int deg = (int)Math.log10(temp)+1;
int i=0;
while(i<deg){
ost=temp%10;
sum=sum+func((int)ost,deg);
temp=temp/10;
i++;
}
if(sum==s) list3.add(sum);
} //проверяем,являются ли числа из лист 2 числами армстронга
System.out.println(list3);
}
public static long func(int i,int j){
return Solution.mass[i][j];
}
}
Kostya Kozhevnikov
28 уровень
где можно оптимизировать
Решен
Комментарии (3)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Justinian Judge в Mega City One Master
22 февраля 2020, 13:51полезный
Так, во-первых.
Форматирование кода - в форме набора поста/коммента есть тег < code >
У тебя очень много пустых строк там где не нужно.
Язык программирования это тоже язык.
Мы можем отделять пробелом логические блока кода.
Например вот так.
Но
если
писать
вот
так
то
как-то не очень для восприятия.
Ты не пишешь так в реальной жизни тексты, то не пиши и в коде.
Во-вторых,
здесь я еще скрепя сердце дал поблажку что это алгоритмическая задача, и в них особое отношение к правилам написания кода., но вот это:
это уже перебор. Я не мог вспомнить даже видел ли когда-нибудь подобное, иф без скобок и элс с скобками.
Ставить фигурные скобки всегда - никогда не будет ошибкой.
А вот их не поставить, это может быть ошибкой во многих случаях.
В-третьих, форматирование, работаешь с кодом, периодически нажимай CTRL+ALT+L идея сама поможет отформатировать скобки и пробелы.
коллекции мы объявляем через интерфейсы, разве что ты точно знаешь что ты тюнингуешь производительность таким образом.
По самому вопросу, если бы тебе дали задание, ты программист, тебя мэрия крупного города наняла для того чтобы посчитать сколько за сутки по центральной улице проезжает автомобилей в зависимости от цвета - красных, зеленых и тд.
Как бы поступил я, я бы запросил тысяч 10-20 долларов, поставил бы камеры, нанял бы пару человек, напилили бы распознавание цвета и попробовали бы прикрутить.
Как сделал бы ты, запросил бы 2 млрд доллара, нанял бы 50 000 рабочих, построил бы гаражи в поле на 300 000 автомобилей, и все автомобили бы загнал туда., где их вручную бы считал +1
Justinian Judge в Mega City One Master
22 февраля 2020, 13:53решение
у меня твой код завершился с ошибкой - память закончилась...
Какое прогнозированное число, сколько чисел ты перебираешь от 0 до Long.MAX_VALUE ? Сколько чисел проходят отсев и являются проверяемыми на то, число они армстронга или нет?
Как ты понимаешь, числа в коллекции сбрасывать нельзя, в задачах на обработку потоков данных мы работаем с потоком.
В одно ухо влетело в другое вылетело. Пришло число в код, мы его проверили и ушло. Нам не зачем хранить их в коллекциях, массивах и тд.
Этот момент нужно пофиксить, и разберись сколько чисел у тебя подпадают под проверку, я не помню точных чисел, у меня медленный алгоритм был, около 10 с еле влез, по-моему около 6-20 млн чисел проверялось в указанном диапазоне.
Те версии которые за 0.4 секунды считают, не знаю сколько, там немного другой принцип работы.
+2
Kostya Kozhevnikov
22 февраля 2020, 18:29
Спасибо большое, намёк со светофором понял. И спасибо за замечания, очень ценю
0