Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Here is the code for the CString class that I created.

public class CString {

    public String reverse(String s) {
        char[] array = new char[s.length()];
        array = s.toCharArray();
        for(int i=0; i<array.length/2; i++) {
            char tmp = array[i];
            array[i] = array[array.length-1-i];
            array[array.length-1-i] = tmp;
        }
        return charArrayToString(array);
    }

    public String charArrayToString(char[] array) {
        StringBuffer sb = new StringBuffer();
        sb.append(array);
        return sb.toString();
    }
}

Is there any bug in the code? Are there more efficient ways to reverse a string?

share|improve this question
5  
Have you not checked for bugs yourself? We are not a debugging service. We review working code. –  Jamal Feb 27 at 21:24
1  
Yes, it passed some simple tests. –  Jane Foster Feb 27 at 21:25
    
Okay, just making sure. The second question is good, and we can help with that. –  Jamal Feb 27 at 21:26

3 Answers 3

up vote 29 down vote accepted

Reversing a string, accurately and efficiently.

You are doing it accurately, yes. But, not very efficiently (although there are worse ways to do things).

NOTE:: Palacsint is right that you are not handling null input and surrogate-pairs in the input data. Your solution is not completely accurate. Consider this answer a discussion the efficiency only.... though I have also updated this answer to include a solution which deals with surrogate pairs efficiently

To understand the efficiency side of things, you have to understand Java String internals.

  • Strings are immutable, cannot be changed.
  • Java is relatively slow at allocating/cleaning memory, try to avoid it.
  • Java can 'inline' method calls and make methods really fast.

So, the best way to make Java efficient is to create/use as little memory as possible, and still end up with a new String (instead of changing an existing string).

Your code has 1 string already, you are creating another string. You cannot avoid that.

What you can avoid though is what happens in between.

Your 'In Between'

What you are doing in between is a bit messy, and wasteful:

    char[] array = new char[s.length()];
    array = s.toCharArray();

You create a new array, then you throw it away, and replace it with the s.toCharArray()... why?

Could be just:

    char[] array = s.toCharArray();

Also, you have a loop that swaps the chars... this is implemented like:

