java - 两个java代码的运行时间有很大差异

Question

在解决在线法官的问题时，我尝试了这两种实现。

这两个实现做同样的事情。任务是报告给定数据集的重复条目。

实现 #1:将输入数据转换为字符串并添加到 HashSet。读取所有输入后，将显示相应的消息。

class Databse2 {

public static void main(String[] args) throws Exception{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int t=Integer.parseInt(br.readLine());//number of test cases
    int N=0,R=0,C=1;
    while(t-->0){ //while there are more test cases
        HashSet<String> set=new HashSet<String>();
        StringTokenizer st=new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()){
            N=Integer.parseInt(st.nextToken());
            R=Integer.parseInt(st.nextToken());//Number of Rows of data
        }

        int ID=0,SC=0;boolean haha=true;
        for(int i=0;i<R;i++){ //for number of rows read each record in the row
            st=new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()){
                ID=Integer.parseInt(st.nextToken());
                SC=Integer.parseInt(st.nextToken());
            }
            String key=ID+""+SC;//convert to string,this combo is used to check for duplicates
            haha=haha && set.add(key);


        }
        if(haha)
            System.out.println("Scenario #"+C+": possible");
        else System.out.println("Scenario #"+C+": impossible");
        C++;
    }
}
}

运行时间 #1 = 3.41 秒(对于 N 个测试用例)

实现 #2:与实现 #1 完成相同的任务，但方式不同。根据输入类型创建一个对象并将其添加到 HashSet 中。

class Database {

private int ID;
private int SC;

public Database(int ID,int SC) {
    this.ID=ID;
    this.SC=SC;
}
@Override
public boolean equals(Object obj) {
    return (obj instanceof Database) ? ID==((Database)obj).ID:SC==((Database)obj).SC;
}

@Override
public int hashCode() {
    return 31*(ID+SC);
}

public static void main(String[] args) throws Exception {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int t=Integer.parseInt(br.readLine());
    int N=0,R=0,C=1;
    while(t-->0) { //while there are more test cases
        HashSet<Database> set=new HashSet<Database>();
        StringTokenizer st=new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()) {
            N=Integer.parseInt(st.nextToken());
            R=Integer.parseInt(st.nextToken());//Number of rows of input
        }
        int ID=0,SC=0;
        boolean haha=true;
        for(int i=0;i<R;i++) { //Read data for each row from input set
            st=new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()) {
                ID=Integer.parseInt(st.nextToken());
                SC=Integer.parseInt(st.nextToken());
            }
            haha=haha?set.add(new Database(ID, SC)):false;
        }
        String str=haha?"Scenario #"+C+": possible":"Scenario #"+C+": impossible";
        System.out.println(str);
        C++;
    }
}
}

运行时间 #2 = 2.74 秒(对于 N 个测试用例)

是什么导致实现 #2 更快？是hashCode方法吗？

Answer 1

字符串是Java中的对象，如果不仔细处理，字符串连接始终是性能问题，尤其是在大循环等中。我相信差异可能在于这行代码

String key=ID+""+SC;//convert to string,this combo is used to check for duplicates

为什么？因为Java String是不可变的对象。即，当您连接这些字符串时，您实际上是在隐式创建新的字符串对象。在第二个实例中，创建的数据库对象一次保存这两个值。编译器在优化方面确实很好地处理了 Hashcode 或 Equals 可能出现的所有其他问题，因此应该没有问题。

进行测试并验证串联是否会带来性能影响，并阅读有关 Java 字符串不变性的更多信息