Java程序执行计时求助：相同输入下计时结果不一致

嘿，我来帮你搞定这个KMP算法执行时间不稳定的问题！首先得明白为啥相同输入每次跑出来时间不一样——这主要是Java虚拟机（JVM）的特性和系统环境波动导致的：

• JIT即时编译：第一次运行代码时，JVM是逐行解释执行字节码，等运行几次后，它会把频繁调用的热点代码编译成机器码，速度就会变快，这就导致第一次和后续运行的时间差很大。
• 系统资源抢占：你的电脑同时可能在跑其他程序，操作系统会调度CPU资源给不同进程，这也会影响单次运行的耗时。
• 垃圾回收（GC）：程序运行过程中可能触发垃圾回收，这会额外占用时间，而且GC的触发时机是不确定的。

接下来给你具体的解决方案和修正后的代码：

核心解决思路 #

1. 预热JVM：正式计时前先跑一次KMP匹配，让JVM把热点代码编译好，这样正式计时的时候就已经是优化后的执行速度了。
2. 多次运行取平均：如果想要更稳定的结果，可以多跑几次然后算平均时间，抵消单次运行的波动。
3. 修复代码小bug：你原来的代码里创建BufferedReader时多了一个括号，会编译报错，我已经帮你修正了。

修正后的完整代码 #

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

/** Class KnuthMorrisPratt **/
public class Knuth1 {
    /** Failure array **/
    private int[] failure;

    /** Constructor **/
    public Knuth1(String text, String pat) {
        /** Pre-construct failure array for the pattern **/
        failure = new int[pat.length()];
        fail(pat);
        /** Find match **/
        int pos = posMatch(text, pat);
        if (pos == -1)
            System.out.println("\nNo match found");
        else
            System.out.println("\nMatch found at index " + pos);
    }

    /** Failure function for the pattern **/
    private void fail(String pat) {
        int n = pat.length();
        failure[0] = -1;
        for (int j = 1; j < n; j++) {
            int i = failure[j - 1];
            while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0)
                i = failure[i];
            if (pat.charAt(j) == pat.charAt(i + 1))
                failure[j] = i + 1;
            else
                failure[j] = -1;
        }
    }

    /** Function to find pattern match **/
    private int posMatch(String text, String pat) {
        int i = 0, j = 0;
        int textLength = text.length();
        int patternLength = pat.length();
        while (i < textLength && j < patternLength) {
            if (text.charAt(i) == pat.charAt(j)) {
                i++;
                j++;
            } else if (j == 0)
                i++;
            else
                j = failure[j - 1] + 1;
        }
        return (j == patternLength) ? (i - patternLength) : -1;
    }

    /** Main Function **/
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Knuth Morris Pratt Test\n");
        
        System.out.println("Enter Text: ");
        String text = br.readLine();
        System.out.print("\nEnter Pattern: ");
        String pattern = br.readLine();

        // 预热JVM：先运行一次，让JIT编译热点代码
        System.out.println("\n--- 预热运行 ---");
        new Knuth1(text, pattern);

        // 正式运行并计时
        System.out.println("\n--- 正式计时运行 ---");
        long startTime = System.nanoTime();
        Knuth1 kmp = new Knuth1(text, pattern);
        long endTime = System.nanoTime();

        double executionTime = (endTime - startTime) / 1_000_000_000.0;
        System.out.print("Execution Time = ");
        System.out.format("%.4f", executionTime);
        System.out.println(" Seconds");

        // 可选：多次运行取平均，结果更稳定
        int runTimes = 5;
        long totalTime = 0;
        System.out.println("\n--- 多次运行取平均（" + runTimes + "次） ---");
        for (int k = 0; k < runTimes; k++) {
            long start = System.nanoTime();
            new Knuth1(text, pattern);
            long end = System.nanoTime();
            totalTime += (end - start);
        }
        double avgExecutionTime = (double) totalTime / runTimes / 1_000_000_000.0;
        System.out.printf("Average Execution Time = %.4f Seconds%n", avgExecutionTime);
    }
}

额外说明 #

• 我把startTime和endTime改成了long类型，比double更适合存储纳秒级时间，避免精度损失。
• 预热步骤很关键，它能消除JIT编译带来的时间差异，让正式计时的结果更稳定。
• 如果你的测试文本和模式很小，执行时间可能太短，波动会更明显，这时候用多次运行取平均的效果会更好。

内容的提问来源于stack exchange，提问作者JAMES ADAKOLE