1

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

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

实现 #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++;
    }
}
}

Running time #1 = 3.41 sec (for N number of test cases)

实施#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++;
    }
}
}

Running Time #2 = 2.74 sec (for N number of test cases)

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

4

2 回答 2

2

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

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

为什么？因为Java String 是不可变的对象。即，当您连接这些字符串时，您实际上是在隐式创建新的字符串对象。在第二种情况下，一次创建的数据库对象同时适用于这两个值。Hashcode 或 Equals 可能引起的所有其他问题都由编译器在优化方面处理得非常好，因此应该没有问题。

做一个测试来验证连接是否提供了性能冲击，并阅读更多关于 Java 字符串不变性的信息

于 2013-06-13T21:23:01.227 回答
0

通常，您使用分析器来确定代码在哪里花费时间。对于 Java，VisualVM是一个不错的、免费的、跨平台的选择。为什么不尝试在分析器中运行每一个并比较结果？

于 2013-06-13T21:10:30.633 回答