• Post Reply Bookmark Topic Watch Topic
  • New Topic

Ways to optimize your java code ?  RSS feed

 
Abhinav Pande
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I want to optimize below code for efficient run time complexity.

The problem statement is: A number is called a "strange prime" if it is a prime number and its sum of digits (reduced to a single digit) is also a prime number. Sum of digits reduced to a single digit means that if the sum of digits have more than 1 digit, we again sum the digits and follow this process till we get a single digit. So if the number is 345181, then its sum of digits (reduced to a single digit) = 3+4+5+1+8+1 = 22 = 2+2 = 4.
Given a number n as input, return the value of the nth strange prime. Note that some strange primes are 2, 3, 5,7,11,23,29 and so on. 29 is a strange prime because it is a prime number and its sum of digits (reduced to a single digit) = 2+9 = 11 = 1+1 = 2 which is a prime number.
nthStrange(2) = 3
nthStrange(8) = 41

My Solution:



Note: Don't use arrays. Don't use built-in functions. Required a raw solution.
 
Paul Clapham
Sheriff
Posts: 22813
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch!

Abhinav Pande wrote:I want to optimize below code for efficient memory and run time complexity.


Efficient memory? I suppose that means you want to minimize the amount of memory used? Seems kind of pointless since the code creates only one object. And anyway it isn't any more efficient to use 1 kilobyte of memory than it is to use 100 kilobytes. Both numbers are trivially small compared to the amount of memory you have available.

And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Abhinav Pande wrote:I want to optimize below code for efficient memory and run time complexity.

Before doing either of those, it's probably best to get some code that works.
Try calculating the 5th strange prime with your code.
 
Abhinav Pande
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joanne Neal wrote:
Before doing either of those, it's probably best to get some code that works.
Try calculating the 5th strange prime with your code.


code is correct now answer my question!
 
Paul Clapham
Sheriff
Posts: 22813
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You need to answer mine first.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Abhinav Pande wrote:now answer my question!

Need working code first.
According to your latest code, the 6th strange prime is 13
 
Charles D. Ward
Ranch Hand
Posts: 99
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Abhinav Pande wrote:code is correct now answer my question!


Great way to ask for help.
 
Abhinav Pande
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joanne Neal wrote:
Need working code first.
According to your latest code, the 6th strange prime is 13


now its working! thanks for the review
 
Abhinav Pande
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:

And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?




http://en.wikipedia.org/wiki/Time_complexity

code written in such way that when it compiles should take less amount of time for program execution i.e. optimal solution
not a feasible one.
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Abhinav Pande wrote: . . . code is correct now answer my question!
That is no way to talk to people who are trying to help. Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only. I think that merits an apology.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12562
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Abhinav Pande wrote:
Paul Clapham wrote:
And I'm not sure what you mean by "run time complexity". Could you explain that a bit more?

http://en.wikipedia.org/wiki/Time_complexity
code written in such way that when it compiles should take less amount of time for program execution i.e. optimal solution
not a feasible one.

Doing that is really more of an art, not a science. after all, it is possible the "optimal solution" hasn't been figured out yet.

Generally, when one is trying to optimize code, you start by defining requirements. and those should be SPECIFIC. there is almost always a way to make the code run faster, but the law of diminishing returns apply. is it worth it to spend 40 hours coding to save a microsecond? is it then worth it to spend 200 hours coding to save another? etc.

Also, at some point, it becomes cheaper to by bigger/faster hardware to get speed improvements than to improve the code.

Have you figured out what the complexity of your algorithm even is?
 
Abhinav Pande
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Abhinav Pande wrote: . . . code is correct now answer my question!
That is no way to talk to people who are trying to help. Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only. I think that merits an apology.



I apologize, I didn't mean that actually but you are right
Even if you did not mean to appear rude, it does appear rude on the net, where you see the writing only.


It will never happen again. I'll choose my words correctly in the future.



 
Paul Clapham
Sheriff
Posts: 22813
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you want your code to run faster then basically there are two ways to do that: (1) Find the parts of your program which are executed most often and fix the code to execute them less often; (2) Write some different code which runs faster.

To use option (1) you should profile your code. To do that you need your code to run for some time, so finding "strange prime" number 6 isn't a good test. Finding number 6,000 would be better.

To use option (2) you need to do some mathematical thinking about the algorithm you chose (since it's a mathematical problem). For example you could write



instead of what you had. I doubt this would speed up your code much, since your profiling wouldn't have pointed there as the most frequently-run code, but that's the sort of thing to do.
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Apology accepted
 
Abhinav Pande
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Apology accepted


Thank you
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Now, what algorithm were you using for finding primes, and for the sum of digits. The algorithm for finding primes looks as if it will run in quadratic time. There are far better ways to do that, for example the Sieve of Eratosthenes, which I suggest you read about.
Also, you do not need to loo as far as the number to find whether it is prime. Work out what the best value of the loop index m should be.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!