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

Question

目标

我正在解决 this问题:

Little Girl and Maximum Sum

The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of n elements (the elements of the array are indexed starting from 1); also, there are q queries, each one is defined by a pair of integers li, ri (1 ≤ li ≤ ri ≤ n). You need to find for each query the sum of elements of the array with indexes from li to ri, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

Input The first line contains two space-separated integers n (1 ≤ n ≤ 2·105) and q (1 ≤ q ≤ 2·105) — the number of elements in the array and the number of queries, correspondingly.

The next line contains n space-separated integers ai (1 ≤ ai ≤ 2·105) — the array elements.

Each of the following q lines contains two space-separated integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

对于测试 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

您可以 download a sample input file ，或者您可以创建自己的示例输入。数字本身并不重要。

问题

我需要在不超过 2 秒的执行时间的情况下读取 600,000 行输入。问题是，它甚至没有在 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);
    }
}

这是我的第二次尝试:

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();
        }
    }
}

检测结果

尝试 1

7 Time: 2000 ms, memory: 20612 KB Verdict: TIME_LIMIT_EXCEEDED

尝试 2

7 Time: 2000 ms, memory: 41340 KB Verdict: TIME_LIMIT_EXCEEDED

您可以查看我的完整测试结果 here和 here .同样，问题出在测试 7 上。

Answer 1

免责声明，我说我能够帮助你，我是，但我不能为你解决。我无法将其限制在 2 秒以内，因为我没有正确理解问题本身。我理解你的算法在技术上的作用，但我在概念上理解它有问题，这让我无法找到 大优化。我发现了很大的优化。见答案底部。

备注:我已经在测试页面上看到了较小测试的结果，并且绝对没有理由为什么您的第一次测试持续 200+ 毫秒。我就是不明白。它们在我的计算机上的运行时间始终低于 2 毫秒(使用 Java 内部 System.nanotime() 方法)。我相信测试包括JVM的启动。如果确实如此，我是否建议您改用更优化的语言，例如 C 或 C++ ?这意味着该测试在某种程度上是针对解释性语言的。

算法

第一个问题是你的算法本身。它很慢:您实际上是在迭代 200,000 × x int s(这是您文件中的平均高值)。在最坏的情况下，您将迭代 200,000 × 200,000 = 40,000,000,000 个整数。难怪你有 20 秒左右的时间。

那太过分了。理想情况下，您应该能够使用优化(例如使用 map )来减少双循环。您可以使用大量内存 (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]);
  }
  ...
}

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

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;
}

小优化

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

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

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

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

您的代码中有错误

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

在最后一个循环 sum 循环中，您将所有内容存储在 long 中，但实际上可能会出现 int 溢出。所以你应该像这样计算你的总和:

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

找到了!

关于您的代码，正如我所说，您遇到了问题，因为您可能会收到超过 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;
}

享受!

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