This week's book giveaway is in the Server-Side JavaScript and NodeJS forum.
We're giving away four copies of Modern JavaScript for the Impatient and have Cay Horstmann on-line!
See this thread for details.
Win a copy of Modern JavaScript for the Impatient this week in the Server-Side JavaScript and NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Bear Bibeault
  • Junilu Lacar
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • salvin francis
  • Frits Walraven
Bartenders:
  • Scott Selikoff
  • Piet Souris
  • Carey Brown

How to minimize the run time complexity of the given java code?

 
Ranch Hand
Posts: 499
Spring AngularJS Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,

I have the following code but when I suggested it to my senior they said it will increase the run time complexity. Do you guys have any ideas on how to reduce it?



I did this for code reduction but as mentioned he said it would increase run time complexity. Is there a work around for this? Please help me guys.
 
Marshal
Posts: 25795
69
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your first two if-statements test the same condition so they could be rolled into one if-statement.
 
Paul Clapham
Marshal
Posts: 25795
69
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Partheban Udayakumar wrote:I did this for code reduction but as mentioned he said it would increase run time complexity.



Presumably "increase run time complexity" involves comparing your code to the previous version. Which you haven't shown us. But your code is O(1) so improving on that is going to be pretty difficult, unless perhaps their definition of "run time complexity" is different to what my understanding is.
 
Partheban Udayakumar
Ranch Hand
Posts: 499
Spring AngularJS Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:Your first two if-statements test the same condition so they could be rolled into one if-statement.


Sorry paul the second if should have been


Paul Clapham wrote:Presumably "increase run time complexity" involves comparing your code to the previous version


Previous version would do some thing like this



This is for one form submit but there would be atleast 3 to 4 such form submits.

Paul Clapham wrote:unless perhaps their definition of "run time complexity" is different to what my understanding is.



He said and I quote "You shouldn't increase the runtime complexity of code to reduce code duplication. If there is no need of setting any of these params, everytime the method is called it would check all the if conditions. So this would increase the runtime." but as far as I have worked in this project, every form submit uses at least one of these params.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That code is not very complex at all, so I wonder why you want to change it to lower complexity. Are you using some static code analysis tool that tells you that this method has a high runtime complexity? That's because there are many possible combinations of one or more of the parameters being empty or not. In fact, since there are 3 parameters, there are 23 = 8 possible combinations. In practice, this is not a problem at all, because the condition for each of the parameters is not dependent on the others.

If it really bothers you, you can make separate methods out of each of the if-statements. But I wouldn't worry about it. Like this:

[code] public String submitForm(String referer, String userAgent, String host) { setReferer(referer); setUserAgent(userAgent); setHost(host); return webBrowser.submitForm(); } private void setReferer(String referer) { if (StringUtils.isNotEmpty(referer) { webBrowser.setRequestHeader("Referer", referer); } } private void setUserAgent(String userAgent) { if (StringUtils.isNotEmpty(userAgent) { webBrowser.setRequestHeader("User-Agent", userAgent); } } private void setHost(String host) { if (StringUtils.isNotEmpty(host) { webBrowser.setRequestHeader("Host", host); } } [/code] In my opnion, that would just make the code longer and has no real benefit.
 
Paul Clapham
Marshal
Posts: 25795
69
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Partheban Udayakumar wrote:He said and I quote "You shouldn't increase the runtime complexity of code to reduce code duplication. If there is no need of setting any of these params, everytime the method is called it would check all the if conditions. So this would increase the runtime."



So here we have two sins.

First using the technical term "runtime complexity" to mean something different than its normal meaning. He could have said "amount of code" and be better understood. Although if he had said what he meant, it would have looked silly because he would have been telling you not to increase the amount of code in order to reduce code duplication. What Jesper said is a good response to that.

Second, premature optimization. The whole method you posted is just a small amount of code which doesn't use any external resources. Its runtime is going to be essentially zero -- maybe a couple of milliseconds at most. And it's only going to be used once in a process which is going to take much longer than that. So spending any time at all on considering whether to optimize it for speed would be a complete waste of time.
 
Partheban Udayakumar
Ranch Hand
Posts: 499
Spring AngularJS Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Jesper de Jong wrote:That code is not very complex at all, so I wonder why you want to change it to lower complexity. Are you using some static code analysis tool that tells you that this method has a high runtime complexity? That's because there are many possible combinations of one or more of the parameters being empty or not. In fact, since there are 3 parameters, there are 23 = 8 possible combinations. In practice, this is not a problem at all, because the condition for each of the parameters is not dependent on the others.
If it really bothers you, you can make separate methods out of each of the if-statements. But I wouldn't worry about it.



We actually work for retail shops and we have around 250 retails shops and around 150 java classes depending on its website layout. So what they have done is One common parent class and 150 child classes. So the code I have mentioned below would not be in the common parent class but in those 150 classes.


I wanted to optimise it so I wrote the new code and gave them to add it to the parent class because they using it at least 3 times in a child class for 150 child classes and more over I have seen people using the wrong spelling for the keys like "Refferer" for "Referer" and spending the whole day not able to resolve the problem. But when I gave it for review they said we would be checking 3 if conditions every time and as you said putting the if conditions in a separate methods would only increase the code.

Paul Clapham wrote:First using the technical term "runtime complexity" to mean something different than its normal meaning. He could have said "amount of code" and be better understood. Although if he had said what he meant, it would have looked silly because he would have been telling you not to increase the amount of code in order to reduce code duplication. What Jesper said is a good response to that


I too didn't understand the phrase "runtime complexity" when he said it to me, I had to google it to check whether it meant something else and on clarification with him, he said it would increase the run time every time this method is called. I was like "WHOA". Anyway he is my senior in the project and he has sent my mail to his seniors to review but they haven't replied any thing. In case if they ask me questions, I have to be ready to justify this method so I posted the question.

Paul Clapham wrote:Second, premature optimization. The whole method you posted is just a small amount of code which doesn't use any external resources. Its runtime is going to be essentially zero -- maybe a couple of milliseconds at most. And it's only going to be used once in a process which is going to take much longer than that. So spending any time at all on considering whether to optimize it for speed would be a complete waste of time.


I didn't get this part. I should have mentioned the 150 child classes first, that would have given you clarity. Sorry my bad   I would like it to move it to the parent class and not the 150 classes if that's what you meant.

Actually I wanted to do something like this


How ever these guys are using only one of these 3 submit methods. I wanted to see the initial reaction for only that method and then propose this. Let's see. Please do let me know if you have any suggestions for this.
 
Paul Clapham
Marshal
Posts: 25795
69
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Partheban Udayakumar wrote:We actually work for retail shops and we have around 250 retails shops and around 150 java classes depending on its website layout. So what they have done is One common parent class and 150 child classes. So the code I have mentioned below would not be in the common parent class but in those 150 classes.



Well, when you have code which is about to be duplicated in many places, the normal thing to do is to put that code into a method and call the method from those many places. And it seems to me that the obvious location of the method would be in the parent class. So what you proposed is perfectly normal refactoring.

As for the idea that your change would increase the run time because you've got three if-statements which weren't there before, that could be true. (It's also true that 1,000,000 is greater than 999,999.) However I don't have anything nice to say about that idea though and we're supposed to Be Nice here, so I'll just not say anything. Except that the way to see if something takes longer to run than something else is to measure the two versions and see what happens. My prediction is that the difference will be less than the time required to serve a request by a very large factor.
 
Marshal
Posts: 15870
265
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The irony of worrying about a few negligible milliseconds while having a superclass with 100+ subclasses. The nightmare it must be to maintain all those subclasses, the time and effort it must take to find and change all the duplicated code (I predict there are more than a few instances where copy-paste programming was used in a few of those 100+ subclasses).

I, too, will follow Paul's example and not say anything here. Know that this is not my keeping silent to be nice face though. This is my "I'm yelling at the computer screen" face.
 
Oh the stink of it! Smell my tiny ad!
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic