在不到2秒的时间内从控制台读取600,000输入

Question

在不到2秒的时间内从控制台读取600,000输入

Rob*_*ert 4 java performance time execution-time

目标

我正在解决这个问题:

小女孩和最大总和

小女孩非常喜欢阵列查询的问题.

有一天,她遇到了一个众所周知的问题:你有一个n个元素的数组(数组的元素从1开始索引); 另外,有q个查询,每个查询由一对整数li,ri(1≤li≤ri≤n)定义.您需要为每个查询找到具有从li到ri(包括)的索引的数组元素的总和.

小女孩发现问题相当无聊.她决定在回复查询之前重新排序数组元素,使查询回复的总和最大化.您的任务是找到此最大总和的值.

输入第一行包含两个空格分隔的整数n(1≤n≤2·105)和q(1≤q≤2·105) - 数组中的元素数和相应的查询数.

下一行包含n个空格分隔的整数ai(1≤ai≤2·105) - 数组元素.

以下q行中的每一行包含两个空格分隔的整数li和ri(1≤li≤ri≤n) - 第i个查询.

输出在单行中打印单个整数 - 重新排序数组元素后查询答复的最大总和.

使用测试7(请参阅问题末尾的测试结果),输入是一个大小为200,000且包含200,000个查询(具有r和l值)的数组.

输入看起来像这样:

200000 200000
189622 189286 194361 184457 182376 183471 197548 184736 195806 ... 200,000 integers

188738 290041
33738 90041
122738 390041
... 200,000 line

Run Code Online (Sandbox Code Playgroud)

您可以下载示例输入文件,也可以创建自己的示例输入.数字本身并不重要.

问题

我需要读取600,000条输入线,而不超过2秒的执行时间.问题是,它甚至没有在2秒内读取前200,000输入.

如何在2秒内加速我的代码读取所有600,000输入？

代码

这是我的第一次尝试:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] array = new int[n];
        for (int i=0; i<n; i++) {
            array[i] = scanner.nextInt();
        }
        int[][] qArray = new int[q][2];
        for (int i=0; i<q; i++) {
            qArray[i][0] = scanner.nextInt();
            qArray[i][1] = scanner.nextInt();
        }

        int[] index = new int[n];
        Arrays.sort(array);
        for (int i=0; i<q; i++) {
            for (int j = qArray[i][0]-1; j<qArray[i][1]; j++) {
                index[j]++;
            }
        }
        Arrays.sort(index);
        long sum =0;
        for (int i = 0; i<n; i++) {
            sum += index[i]*array[i];
        }
        System.out.println(sum);
    }
}

Run Code Online (Sandbox Code Playgroud)

这是我的第二次尝试:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        try {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            String input = bufferedReader.readLine();
            String[] SplitInput = input.split(" ");
            int n = Integer.parseInt(SplitInput[0]);
            int q = Integer.parseInt(SplitInput[1]);

            String input2 = bufferedReader.readLine();

            int[][] qArray = new int[q][2];
            for (int i=0; i<q; i++) {
                input = bufferedReader.readLine();
                SplitInput = input.split(" ");
                qArray[i][0] = Integer.parseInt(SplitInput[0]);
                qArray[i][1] = Integer.parseInt(SplitInput[1]);
            }

            String[] SplitInput2 = input2.split(" ");
            int[] array = new int[n];
            for(int i=0; i<n; i++){
                array[i] = Integer.parseInt(SplitInput2[i]);
            }

            int[] index = new int[n];
            Arrays.sort(array);
            for (int i=0; i<q; i++) {
                for (int j = qArray[i][0]-1; j<qArray[i][1]; j++) {
                    index[j]++;
                }
            }
            Arrays.sort(index);
            long sum = 0;
            for (int i=0; i<n; i++) {
                sum += index[i]*array[i];
            }
            System.out.println(sum);
        }
        catch (NumberFormatException ex) {
            System.out.println("Not a number !");
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Run Code Online (Sandbox Code Playgroud)

检测结果

尝试1

7时间:2000毫秒,内存:20612 KB判决:TIME_LIMIT_EXCEEDED

尝试2

7时间:2000毫秒,内存:41340 KB结论:TIME_LIMIT_EXCEEDED

您可以在此处和此处查看我的完整测试结果.同样,问题出在测试7上.

Answer 1

Oli*_*ire 6

免责声明,我说我能够帮助你,我,但我无法为你解决.我无法在2秒内限制它,因为我没有正确理解问题本身.我明白你的算法做了什么,从技术上说,但我有问题,从概念上理解它,让我无法找到的大优化.我发现了很大的优化.见答案的底部.

备注:我已经在测试页面上看到了较小测试的结果,并且绝对没有理由说您的第一次测试持续200+ ms.我只是不明白.它们在我的计算机上一直运行不到2毫秒(使用Java内部System.nanotime()方法).我相信测试包括JVM的启动.如果情况确实如此,我可以建议您切换到更优化的语言,如C或C++吗？这意味着测试在某种程度上违背了解释性语言.

算法

第一个问题是你的算法本身.它很慢:你实际上正在迭代200,000× x ints(这是一个很高的平均值,来自你的文件).在最坏的情况下,您将迭代200,000×200,000 = 40,000,000,000英镑.难怪你的时间大约是20秒.

这太过分了.理想情况下,您应该能够像使用地图一样使用优化来减少双循环.你有大量的内存(256 MB),使用它.你已经做到了; 做得更多.

最大的优化在于此处.我相信,不是通过索引递增索引,而是应该通过跳过此索引机制并使用更好的索引机制来找到另一个优化.我相信这就是为什么存在这个问题的原因:找到那个算法而不是其他算法.我不喜欢这样,但我不判断它.

读数据

我测试通过输入读取数据,你的方法很慢.我责怪你的使用Scanner.

我建议你使用这种结构和这种拆分方法,在我的计算机上使用你的大测试文件总计<100毫秒(我坚持......我的电脑不是你的电脑而我们的电脑不是你的测试评估的电脑) .我相信它可以进一步减少,但我会说它已经足够了.这不是我们正在寻找的重大优化,但我相信它是第二个.

try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
  int[] counts = split(reader.readLine(), new int[2]);
  int n = c[0], q = c[1];
  int[] array = split(reader.readLine(), new int[n]);
  int[][] queries = new int[q][]; // Note, no size in the second part of the array creation.
  for (int i = 0; i < q; i++) {
    queries[i] = split(reader.readLine(), new int[2]);
  }
  ...
}

Run Code Online (Sandbox Code Playgroud)

使用针对您的用例优化的适当拆分方法:

static int[] split(String s, int[] a) {
  int n = 0, aIndex = 0;
  for (int sIndex = 0, sLength = s.length(); sIndex < sLength; sIndex++) {
    char c = s.charAt(sIndex);
    if (c == ' ') { // Separator
      a[aIndex++] = n;
      n = 0;
    } else if ('0' <= c && c <= '9') { // Number
      n = n * 10 + (c - '0'); // Add a digit to the current number
    }
  }
  a[aIndex] = n;
  return a;
}

Run Code Online (Sandbox Code Playgroud)

小优化

从概念上讲,您有以下代码:

for (int i = 0; i < q; i++) {
  // Fill qArray
}

for (int i = 0; i < q; i++) {
  // Work with index.
}

Run Code Online (Sandbox Code Playgroud)

这两个循环可以合并,甚至可以消除你的需要qArray.您读取数据,然后直接处理它.如果循环彼此相邻,那么这并不重要,但是在您第一次尝试中对数组中的东西进行排序之间,并且您在第二次尝试中对数组进行排序并解析输入.这使得您的数据一方面远离CPU缓存,但您在另一方面处理I/O. 我不知道哪一个更好.

您的代码中存在错误

我试图重新思考这个问题并找到了解决方案,但你的答案与我的答案完全不同.我实际上在你的代码中发现了一个错误.我的文件无法获得与您相同的结果.

在你的最后一个循环中,sum-loop,你将所有东西存储在一个long中,但它实际上可以获得一个int溢出.所以你应该这样做你的总和:

sum += (long)(index[i]) * array[i];

Run Code Online (Sandbox Code Playgroud)

找到了!

关于你的代码,正如我所说,你有一个问题,因为你可能会得到超过400亿条指令.我可以用你在下面看到的内容来展平你的解决方案.我现在一直达到500毫秒.

public static void main(String[] args) throws IOException {
  long nanos = System.nanoTime();
  myMain();
  nanos = System.nanoTime() - nanos;
  System.out.printf("Time: %sms%n", MILLISECONDS.convert(nanos, NANOSECONDS));
}

static void myMain() throws IOException {
  try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
    int[] counts = split(reader.readLine(), new int[2]);
    int n = counts[0], q = counts[1];
    int[] array = split(reader.readLine(), new int[n]);
    int[] indices = new int[n];
    for (int i = 0; i < q; i++) {
      int[] query = split(reader.readLine(), new int[2]);
      indices[query[0] - 1]++;
      if (query[1] < n) {
        indices[query[1]]--;
      }
    }
    for (int i = 1; i < n; i++) {
      indices[i] += indices[i - 1];
    }
    sort(array, 200_000);
    sort(indices, 200_000);
    long sum = 0;
    for (int i = 0; i < n; i++) {
      sum += (long)array[i] * indices[i];
    }
    System.out.println(sum);
  }
}

static void sort(int[] array, int n) {
  int[] counts = new int[n+1];
  for (int element: array) {
    counts[element]++;
  }
  int current = 0;
  for (int i = 0; i < counts.length; i++) {
    Arrays.fill(array, current, current + counts[i], i);
    current += counts[i];
  }
}

static int[] split(String s, int[] a) {
  int n = 0, aIndex = 0;
  for (int sIndex = 0, sLength = s.length(); sIndex < sLength; sIndex++) {
    char c = s.charAt(sIndex);
    if (c == ' ') {
      a[aIndex++] = n;
      n = 0;
    } else if ('0' <= c && c <= '9') {
      n = n * 10 + (c - '0');
    }
  }
  a[aIndex] = n;
  return a;
}

Run Code Online (Sandbox Code Playgroud)

请享用!

如果您对此优化有任何疑问,请不要犹豫;)

归档时间：	10 年，1 月前
查看次数：	482 次
最近记录：	9 年，11 月前