-6

Code 1:

private static int myCompare(String a, String b) {

    /* my version of the compareTo method from the String Java class */

    int len1 = a.length();
    int len2 = b.length();

    if (len1 == len2) { 

        for (int i = 0; i < a.length(); i++) { 

            int intValueOfStringA = (int) a.charAt(i); 
            int intValueOfStringB = (int) b.charAt(i); 

            if (intValueOfStringA != intValueOfStringB) {

                return intValueOfStringA - intValueOfStringB;
            }
        }
    }
    return len1 - len2;
}

Code 2:

private static int stringCompare(String a, String b) {

    /* Direct implementation of the compareTo from the String Java class */


    int len1 = a.length(); 
    int len2 = b.length();
    int lim = Math.min(len1, len2); 

    char[] v1 = a.toCharArray(); 
    char[] v2 = b.toCharArray(); 

    int k = 0;
    while (k < lim) { 
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) { 
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

Please ignore commenting on the type of access modifier used or the args made available to the method. I actually came up with Code 1 before being counseled by my friend to use the "compareTo" method from the String Class, which is reproduced here under Code 2. I wonder which piece of code is more effective though (w.r.t time and memory). Please advise.

I am trying to understand the Big O for both the code blocks and trying to elegantly improve efficiency. IMO Code 2 is relatively costly w.r.t memory usage. I want to confirm this. I apologize if my question is possibly alluding to the classic micro-optimization Vs. readable code debate.

8
  • 2
    You should benchmark. Perhaps using the equal or compareTo method of the standard String class might be even faster (probably the compiler & JVM know it). Feb 5, 2017 at 8:01
  • Possible duplicate of Is micro-optimisation important when coding?
    – gnat
    Feb 5, 2017 at 8:29
  • The versions are not equivalent. Your version always returns -1 if the strings are of different length.
    – juhist
    Feb 5, 2017 at 9:30
  • 2
    I think CodeReview would be a better place for this, wouldn't it?
    – Artery
    Feb 5, 2017 at 9:59
  • @juhist yeah. Sorry, my bad. Forgot to mention that I intentionally designed it that way cuz I in the ensuing code (which is not reproduced above) I have a validation check very specific to length mismatch cases that is identified by checking for negative ones. Otherwise does it look ok? Feb 5, 2017 at 13:24

2 Answers 2

3

First: The two methods does two different things. stringCompare returns the alphabetic ordering of two strings which means it can be used to sort a set of strings alphabetically.

myCompare just returns -1 if the stings have different lengths, which means it can't be used for sorting. So comparing the performance of the methods does not make a lot of sense since they don't do the same thing.

For myCompare the behavior is so surprisingly different between strings of same length and strings of different length that I would consider it a bad design regardless of performance.

If you only want to compare strings for equality and don't care about sorting, then you should not compare the code to String.stringCompare() but rather String.equals() which have the same optimization for strings of different lengths.

Anyway, considering strings of the same length, both samples use the same basic algorithm for comparison, but the second sample copies the char arrays, which will require more memory. However both algorithms are O(n) operations, so the difference will be in constant factors like the possible overhead of calling length() multiple times and using charAt() rather than using array indexing. Such differences will depend on compiler and environment, so the only way you can find out is by benchmarking.

2
  • The second version allocate two new char arrays, which represents a memory difference, no?
    – Erik Eidt
    Feb 5, 2017 at 12:06
  • @ErikEidt: You are correct, I missed that. And while arraycopy is pretty fast, it is still O(n).
    – JacquesB
    Feb 5, 2017 at 12:35
1

Method 1 is quite efficient as far as execution time and memory usage are concerned. Unfortunately, it is completely useless, so efficiency doesn't help.

Method 2 is unnecessary inefficient for most pairs of strings, where probably the first or second character is already different, but you convert the complete strings to character arrays.

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