CIT 594 Assignment 10: ForkJoin
Spring 2012, David Matuszek
Randomly generate one million (x, y) points, where 0.0 <= x < 1.0 and 0.0 <= y 1.0, and
y are of type
double. Then find and print out the two closest points, along with the distance between them.
Do this as quickly as possible, and print out the time required in seconds, as a floating point number.
ForkJoin. If you have a dual-core or quad-core computer, this should make your program about 2x or 4x faster. If you don't, using
ForkJoin will slow things down slightly--but use it anyway!
Since I need to be able to check if you got the right answer, I need some control over the "random" points you generate. So I would like you to generate them exactly as follows:
static Random rand = new Random(seed); Do this only once, at the beginning of the program.
xvalue of the first point.
yvalue of the first point.
xvalue of the second point.
yvalue of the second point.
xvalue of the third point.
Nothing beats a good algorithm.
On my home computer (2.8 GHz quad core), using a sequential program to compare every point against every other point, I got the following numbers:
But obviously some pairs of points are so far apart that you don't even need to consider them. I used a simple trick to eliminate many of these pairs, and got the following timings:
ForkJoin gave me approximately another 4x speedup.
How do you know you have the correct answer?
Comparing every point against every other point is really simple, and you can probably write that without error. Test it for a small number of points, say, 1000. Then see if your fancier algorithm gives the same answer.
Your program is due before 6am Tuesday, April 17. Zip up the entire directory for this project, and submit via Blackboard. Only assignments submitted via Blackboard will be accepted--any assignments emailed to me will be discarded without comment. A late penalty of 5 points per day (out of 100 points) will apply.
Because many of you are interviewing this semester, a limited number of 48-hour extensions will be available. To get an extension, email me before 5pm Friday, stating the reason you need the extension. No extensions will be granted after Friday. If you get an extension and fail to get the project in by the extended due date, late points will be counted from the original due date.