HD7 Results

Hacker's Delight #7 Final Results

Problem & Constraints

You will be provided with a cloud of no more than 65535 points
The point cloud will not be a pathological case, such as points distributed in a regular grid pattern, on a surface of a sphere, or all on a single plane.

Our tests included the Stanford bunny mesh and randomly generated sets of 65535 points. Congratulations to all entrants - all entries were much faster than the reference implementation. Congrats to Alistair Milne of EA Montreal - awesome entry!

Rank	Name	Total Cycles	Runs	Time (ms)	Per Run (ms)	DQ	Notes

1	AlistairMilne_ElectronicArtsMontreal_submission2	57003397398	800	15834.28	19.79	OK	-
	Senzee_Tiburon_1	76097087667	800	21138.08	26.42	DQ	run 50/800 incorrect
	AndySouthgate_EATech	90699312924	800	25194.25	31.49	DQ	run 293/800 incorrect
2	ColinAndrews_ElectronicArtsMaxis_sub7	131961781503	800	36656.05	45.82	OK	-
2	ColinAndrews_ElectronicArtsMaxis_sub6	132929517312	800	36924.87	46.16	OK	-
2	ColinAndrews_ElectronicArtsMaxis_sub8	133619520465	800	37116.54	46.40	OK	-
2	ColinAndrews_ElectronicArtsMaxis_sub1	138658942728	800	38516.37	48.15	OK	-
2	ColinAndrews_ElectronicArtsMaxis_sub3	139746436254	800	38818.45	48.52	OK	-
2	ColinAndrews_ElectronicArtsMaxis_sub5	140119140726	800	38921.98	48.65	OK	-
2	ColinAndrews_ElectronicArtsMaxis_sub4	142041002922	800	39455.84	49.32	OK	-
3	dwinter1_ElectronicArtsCanada	163758314763	800	45488.42	56.86	OK	-
4	JayMacDonald_EAC	191835150390	800	53287.54	66.61	OK	-
5	MichaelCooper_PolarSun	235507388454	800	65418.72	81.77	OK	-
6	DavidGaleano_ElectronicArtsEATech_4	278949846951	800	77486.07	96.86	OK	-
7	LouisGascoigne_ElectronicArtsRedwoodShores_2	288767046564	800	80213.07	100.27	OK	-
8	DavidGaleano_ElectronicArtsEATech_2	319879085328	800	88855.30	111.07	OK	-
8	DavidGaleano_ElectronicArtsEATech_3	382839377481	800	106344.27	132.93	OK	-
9	LarzSmith_EATiburon	711535278186	800	197648.69	247.06	OK	-
10	JeffreyRainy_ElectronicArtsCanada	795788127657	800	221052.26	276.32	OK	-
	NathanHoobler_ElectronicArtsMythic	-	-	-	-	DQ	exception on certain sets
	NathanHoobler_ElectronicArtsMythic2	-	-	-	-	DQ	exception on certain sets
	ColinAndrews_ElectronicArtsMaxis_sub2	-	-	-	-	DQ	hangs on certain sets - the only dual threaded entry
	AlistairMilne_ElectronicArtsMontreal	-	-	-	-	DQ	hangs on certain sets
	Dom_EAC	-	-	-	-	DQ	exception on certain sets; some incorrect
	dwinter2_ElectronicArtsCanada	-	-	-	-	DQ	hangs on certain input sets
	PhilipDunstan_EATechUK_v2	-	-	-	-	DQ	exception on certain input sets
	PhilipDunstan_EATechUK_v1	-	-	-	-	DQ	incorrect answers on certain input sets
	YggyKing_ElectronicArtsCanada	-	-	-	-	DQ	hangs on certain input sets
11	Reference	-	-	-	26257.13	OK	-

	Senzee_AlistairMilneAlgorithm_1	46818518994	800	13005.14	16.26	OK	optimization of Alistair Milne's fastest entry

Submissions

The entries we received used a variety of approaches. The canonical divide-and-conquer approach (see Cormen, Introduction to Algorithms, p.957), kd-trees, various sorting and hashing approaches were all represented. We even received one entry that was dual-threaded.

Fastest Entry

Alistair Milne's elegant second entry was fastest by a clear margin. And it's pure C++. It is a beautiful and simple algorithm that I was shocked not to find anywhere in the literature. Essentially, it's a quicksort based algorithm that's modified to traverse an implicit kd-tree. Alistair writes,

"It's basically a KD tree builder based on qsort, with some extra mess to cope with the overlaps between zones." Here's a paraphrase of the algorithm -


// partition all points less than sqrt(distancesq) away from the plane specified by pivot and coordinate (0 = x, 1 = y, 2 = z)
  // into the lower part of the array and returns the final location of the pivot point
  Point *PartitionByDistance(Point *lo, Point *hi, Point *pivot, unsigned coordinate, float distancesq);
  
  // A normal quicksort median of 3 partition function that partitions based on the coordinate (0 = x, 1 = y, 2 = z) specified
  Point *PartitionMedian3(Point *lo, Point *hi, unsigned coordinate);
  
  // The naive O(N^2) function for small sets
  float *GetMinDistSquared_Naive(Point *lo, Point *hi);
  
  float GetMinDistSquared(Point *lo, Point *hi, float distancesq = FLT_MAX, unsigned depth = 0)
  {
  enum { N2_CUTOFF = .. }; // set to optimal threshold for N^2 algorithm
  
  float d;
  
  if (lo + N2_CUTOFF < hi)
  {
  unsigned coordinate = depth % 3;
  
  // partition segment
  Point *q = PartitionMedian3(lo, hi, coordinate);
  
  // now recurse, divide and conquer
  if ((d = GetMinDistSquared(lo, q - 1, distancesq, depth + 1)) < distancesq)
  distancesq = d;
  if ((d = GetMinDistSquared(q + 1, hi, distancesq, depth + 1)) < distancesq)
  distancesq = d;
  
  // now get any 'smallest' pairs that cross a partition
  q = PartitionByDistance(lo, hi, q, coordinate, gMind);
  if ((d = GetMinDistSquared(lo, q, distancesq, depth + 1)) < distancesq)
  distancesq = d;
  }
  else if (lo < hi)
  {
  if ((d = GetMinDistSquared_Naive(lo, hi)) < distancesq)
  distancesq = d;
  }
  return distancesq;
  }

For interest, we created an SIMD optimized version of Alistair's algorithm. Thanks to the efforts of everyone who entered.

Paul D. Senzee
psenzee@ea.com