1

オンラインジャッジの問題を解決しながら、これらの 2 つの実装を試してみました。

これら 2 つの実装は同じことを行います。タスクは、特定のデータ セットの重複エントリを報告することです。

実装 #1 : 入力データを String に変換し、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 は不変オブジェクトであるためです。つまり、これらの文字列を連結すると、実際には暗黙的に新しい文字列オブジェクトが作成されます。2 番目のインスタンスでは、一度作成されたデータベース オブジェクトが両方の値を保持します。Hashcode または Equals から発生する可能性のある他のすべての問題は、最適化に関してコンパイラによって非常に適切に処理されるため、問題は発生しないはずです。

連結がパフォーマンス ヒットを提供することを検証するテストを実行し、Java 文字列の不変性に関する詳細を読む

于 2013-06-13T21:23:01.227 に答える
0

通常、プロファイラーを使用して、コードがどこで時間を費やしているかを把握します。Java の場合、VisualVMは優れた無料のクロスプラットフォームの選択肢です。それぞれをプロファイラーで実行して結果を比較してみてはいかがでしょうか。

于 2013-06-13T21:10:30.633 に答える