Как я могу уменьшить время выполнения? - PullRequest
Новая
       4

Как я могу уменьшить время выполнения?

0 голосов
/ 03 марта 2020

Мне нужен этот код для запуска менее 0,15 секунд. вот код: 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int k=s.nextInt();
        for(int i=0;i<k;i++) {
            for(int j=1; j<=(n-i); j++)System.out.print(" ");
            for(int j=1;j<=((2*i)+1);j++) System.out.print("*");
            System.out.println();
        }
        for(int i=k; i<=n;i++) {
            for(int j=1; j<=(n-i); j++)System.out.print(" ");
                for(int j=1;j<=k;j++)System.out.print("*");
                for(int j=1;j<=((2*(i-k))+1);j++)System.out.print(" ");
                for(int j=1;j<=k;j++)System.out.print("*");
         System.out.println();
        }

        for(int i=(n-1); i>=k;i--) {
            for(int j=1; j<=(n-i); j++)System.out.print(" ");
                for(int j=1;j<=k;j++)System.out.print("*");
                for(int j=1;j<=((2*(i-k))+1);j++)System.out.print(" ");
                for(int j=1;j<=k;j++)System.out.print("*");
                System.out.println();
        }
            for(int i=(k-1);i>=0;i--) {
                for(int j=1; j<=(n-i); j++)System.out.print(" ");
                for(int j=1;j<=((2*i)+1);j++) System.out.print("*");
                System.out.println();
            }
    }

}

и это пример ввода и вывода. 

input:
n=10
k=3
output:
          *
         ***
        *****
       *** ***
      ***   ***
     ***     ***
    ***       ***
   ***         ***
  ***           ***
 ***             ***
***               ***
 ***             ***
  ***           ***
   ***         ***
    ***       ***
     ***     ***
      ***   ***
       *** ***
        *****
         ***
          *

какие изменения я могу внести в него, чтобы сделать это? я провел так много времени, думая об этом, но это ни к чему не привело. .................................................. ................................................

Ответы [ 4 ]

1 голос
/ 03 марта 2020

Возможно, вы захотите попробовать с StringBuilder и StringUtils сделать заполнение строк для вас, что-то вроде этого: 

public static void print2(int n, int k) {
    StringBuilder output = new StringBuilder();

    for (int i = 0; i < k; i++) {
        output.append(StringUtils.leftPad("", n-i,' '));

        output.append(StringUtils.leftPad("", 2*i+1,'*'));
        output.append(System.lineSeparator());
    }
    for (int i = k; i <= n; i++) {
        output.append(StringUtils.leftPad("", n-i,' '));
        output.append(StringUtils.leftPad("", k,'*'));
        output.append(StringUtils.leftPad("", 2*(i-k)+1,' '));
        output.append(StringUtils.leftPad("", k,'*'));
        output.append(System.lineSeparator());
    }

    for (int i = (n - 1); i >= k; i--) {
        output.append(StringUtils.leftPad("", n-i,' '));
        output.append(StringUtils.leftPad("", k,'*'));
        output.append(StringUtils.leftPad("", 2*(i-k)+1,' '));
        output.append(StringUtils.leftPad("", k,'*'));
        output.append(System.lineSeparator());
    }
    for (int i = (k - 1); i >= 0; i--) {
        output.append(StringUtils.leftPad("", n-i,' '));
        output.append(StringUtils.leftPad("", 2*i+1,'*'));
        output.append(System.lineSeparator());
    }

    System.out.println(output.toString());
}

посмотрите, что это та же самая логика c вы было. Для дальнейшего улучшения вам необходимо переработать алгоритм. На моем виртуальном хосте он работает примерно в 5 раз быстрее.

1 голос
/ 03 марта 2020

На моей машине ваш код достаточно быстр, но есть некоторые улучшения, которые вы можете сделать:

Первым улучшением будет не печатать каждый символ отдельно, а вместо этого использовать java.lang.StringBuilder: 

        public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("type n:");
        int n = s.nextInt();
        System.out.println("type k:");
        int k = s.nextInt();
        long starttime = System.currentTimeMillis();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < k; i++) {
            for (int j = 1; j <= (n - i); j++)
                stringBuilder.append(' ');
            for (int j = 1; j <= ((2 * i) + 1); j++)
                stringBuilder.append('*');
            stringBuilder.append('\n');
        }
        for (int i = k; i <= n; i++) {
            for (int j = 1; j <= (n - i); j++)
                stringBuilder.append(' ');
            for (int j = 1; j <= k; j++)
                stringBuilder.append('*');
            for (int j = 1; j <= ((2 * (i - k)) + 1); j++)
                stringBuilder.append(' ');
            for (int j = 1; j <= k; j++)
                stringBuilder.append('*');
            stringBuilder.append('\n');
        }

        for (int i = (n - 1); i >= k; i--) {
            for (int j = 1; j <= (n - i); j++)
                stringBuilder.append(' ');
            for (int j = 1; j <= k; j++)
                stringBuilder.append('*');
            for (int j = 1; j <= ((2 * (i - k)) + 1); j++)
                stringBuilder.append(' ');
            for (int j = 1; j <= k; j++)
                stringBuilder.append('*');
            stringBuilder.append('\n');
        }
        for (int i = (k - 1); i >= 0; i--) {
            for (int j = 1; j <= (n - i); j++)
                stringBuilder.append(' ');
            for (int j = 1; j <= ((2 * i) + 1); j++)
                stringBuilder.append('*');
            stringBuilder.append('\n');
        }
        System.out.println(stringBuilder.toString());
        long endtime = System.currentTimeMillis();
        System.out.println("UsedTime : " + ((endtime - starttime) * 0.001) + "s");
}

Если этого недостаточно, вам придется изменить алгоритм рисования, если это так, пожалуйста, оставьте комментарий. Затем я тоже посмотрю на алгоритм.

Хорошо, я знаю, что проверил несколько вещей:

Это закончилось в следующие "эталонные" времена (в среднем за 10 000 запусков):

оригинал: 0.001223081 с (в 319.17562630480165 раз медленнее, чем самый быстрый)

строитель: в 6.977200000000001E-5s (18.207724425887264 раз медленнее, чем самый быстрый)

myCode: 3.832E-6s ( самый быстрый)

TomSCode: 7,3558E-5 с (в 19,19572025052192 раза медленнее самого быстрого)

Код TomS является предлагаемым решением из этого ответа: { ссылка }

Как видите, следующий код был немного быстрее, чем приведенный выше, но я понятия не имею, почему это так ... 

    private static long paintMyCode(int n, int k) {
        long starttime = System.nanoTime();
        StringBuilder stringBuilder = new StringBuilder();
        for (int y = 0; y <= n * 2; y++) {
            int Δy = Math.abs(n - y);
            for (int x = 0; x <= n * 2; x++) {
                int d = Δy + Math.abs(n - x);
                if (d <= n && n - k < d) {
                    stringBuilder.append('*');
                } else {
                    stringBuilder.append(' ');
                }
            }
            stringBuilder.append('\n');
        }
        long endtime = System.nanoTime();
        System.out.println(stringBuilder);
        return endtime - starttime;
    }
0 голосов
/ 03 марта 2020

Использование BufferedReader вместо Scanner значительно повышает производительность вашей программы и для вывода вместо использования System.out.print каждый раз создает StringBuilder и добавляет к нему результат и печатает последнюю строку только один раз.

0 голосов
/ 03 марта 2020

Вместо System.in передать входной файл в сканер

Scanner s c = новый сканер (новый файл ("input.txt"));

Сохранение ввода в файле input.txt

...