Производительность небольшого Java-приложения

Question

У меня есть программа для моего класса CS, и мне нужно сократить время выполнения, когда я получаю большие входы.

Вот код

import java.util.Scanner; 
import java.util.ArrayList; 

public class Main{ 
    public static void main (String[] args){ 


    Scanner input = new Scanner(System.in); 


    int hours = 12; 
    int minutes = 00; 

    int count = 0; 

    int d = input.nextInt(); 

    for(int i = 0; i < d; i++){ 
     minutes++; 
     if(minutes >= 60){ 
      hours++; 
      hours = hours % 12; 
      minutes = 0; 
     } 

     String formatNull = ""; 
     String hourFormat = ""; 

     if(minutes < 10){ 
      formatNull = "0"; 
     } 

     if(hours < 10) 
      hourFormat = "0"; 

     String finalTimeString = hourFormat + hours + ":" + formatNull + minutes; 

     if(isSequence(finalTimeString)){ 
      count += 1; 

     } 

    } 

    System.out.println(count); 

} 

public static boolean isSequence(String time){ 

    String firstDig = time.split(":")[0]; 
    String secondDig = time.split(":")[1]; 



    ArrayList<Integer > foo = new ArrayList<Integer>(); 

    if(firstDig.length() >= 2){ 
if(firstDig.charAt(0) != '0'){ 
     foo.add(Integer.parseInt(String.valueOf(firstDig.charAt(0)))); 
    } foo.add(Integer.parseInt(String.valueOf(firstDig.charAt(1)))); 
    } 

    if(secondDig.length() >= 2){ 
     foo.add(Integer.parseInt(String.valueOf(secondDig.charAt(0)))); 
     foo.add(Integer.parseInt(String.valueOf(secondDig.charAt(1)))); 
    } 

    ArrayList<Integer> bar = new ArrayList<Integer>(); 

    int prev = foo.get(0); 


    for(int i = 1; i < foo.size(); i++){ 


    bar.add(foo.get(i) - prev); 
     prev = foo.get(i); 
    } 




    boolean isDiff = false; 

    int prevDifference = bar.get(0); 

    for(int i = 1; i < bar.size(); i++){ 
     if(prevDifference == bar.get(i)){ 

     }else{ 

      isDiff = true; 

     } 

     prevDifference = bar.get(i); 

    } 

    return !isDiff; 

} 

}

я не могу получить что-нибудь более 0,8 секунды, а сейчас им удара 2,0 секунды. Если бы кто-нибудь мог предложить что-нибудь, это было бы здорово. Приветствия.

// обновление, поэтому я думаю, что я правильно отформатировал код сейчас. Эта программа берет ввод за считанные минуты, добавляет его к часам 12 часов и подсчитывает, сколько особых времен есть. Особое время, например: 12:43, 02:46 (по существу время, когда цифры имеют общую разницу);

Answer 1

Несколько вещей, которые я замечаю сразу:

Во-первых, вы вызываете isSequence в цикле. isSequence сам имеет две петли. Таким образом, этот алгоритм равен O(d * (foo.size() + bar.size()). Фактически, мы могли бы сказать, что это Theta(d * (foo.size() + bar.size()) (т. Е. Всегда именно такая сложность), поскольку на самом деле нет возможности сделать это менее, чем d * (foo.size() + bar.size()) шагов. (Для записи, да, я понимаю, что я не строго точен с обозначением, потому что кратные n просто сводят к n, но я думаю, что писать это так полезно). Вероятно, это одна из основных причин, по которой она медленна для больших ресурсов. Вы можете подумать о том, как попытаться уменьшить это.

Мое упоминание о том, что существует только столько, что вы можете сделать с точки зрения оптимизации кода, если вычислительная сложность вашего базового алгоритма слишком высока.

Во-вторых, в качестве оптимизации:

for(int i = 1; i < bar.size(); i++){ 
    if(prevDifference == bar.get(i)){ 
     // You don't actually do anything here 
    }else{ 
     // Why not break out the loop here? There's no possibility of this 
     // becoming false later. That could save you some steps. 
     isDiff = true; 
    } 

    prevDifference = bar.get(i); 
} 

Наконец, почему вы не можете комбинировать ваш для петель в isSequence?

Answer 2

Отказ: насколько я могу судить, ваш код в настоящее время дает неправильный ответ. Вам нужно это исправить. Но вы спросили, как заставить его работать быстрее, а не как его исправить, так вот что я отвечаю.

Вы выполняете много форматирования и разбора строк, и многое из этого в вашем основном цикле. Сколько раз вы переходите от String к int и int к String? Все, что происходит взад и вперед, значительно замедляет процесс.

Если ваши минуты 2 цифры, вы можете получить последнюю цифру с minutes % 10. Вы можете получить первую цифру с minutes/10. То же самое с часами. Нет строкового анализа. Этого уже достаточно, чтобы сократить время ниже необходимого.

Но есть еще кое-что, что вы можете сделать, это еще лучше. Вместо того, чтобы ваш код выполнялся в O (n) времени, вы можете заставить его работать в том, что является эффективным временем O (1). Да, Вы прочли это правильно. Для больших n вы можете выполнить этот запуск в постоянное время.

Обратите внимание, что существует только так много возможных комбинаций часов и минут в день. Если вы используете 12-часовое время, то 12 * 60 = 720. Вы можете воспользоваться этим. Все, что вам нужно для обработки - это ответ на 720, и ответ за n % 720, а затем выполните небольшую математику. answer(n) является answer(720) * n/720 + answer(n % 720).Используя это, вы можете более или менее мгновенно вычислить любое значение до 2147483647. Черт, если вы использовали long вместо int, вы могли бы более или менее мгновенно вычислить любое значение до 9223372036854775807. (Подумайте об этом - ответ за 72000000 идет чтобы быть точно в 100000 раз ответом на 720, потому что одни и те же номера просто повторяются, так зачем беспокоиться об этом 72000000 раз?)