在Java中速度为什么会快，为什么有些代码运行得更快？

Question

我正在尝试解决 UVa 问题号为 10324 的问题，我编写了以下解决方案，虽然通过了测试，但运行时间非常糟糕，需要 2.670 秒。 我有以下两个代码： 这是我的代码：

    public static void main(String[] args) throws Exception{
        // write your code here
        StringBuilder op = new StringBuilder();
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader reader = new BufferedReader(isr);
            String input, tmp[];
            int n, l, u, j, i = 0;
            boolean dec;
            char thi;
            while ((input = reader.readLine()) != null) {
                op.append("Case " + (++i) + ":\n");
                n = Integer.parseInt(reader.readLine());
                while (n-- > 0) {
                    tmp = reader.readLine().split(" ");
                    l = Integer.parseInt(tmp[0]);
                    u = Integer.parseInt(tmp[1]);
                    if (l > u) {
                        l ^= u;
                        u ^= l;
                        l ^= u;
                    }
                    //System.out.println(l + "|" + u);
                    dec = true;
                    thi = input.charAt(l++);
                    for (; l <= u; l++) {
                        if (thi != input.charAt(l)||(thi != input.charAt(u--))) {
                            dec = false;
                            break;
                        }
                    }
                    op.append((dec ? "Yes\n" : "No\n"));
                }
            }
            System.out.print(op.toString());
            return;

    }
}

另外一段代码我在Mr Gorgon的解决方案中发现。这段代码的运行时间为0.84秒

public static void main(String[] args) throws Exception {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    StringBuilder sb = new StringBuilder("");
    int testCase = 1;
    String line;
    while ((line = br.readLine()) != null) {
        sb.append("Case ").append(testCase).append(":\n");
        testCase++;
        int noOfCases = Integer.parseInt(br.readLine());
        for (int j = 0; j < noOfCases; j++) {
            String[] str = br.readLine().split(" ");
            int val1 = Integer.parseInt(str[0]);
            int val2 = Integer.parseInt(str[1]);
            if (val1 > val2) {
                val1 ^= val2;
                val2 ^= val1;
                val1 ^= val2;
            }
            boolean isValid = true;
            if (val1 != val2) {
                for (int i = val1; i < val2; i++) {
                    if (line.charAt(i) != line.charAt(i + 1)) {
                        isValid = false;
                        break;
                    }
                }
            }
            if (isValid)
                sb.append("Yes\n");
            else
                sb.append("No\n");
        }
    }
    System.out.print(sb);
}

我觉得很难理解为什么这段代码在所有任务本质相同的情况下运行得如此之快，而我的代码比Gorgon的代码声明更少。

- Shubham Arawkar

---

声明并不会增加太多的性能开销，事实上（我也没有看到你真正减少了任何声明...） - Adrian Shum

我创建了一些测试用例，其中包括几个非常长的字符串和许多较短的字符串，并在本地运行了两个版本（Windows 和 Linux，JDK8），你的版本大约快了2倍。了解他们（UVa）实际的测试用例和他们使用的 Java 运行时将是很有趣的。 - starikoff

Answer 1

• op.append("第 " + (++i) + " 个案例：\n");

这将抵消 StringBuilder 的优点。

• if (val1 != val2) { 在第二个版本中可以缩短循环时间。

- Scary Wombat

---

你的第二点是无效的。如果两个值相同，OP的循环条件也不会进入循环。 - Klitos Kyriacou

尝试进行更改，但仍然得到相同的时间。 - Shubham Arawkar

Answer 2

its the

input.charAt(l)!=input.charAt(l+1)

我认为有一种方法可以加速程序，它与缓存有关。

我进行了研究，并发现了一个叫做JCS的东西，它可能允许他们的Apache服务器缓存内存数据并帮助更快地访问。

- Shubham Arawkar

---

JCS与此无关，但您正确地指出，与您的版本相比，这行代码使代码运行显着更快。 - starikoff

Answer 3

你的解决方案中缺少以下代码。你正在盲目循环，而 if 条件限制了循环。

if (val1 != val2) {
                                    }
            }

- Vineet Kasat