CODEWITHSUNDEEP
javaalgorithmtime-complexity
user10516751
user10516751

Reputation:

Why is the second code more efficient than the first one?

I am confused between two codes, why the second one I am going to give here is more efficient than the first one.

Both of the codes just reverse a String, but first code is slower than the other and I am not able to understand why.

The first code is:

String reverse1(String s) {
    String answer = "";
    for(int j = s.length() - 1; j >= 0; j--) {
        answer += s.charAt(j); 
    }
    return answer;
}

The second code is:

String reverse2(String s) {
    char answer[] = new char[s.length()]; 
    for(int j = s.length() - 1; j >= 0; j--) {
        answer[s.length() - j - 1] = s.charAt(j);
    }
    return new String(answer);
}

And I'm not able to understand how the second code is more efficient than the first one, I'd appreciate any insight on this.

Upvotes: 0

Views: 98

Answers (7)

Prashant Pandey
Prashant Pandey

Reputation: 4662

The JVM treats strings as immutable. Hence, every time you append to the existing string, you are actually create a new string! This means that a new string object has to be created in heap for every loop iteration. Creating an object and maintaining its lifecycle has its overhead. Add to that the garbage collection of the discarded strings (the string created in the previous iteration won't have a reference to it in the next, and hence, it is collected by the JVM).

You should consider using a StringBuilder. I ran some tests and the time taken by the StringBuilder code is not much smaller than that of the fixed-length array.

There are some nuances to how the JVM treats strings. There are things like string interning that the JVM does so that it does not have to create a new object for multiple strings with the same content. You might want to look into that.

Upvotes: 0

ZhaoGang
ZhaoGang

Reputation: 4915

Why is the second code more efficient than the first one?

String is immuable, by answer += s.charAt(j); you are creating a new instance of String in each loop, which makes your code slow.

Instead of String, you are suggested to use StringBuilder in a single thread context, for both performance and readablity(might be a little slower than fix-sized char array but has a better readablity):

String reverse1(String s) {
  StringBuilder answer = new StringBuilder("");
  for (int j = s.length() - 1; j >= 0; j--) 
       answer.append(s.charAt(j)); 
 return answer.toString();
}

Upvotes: 0

vivekdubey
vivekdubey

Reputation: 510

In this code you are creating a new String object in each loop iteration,because String is immutable class

String reverse1(String s) {
    String answer = "";
    for (int j = s.length() - 1; j >= 0; j--)
        answer += s.charAt(j);
    return answer;
}

In this code you have already allocated memory to char array,Your code will create only single String at last line, so it is more efficient

String reverse2(String s) {
    char answer[] = new char[s.length()];
    for (int j = s.length() - 1; j >= 0; j--)
        answer[s.length() - j - 1] = s.charAt(j);
    return new String(answer);
}

Upvotes: 0

obfish
obfish

Reputation: 667

String object is immutable and every time you made an add operation you create another object, allocating space and so on, so it's quite inefficient when you need to concatenate many strings.

Your char array method fits your specific need well, but if you need more generic string concatenation support, you could consider StringBuilder

Upvotes: 0

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522712

Your question is perhaps difficult to answer exactly, in part because the answer would depend on the actual implementation of the first version. This, in turn, would depend on what version of Java you are using, and what the compiler decided to do.

Assuming that the compiler keeps the first version verbatim as you wrote it, then yes, the first version might be more inefficient, because it would require allocating a new string for each step in the reversal process. The second version, on the contrary, just maintains a single array of characters.

However, if the compiler is smart enough to use a StringBuilder, then the answer changes. Consider the following first version:

String reverse1(String s) {
    StringBuilder answer = new StringBuilder();
    for (int j = s.length() - 1; j >= 0; j--) 
        answer.append(s.charAt(j));

    return answer;
}

Under the hood, StringBuilder is implemented using a character array. So calling StringBuilder#append is somewhat similar to the second version, i.e. it just adds new characters to the end of the buffer.

So, if your first version executes using literal String, then it is more inefficient than the second version, but using StringBuilder it might be on par with the second version.

Upvotes: 1

Mad Physicist
Mad Physicist

Reputation: 114528

The first code declares

String answer;

Strings are immutable. Therefore, every append operation reallocates the entire string, copies it, then copies in the new character.

The second code declares

char answer[];

Arrays are mutable, so each iteration copies only a single character. The final string is created once, not once per iteration of the loop.

Upvotes: 3

mkjh
mkjh

Reputation: 1654

String is immutable. Whenever you do answer += s.charAt(j); it creates a new object. Try printing GC logs using -XX:+PrintGCDetails and see if the latency is caused by minor GC.

Upvotes: 0

Related Questions