Ants raise catepillars, and grow antibiotics to control mold infestations(!) in their agricultural farms(!). I will never get tired of seeing complex behavior without fat brains. And they haven't changed since Gondwanaland.

Bonus link: robot movie.

## 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".

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".

## Sunday, May 27, 2007

### Google reader is almost perfect

Do RSS feeds typically only show the most recent posts? I want to share other people's old blog posts in google reader, but they often don't show up in the RSS feeds. I wish google reader would let me share links that aren't part of RSS feeds - it's the only thing that bothers me. And since I'm not on the Reader development team, I can assume it would be really easy to implement :)

Subscribe to:
Posts (Atom)