在不到 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 and here。同样，问题出在测试 7 上。

Answer 1

免责声明，我说我可以帮助你，我是，但我不能解决它给你。我没能把它限制在 2 秒以内，因为我没有正确理解问题本身。从技术上讲，我理解你的算法的作用，但我在概念上理解它时遇到问题，使我无法找到大优化。我找到了大优化。请参阅答案底部。

备注：我在测试页上看到了你的小测试结果，你的第一个测试绝对没有理由超过 200 毫秒。我只是不明白。在我的计算机上，它们都运行ning 始终低于 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]);
  }
  ...
}

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

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。不知道哪个更好

您的代码中有错误

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

在最后一个循环中，求和循环中，您将所有内容都存储在 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;
}

尽情享受吧！

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

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

Read 600,000 input from the console in less than 2 seconds

java

performance

time

execution-time

目标

Little Girl and Maximum Sum

问题

代码

测试结果

算法

正在读取数据

小优化

您的代码中有错误

找到了！