for(int i=0; i<array.length/2; i++) {

This could be faster if you did it backwards ( could be - depending on which Java you use).

for (int i = array.length / 2; i >= 0; i--) {

This way it only has to do the array.length / 2 one time (though, as I say, some Java implementations will perhaps compile it to work out for you).

Finally, the charArrayToString() is serious overkill....

Converting to a StringBuilder then to a String is a waste of time/resources...

return charArrayToString(array);

can be

return new String(array);

EDIT: Also, as has been mentioned by Richard Miskin... and I assumed you were already using a StringBuilder .... StringBuilder is much more efficient in a single-thread situation than StringBuffer. Unless you have good reason, you always should use StringBuilder.

Efficient in-between ....

public String reverse(String s) {
    char[] array = s.toCharArray();
    char tmp;
    for(int i=array.length/2; i >= 0; i--) {
        tmp = array[i];
        array[i] = array[array.length-1-i];
        array[array.length-1-i] = tmp;
    }
    return new String(array);
}

Edit: a different way:

Here are some performance numbers...

String Reverse                           => 4473870 (hot 19.74881ms)
String Reverse Surrogate Aware           => 4473870 (hot 22.73488ms)
String Reverse B                         => 4473870 (hot 25.16192ms)
String Reverse StringBuilder             => 4473870 (hot 31.60709ms)
String Reverse StringBuilder NoNullCheck => 4473870 (hot 31.72952ms)
String Reverse Orig                      => 4473870 (hot 36.83827ms)

For each of those 'hot' runs, I am reversing the order of 479829 words (linux.words) (and there are 4473870 characters in the data excluding newlines).

  • the code I suggested above as the 'efficient in-between' does it in 20 milliseconds

  • based on the discussion about null and Surrogate Pairs, the following code does this 'right', and runs in 23 milliseconds:

    public String reverse(final String s) {
        if (s == null) {
            return null;
        }
        final char[] array = s.toCharArray();
        char tmp;
        for(int i=array.length/2; i >= 0; i--) {
            tmp = array[i];
            array[i] = array[array.length-1-i];
            array[array.length-1-i] = tmp;
        }
        //surrogte pairs will have been swapped.
        //identify, and un-swap them.
        for (int i = 1; i < array.length; i++) {
            if (Character.isHighSurrogate(array[i]) && Character.isLowSurrogate(array[i - 1])) {
                tmp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = tmp;
            }
        }
        return new String(array);
    }
    
  • The following code does it in 25 milliseconds

    public String reverse(String s) {
        char[] array = new char[s.length()];
        for(int i=array.length - 1, j = 0; i >= 0; i--, j++) {
            array[i] = s.charAt(j);
        }
        return new String(array);
    }
    
  • @palacsint's recommendation does it in 31 milliseconds:

    public static String reverse(final String str) {
        if (str == null) {
            return null;
        }
        return new StringBuilder(str).reverse().toString();
    } 
    
  • @palacsint's recommendation (without the null-check) does it in 31 milliseconds:

    public static String reverse(final String str) {
        return new StringBuilder(str).reverse().toString();
    } 
    
  • Your code does it in 37milliseconds.

If you look at the code, my code creates three objects (char[] and new String() (which creates char[] as well))

The s.charAt() code also creates three objects, but has a lot of calls to String.charAt().

The @palacsint recommendation creates 4 objects (StringBuffer, StringBuffer's internal char[], String, and String's internal char[]);

That is true with and without the null-check.

Your code creates 5 objects (6 if you count the first array which is likely to be compiled out...) : (char[] array, new StringBuffer, StringBuffer's char[], String, and String's char[])

My guess is that there is a close correlation between our times simply because it takes 5ms to create 480,000 objects on the heap, plus some overhead of actual work.

share|improve this answer
4  
"Java is relatively slow at allocating/cleaning memory, try to avoid it." Fast memory allocation (i.e. memory retrieving by the VM) is not one of the key points of a GC-based system and managed-by-vm memory systems in general? As far I know, "allocating" memory in Java-like languages is pretty fast because there is no "true" allocation (i.e. calling a heap allocator to retrieve new chunks/pages of free memory), only is the VM retrieving you some piece of a larg amount of memory it allocated previously to avoid calling the slow "mallocs" continuously. –  Manu343726 Feb 27 at 22:24
4  
Also, GCs are not slow at collecting, they are pretty fast nowadays. The only problem is the indeterministic way they works (i.e. "I don't know when the GC would stop my program to perform the collecting"), which could be a problem in realtime systems (like videogames). –  Manu343726 Feb 27 at 22:25
2  
@Manu343726 - both your points are valid, but out of context for this discussion. What I am saying is 'using the heap (whether pre-malloc'd or not) is slower than not using the heap.'. Not having to GC some memory is faster than the alternative. –  rolfl Feb 27 at 23:20
1  
Edited the answer to include some comparative performance results. –  rolfl Feb 27 at 23:21
    
@rolfl: +1, and hope you get a lot more +1's, too. Though Java isn't my language, I accidentally found this question (flag queue). I had to up-vote, if only for the effort that has clearly gone into this. Nice to see a CR answer that actually bothers with both the code and the reasons why –  Elias Van Ootegem Feb 28 at 9:51

Learn from the existing implementations, they usually have solutions to corner cases and common pitfalls. For example, Apache Commons Lang StringUtils also has a reverse function. It's implementation is quite simple:

public static String reverse(final String str) {
    if (str == null) {
        return null;
    }
    return new StringBuilder(str).reverse().toString();
} 

It uses StringBuilder.reverse whose javadoc mentions some special cases:

If there are any surrogate pairs included in the sequence, these are treated as single characters for the reverse operation. Thus, the order of the high-low surrogates is never reversed.

Here are a few tests:

@Test
public void testCstring() {
    assertEquals("\uD800\uDC00", CString.reverse("\uD800\uDC00")); // fails
    assertEquals("\uD800\uDC00", CString.reverse("\uDC00\uD800")); // OK
}

@Test
public void testStringUtils() throws Exception {
    assertEquals("\uD800\uDC00", StringUtils.reverse("\uD800\uDC00"));
    assertEquals("\uD800\uDC00", StringUtils.reverse("\uDC00\uD800"));
}

I don't know too much about these surrogates but you should check it and handle them in your code. I suppose the JDK's implementation is more reliable and it's not coincidence that the handle them in the way they mention in the javadoc.

There is a good question (with great answers) about surrogates on Stack Overflow: What is a surrogate pair in Java?

(See also: Effective Java, 2nd edition, Item 47: Know and use the libraries)

share|improve this answer
2  
Handling surrugates isn't enough. You also need to handle combining characters. –  CodesInChaos Feb 28 at 20:06

The code appears to be functionally correct, although you could simply choose to use a StringBuffer.reverse(). There is some discussion of this here.

If you do need to roll your own reversing method, you can avoid using StringBuffer/StringBuilder at all and simply do new String(array) instead.

As a general point, if you're not dealing with multithreaded code you should probably use StringBuilder in preference to StringBuffer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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