• Post Reply Bookmark Topic Watch Topic
  • New Topic

Timing complexity of this string reverse  RSS feed

 
Jacob Sonia
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
String str = "abcdefghijklmnopqrstuvwxyz";
String rstr = "";
for(int i =(str.length()-1);i>=0;i--){
rstr += str.charAt(i);
}


Hi All,

Please help me what would be the exact timing complexity of this program....i would think it should be 2n - 2
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jacob Sonia wrote:
Please help me what would be the exact timing complexity of this program....i would think it should be 2n - 2


No it's far worse, Because String is mutable it will rather be quadratic, like O(n*n).

But you're lucky. Most Java compilers will replace the rstr String with a StringBuilder in this case. This means the actual reversion will go in n steps, but then afterwards a String object must be created from the StringBuilder and this will require an additional n steps.

This means without compiler optimization you land in the region of n*n/2 steps, whereas with compiler optimization it's likely to be more like 2*n steps. And this is a huge difference for long strings. The "naive" code you presented would be a disaster without the optimization I was talking about, and this of course is why it takes place.
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This sounds like homework. Please explain your reasoning (and remember O(an+b) is O(an))
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David O'Meara wrote:This sounds like homework. Please explain your reasoning (and remember O(an+b) is O(an))


The OP asked about the exact timing, not the Ordo complexity.

And remember that about 99% of the questions at a forum like this is homework-related.
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, but it was a warning to others not to provide a direct solution, which would teach nothing.
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ulrika Tingle wrote:But you're lucky. Most Java compilers will replace the rstr String with a StringBuilder in this case. This means the actual reversion will go in n steps, but then afterwards a String object must be created from the StringBuilder and this will require an additional n steps

Indeed, although the poster is unlikely to see the difference in such a small String. The size of the String may lead the poster to believe there is not a difference so I would advise two things: first use a much larger String (copy a milllion characters of text from 'the internet' somewhere) and then compare the initial code sample with one using a StringBuffer or StringBuilder (the latter is preferred in cases where there is a single thread) and compare the time taken. I suspect that the original code will not be optimised by the compiler, but I'm keen for the original poster to return their results
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David O'Meara wrote:Yes, but it was a warning to others not to provide a direct solution, which would teach nothing.


I don't think you need to worry. Most educational institutes today are aware of the internet and what it offers, and take precutions to offset any possible cheating. And this is a good thing I think. When schools and universities no longer allow unverified work to count toward degrees, people seeking help at forums like these no longer have to be accused of cheating. It's a relief. If someone is asking for help you just give it without having to judge that person's hidden agenda. No help can be used for cheating anybody but oneself.
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David O'Meara wrote:
I suspect that the original code will not be optimised by the compiler


I suspect it will, for the simple reason the JLS specifically suggests this optimization.

It would be suicide for a compiler not to implement it.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think it will almost certainly be optimized to some extent. However the details can be tricky, and I wouldn't trust the compiler or JIT to do that good a job. Consider:

How will this be optimized? Will it be something like this?

Or will it be more like this?

I can observe a huge difference in performance for these options, especially for N = 50000 or so. (I got bored waiting for results for higher values of N.) My results strongly suggest that the compiler does not optimize the original code nearly as well as I can do myself. In general, that sort of thinking is usually folly - but where String concatenation is concerned, it's often accurate.
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Simmons wrote:the compiler


What compiler?
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I agree with Mike. For 150k characters I got 32s for the concatenation, 12ms using a StringBuilder and 19ms with the StringBuffer.
The compiler optimisation you may be referring to relates to the case where the concatenation occurs in a single statement
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
DOM: agreed with whom? What code are you reporting timings for? Can't tell offhand.

Ulrika Tingle wrote:
Mike Simmons wrote:the compiler


What compiler?


Any widely-available compiler (or compiler/JVM combination) you care to discuss, really. I tested it on an Apple MacBook running Snow Leopard, with a javac that identifies itself as "javac 1.6.0_15", and a JVM that identifies itself as
Java(TM) SE Runtime Environment (build 1.6.0_15-b03-219)
Java HotSpot(TM) 64-Bit Server VM (build 14.1-b02-90, mixed mode)

Whatever. I don't claim to have tried them all. But my guess, based on some experience, is that most current compilers will not optimize the original += code very well at all. They do fine for a single standalone statement, but if you put that statement in a loop, they will not make the highly-desirable optimization of moving the StringBuilder declaration outside the loop, so that all concatenations share the same StringBuilder. (Or something roughly equivalent to that.)

It's entirely possible this guess of mine is incorrect. I'd be happy to hear about any real-world counterexamples.
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Simmons wrote:
It's entirely possible this guess of mine is incorrect. I'd be happy to hear about any real-world counterexamples.


Well, one lesson is that you cannot just code away and hope for the best.

Another lesson is that also "homework" questions are valuable, because when properly discussed they give new insight.
Or what do you say David O'Meara?
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd say this post is about the original poster and not you or I.
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
David O'Meara wrote:I'd say this post is about the original poster and not you or I.


But you said you loved me, didn't you?
 
Rob Spoor
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Simmons wrote:I think it will almost certainly be optimized to some extent. However the details can be tricky, and I wouldn't trust the compiler or JIT to do that good a job. Consider:

How will this be optimized? Will it be something like this?

Or will it be more like this?

I can observe a huge difference in performance for these options, especially for N = 50000 or so. (I got bored waiting for results for higher values of N.) My results strongly suggest that the compiler does not optimize the original code nearly as well as I can do myself. In general, that sort of thinking is usually folly - but where String concatenation is concerned, it's often accurate.

It's the former; one StringBuffer (or StringBuilder) object per assignment. That is why it is wise to create your own StringBuilder / StringBuffer if you are going to loop. As another performance gain, if you know the size of the result you should specify this in the StringBuilder / StringBuffer constructor, so its internals do not need to be reorganized because of a lack of space.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rob Prime wrote:It's the former; one StringBuffer (or StringBuilder) object per assignment.

That's certainly been my impression, yes, as I indicated. But if someone wants to be skeptical, I was putting out evidence in a form others can easily test themselves.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!