Win a copy of Murach's Python Programming this week in the Jython/Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Discussion: optimizing code  RSS feed

 
Craig O'Brien
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello all,
I just discovered this place about a week ago and it seems like a great bunch of people.
I would like to submit a short program and see what you folks think about optimization of java code. The following is a short randomizing algorithm that I wrote which can be used to create passwords and such. The result is a character sequence of upper and lower case characters and numbers the length that you type into the shell. (ex. java CraigsRandomizer 50 -- would produce a sequence of 50 characters) It will tell you how many characters you chose, the processing time in milliseconds, and display the result. Just copy, paste, compile, and your off.
Here is the code:


You will probably note that you have to make the length more then 100-200 to start getting any processing time indication at all. The processing time result is relative to the amount of characters that are generated which quickly meet the specification.
The program uses Math.random() and creates an array of "len" characters which meet the specification.
Steps I took to optimize the code:
1) The class and method are final to maximize compilation.
2) Short circuit comparison operators are used and the comparisons listed from the largest group to the smallest group for fastest rejection.
3) An array of primitives is used and discarded for quick access and memory size.
4) Math.random() * 122 limits the result to numbers which do not exceed our needs.
Please disregard the three lines of code which are for displaying the timing and print the messages to the screen. They are just for the purpose of this discussion.
Also I am aware of the opinion that the java.lang.Math.random() does display certain consistencies and that other algorithms can produce more random results. For this purpose it is certainly random enough.
Are there any further ways to optimize this?
What about the two casts?
Would a different algorithm be faster?
Is there a more efficient way to handle memory?
Thanks for your time,
Best Regards,
Craig

(fixed formating)
[This message has been edited by Craig O'Brien (edited March 01, 2001).]
 
Angela Lamb
Ranch Hand
Posts: 156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Two suggestions:
1. Instead of using Math.random(), which produces a double that has to be cast, you could use the following:

2. You could also eliminate the char casting by using a different string constructor for the result:
 
Craig O'Brien
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey thanks for responding Angela.
Replacing
int n = (int)(Math.random() * 122);
with
int n = rand.nextInt(122);
did yield a 1.0107% increase in performance.
Unfortunately for the result to be a character sequence the integers still need to be cast to characters so the String() constructor does not fill the need.
I see that I probably placed this in the wrong forum, I told you I was new here. I see that there is a performance forum just a few lines above. Guess I'll mosey over there.
Thanks,
Craig
 
Cindy Glass
"The Hood"
Sheriff
Posts: 8521
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You know we have a whole forum dedicated to performance issues. The folks over there would really like this kind of a conversation.
 
Craig O'Brien
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
duhhhh...I see now.
If you could transfer me It would be great. Otherwise I'll make it over there soon......
but: crossposting is spam :0)
 
Frank Carver
Sheriff
Posts: 6920
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're outta here dude. See you in "Perfomance" ...
 
Craig O'Brien
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Sheriff.
Craig
 
Jack Shirazi
Author
Ranch Hand
Posts: 96
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My first advice would be to profile the code to get some clues. Having said that, I'll instead have a look at the code and guess at some speedups.
Firstly, rather than use the Random class, try a net search for FastRandom. I'm pretty sure I remember it's out there somewhere. Then, instead of using the class, just take its pseudo-random number generator algorithm (its usually a simple one or two liner) and plug it straight into your code.
Then, don't throw away randoms. And get rid of that ugly test. I think its letters and characters, but can't be bothered to work out its logic.
Instead get your random as a value from 0 to 35, and use an array of letters & characters to get your char from the random value.
Finally, don't use that annoying concatenation operator. It won't make much difference in a program like this, but it is tuning 101. Use a StringBuffer created with the correct capacity, and append to it. And I don't think you need the temporary int array either.
--Jack Shirazi http://www.JavaPerformanceTuning.com/
 
Craig O'Brien
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks,
I'll do all of those things. I did this on a whim and thought it might generate some conversation. I appreciate your time.
Craig
 
Craig O'Brien
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I used much of Jack Shirazi's advice and updated this little algorithm. The speed is greatly improved. I found FastRandom by Pedro Silva and Nuno Lopes ( http://laseeb2.isr.ist.utl.pt/sw/jdeal/ ) and attempted to use this Algorithm for generating seeds:
<pre>
long seed = (System.currentTimeMillis() ^ 0x5DEECE66DL);
n = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
</pre>
But it just couldn't produce seeds fast enough as it uses System.currentTimeMillis().
Anyway, admittedly this is frivolous as its probable use is for only sequences of 10-16 characters which is so small that even the original version wasn't measurable with the range of milliseconds. There was significant improvement with the suggestions.
Here's the latest version. Can it get faster? This is just for fun. :0)

<pre>
import java.util.*;
final public class RanchRandomizer2{
// generates a random alpha-numeric sequence

public static void main(String[] args){

RanchRandomizer2 t = new RanchRandomizer2();
int len;
if (args.length != 0)
len = Integer.parseInt(args[0]);
else
len = 12;
System.out.println("A random sequence of " + len + " characters");
System.out.println(t.randomPass(len));
}

final StringBuffer randomPass(int len){
long timeIn = System.currentTimeMillis();
char[] set = {'a','A','b','B','c','C','d','D','e','E','f','F','g','G',
'h','H','i','I','j','J','k','K','l','L','m','M','n','o',
'O','p','P','q','Q','r','R','S','t','T','u','U','v','V',
'w','W','x','X','y','Y','z','Z','1','2','3','4','5','6',
'7','8','9','0'};
StringBuffer result = new StringBuffer(len);
Random rand = new Random();
int i = 0;
while(i < len){
int n = rand.nextInt(set.length);
result.append(set[n]);
i++;
}
long timeOut = System.currentTimeMillis();
System.out.println("Processing time: " + (timeOut - timeIn) + " milliseconds\n");
return result;
}
}
I was kind of proud of my "ugly test", I guess thats from too much perl.
Regards,
Craig
[This message has been edited by Craig O'Brien (edited March 06, 2001).]
 
Jack Shirazi
Author
Ranch Hand
Posts: 96
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think if you closer at FastRandom you'll find that the seed is generated once only. Then it is fed into the randomizing algorithm once, and the output is fed back into the randomizing algorithm each time a new random is required, i.e.
<PRE>
//initialize once only
long seed = (System.currentTimeMillis() ^ 0x5DEECE66DL);
long n = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
while (...
{
//Use the current n each time we want a new pseudo-random
n = (n * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
result.append(set[n%36]);
...
</PRE>
--Jack Shirazi http://www.JavaPerformanceTuning.com/
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!