Monday, May 28, 2007

optimization challenge

Here are today's unsharable links: a collection of links on optimization, and an optimization challenge.

I'm working on my solution to the challenge. The previous challenge (#6) depended on assembly - hopefully my lack of ASM skills won't be a problem, #7 seems to be algorithm-constrainted. I wish I had visual assist at home, I feel crippled without it. Sadly, paying for a full version of VS2005 just for VA compatability (on top of the price of VA) seems like overkill for hobby programming (I'm currently using VS express for free).

First pass: 15x speedup from the brute-force "you can do better than this" reference implementation. I was hoping to do something like sweep and prune, giving each point a 'radius' of the minimum pair distance I've seen so far, but it didn't reject *any* points, because the distance between points on the other axes is always greater than the minimum on the sorted axis, and I don't have real AABBs for the points. It seems like it should work, though, or something else very similar to it.

Update: 45x faster, with sweep and prune on one axis. You don't need to reject points - just reduce the number of point-point pairs that need testing. Each is tested against ~20 others.

Update 2: 125x faster by not fully sorting the points - just partition down to 32ish-sized groups, and compare against all your neighbors inside those (since you'd be looking at about that many neighbors anyway) - they don't need to be sorted.

Messy update 3: I don't think I should on all 3 axes... sorting on 1 axis then testing the overlapping pairs on only that axis is faster than the time it takes just to sort on 2 axes. [Then why is it worth doing 3-axis SAP in physics?] I think I could probably be clever and do recursive partitions on alternating axes, so it would be as cheap as a single sort but with better partitioning (you're more likely to see close neighbors if it arranged into shrinking neighborhoods of X, Y, Z, X, Y, Z... instead of X, X, X, X...).

It would be kind of like a KD tree, I guess, where the points near the boundaries will be a hassle (like my current solution, only worse), but everything inside each partition is guaranteed to fall inside a small range of X, Y, and Z values (sorting on one of the axes to reject most neighbors, like the 'first pass' solution). The alternating-axis partition will have most of the benefit of 3 sorts but only costs as much as 1. A rough version of the KD tree sorting seems to be going about twice as slowly, and I don't think I'll bother figuring it out tonight, it's late and it since it looks like contest #7 was supposed to be finished months ago - it looks abandoned by Hejl, the dude who ran it.

Unexplored solution: put everything in a hashtable, hashing 3d space to a list of points.

Update 4: Results: I would have come in 7th (aka 3rd last :) with the solution in update 2. Update 3's unimplemented idea was close to the winning solution - "Essentially, it's a quicksort based algorithm that's modified to traverse an implicit kd-tree".

1 comment:

Senzee said...

Ian,

Thanks for reading those! The results for HD #7 have come out.

If you'd like, I can run your submission against the others. (Let me know at psenzee at yahoo com)

HD#7 Official Results (if this isn't up yet, it should be sometime tomorrow)
Senzee 5: Nearest Neighbor

Also I did some cleaning and the "Optimize This!" post is no longer available. Here's a replacement link: http://senzee.blogspot.com/search/label/Optimization