1
\$\begingroup\$

While solving a problem on an online judge, I tried with these two implementations.

These two implementations do the same thing. Task is to report duplicate entry for a given set of data.

Implementation #1 : Converts input data to a String and adds to a HashSet. After all the input is read, appropriate message is displayed.

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 = 3.41 sec (for N number of test cases)

Implementation #2: Same task is accomplished as in Implementation #1 but in a different way. An object is created based on input type and added to 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){
        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());
        }
        int ID=0,SC=0;boolean haha=true;
        for(int i=0;i<R;i++){
            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)

What causes implementation #2 to be faster? Is it the hashCode method?

\$\endgroup\$
  • 3
    \$\begingroup\$ I'd say it's the string concatenation in version 1. Not sure though. You may want to give a try at caliper for being sure. \$\endgroup\$ – fge Jun 13 '13 at 19:38
  • 1
    \$\begingroup\$ Did you do multiple runs of each? If not, i would do that then compare the mean times to each. \$\endgroup\$ – DFord Jun 13 '13 at 23:16
1
\$\begingroup\$
  1. String.equals() compare their char[] inside, which is slower than simply compare two ints.
  2. String concatenation is slower than creating a Database.
  3. String.hashcode() is just like its equals.

Note that your implementation of Database.equals is incorrect, though you're lucky this time.

@Override
public boolean equals(Object obj) {
    return (obj instanceof Database) && ID == ((Database)obj).ID &&
            SC == ((Database)obj).SC;
}

The hashcode implementation is only a suggestion.

@Override
public int hashCode() {
    return 31 * (31 * 17 + ID) + SC;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ String.hashCode() uses a precalculated hashCode so this is not any slower that comparing integers. \$\endgroup\$ – Uwe Plonus Jun 14 '13 at 6:08
  • \$\begingroup\$ @UwePlonus But it still calculate it once, and because hashcode cache the result, I put it at the third cause. \$\endgroup\$ – johnchen902 Jun 14 '13 at 8:01
  • \$\begingroup\$ @johnchen902 thanks for pointing out incorrect equals implementation. \$\endgroup\$ – Nishant Jun 14 '13 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.