1

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 #1 = 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) { //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)

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

5
  • hashCode() is an overridden method. Why not remove it, recompile the code, and test it yourself?
    – Dan O
    Jun 13, 2013 at 21:04
  • @orzechowskid removing hashCode() will break the code for the given purpose.
    – Nishant
    Jun 13, 2013 at 21:10
  • 1
    The differences in the timing seem negligible to me. There are so many other factors that could go into the timings. Perhaps you re-ran your experiment and got consistent results. But even that is not a guarantee of whether one implementation is faster in the long run, because sometimes the HotSpot compiler needs to "warm-up" over time before it applies optimizations. So you really need to refactor your code so that you may apply a micro-benchmarking tool like Google's Caliper. Jun 13, 2013 at 21:38
  • That said, some of the suggestions about Strings are probably applicable anyway. But the warning should be to not trust rough timings like the one you made as a true measure of large-scale performance comparison. Jun 13, 2013 at 21:43
  • @KevinWelker Thanks for the insights. I'll try Caliper.
    – Nishant
    Jun 13, 2013 at 21:47

2 Answers 2

2

String are objects in Java and String concatenation is always an issue for performance if not carefully handled and especially in a large loop etc. I believe that the difference might be this line of code

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

why? Because Java String are immutable objects. i.e. when you concatenate these strings you are actually implicitly creating new String Object. In the second instance the Database Object created once holds for both values. All the other issues that could arise from Hashcode or Equals are really very well handled by compilers in terms of optimization so there should be no issues there.

Do a test a validate that concatenation provides the performance hit and read more about Java String Immutability

2
  • 1
    Yup, that's my prime suspect as well.
    – fge
    Jun 13, 2013 at 21:27
  • 1
    ya got it changing String key=ID+""+SC to int key = 31*(ID+17*SC) improved running time to 2.71 sec :-) Thanks for pointing it out.
    – Nishant
    Jun 13, 2013 at 21:32
0

Typically you use a profiler to figure out where code is spending its time. For Java, VisualVM is a good, free, cross-platform choice. Why don't you try running each in a profiler and comparing the results?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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