What is the most efficient way to reverse a char array?

Question

I tried two different ways to reverse a char array

    //method 1
    char c[] = {'A', 'B', 'C', 'D'};
    char c_rev[] = new char[4];
    for (int i = 3; i >= 0; i--) {
        c_rev[i] = c[3 - i];
    }
    System.out.println(Arrays.toString(c_rev));

---

    //method 2
    char c[]  = {'A', 'B', 'C', 'D'};
    Stack<Character> st = new Stack();
    for (int i = 0; i < 4; i++) {
        st.push(c[i]);
    }
    for (int i = 0; i < 4; i++) {
        c[i] = st.pop();
    }
    System.out.println(Arrays.toString(c));

I just wondered what will be the most efficient one. Method 1 or Method 2 ? Can anyone help me or give any suggestions ?

Answer 1

In terms of time complexity, they're both O(n). Performance wouldn't be significant here.

Which to choose? None. I would use a ready method StringBuilder#reverse:

String reversed = new StringBuilder(new String(c)).reverse().toString();

If I wanted to choose one from the two methods you posed, I would have choose the first one, it have only one loop and it's straightforward, no methods will be called, no helper objects will be created; you simply create a new array and directly push to it the new elements.

Answer 2

@MarounMaroun's answer will work for char arrays that are really strings. If you are worried only about those two methods then the first involves less heap allocations and GC.

However in general for an array I would use neither of your methods, but instead:

int len = c.length; 
for(int i = 0; i < len / 2; i++) {
    char ch = c[i];
    c[i] = c[len - i - 1];
    c[len - i - 1] = ch;
}

It is:

1. shorter to type than method 2
2. only iterates for half the array length (it is still O(n) due to the ops per iteration)
3. will work for any array type
4. doesn't need extra object allocations (vs Method 2) or two arrays (vs Method 1)

I would, however, be careful of micro-optimizations like this. The difference between this and Method 1 is probably minimal for small array allocations so you are better off using the one that is easiest for you to understand. (Similarly I only pulled the len variable out for clarity - some microbenchmarks claim it speeds up loops, but the downside is it pollutes your local variables with something that is only used inside the loop).

Answer 3

I'd say that method 1 is probably faster since it doesn't require the creation, allocation, and destruction of new objects (i.e. the Stack and its internal objects). For the same reason it should also have a lower impact on the garbage collector.

If this is a frequent operation in your code, you can benchmark both methods using something like Google caliper. Otherwise, I wouldn't worry about it :)