How should I write a FindClosestMatching function?

Question

Of all objects matching a condition, find the one closest to a position. Supposedly a very common problem. The current code looks like this:

protected Foo FindClosestFooMatching (Vec pos, Func<Foo, bool> matches)
{
 float bestDist = float.MaxValue;
 Foo bestFoo = null;

 foreach (Foo foo in AllFoos()) {
  if (matches (foo)) {
   float dist = pos.Dist (foo.Center);
   if (dist <= bestDist) {
    bestDist = dist;
    bestFoo = foo;
   }
  }
 }
 return bestFoo;
}

I'm thinking of several ways to refactor this code, but failed to find a really nice one yet. If you've got a minute, give it a shot. :-)

Edit: Regarding Eric's questions. It's a standard 3D space with Euclidian metric (= fast). Point clustering and junk query likelihood is unknown.

Answer 1

Can't compile right now, but I hope this does the job.

var foos = AllFoos().Where (x => matches (x));
return foos.OrderBy (x => pos.Dist (x.Center)).FirstOrDefault ();

The important point to notice here is that every operation, including OrderBy, is subject to deferred execution, so the performance should be ok.

This would be a nicer looking solution:

var res = from foo in AllFoos()
 where matches (foo)
 orderby pos.Dist (foo.Center)
 select foo;
return res.FirstOrDefault ();

Edit: I found this question to be a valuable source in this issue. Since OrderBy actually orders the whole list first, it's of course slow (as Eric said, O(n log n). A better solution would be to use Aggregate or Jon Skeet's propsed MinBy extension (see above link for examples).

I actually love the MoreLinq solution, as it reduces the code to:

return World.AllNodes
 .Where (x => matches (x.T))
 .MinBy (x => pos.DistSq (x.T.Volume.Center));

Answer 2

return (from f in AllFoos()
        where matches(f)
        orderby f.Center.Dist(pos)
        select f).FirstOrDefault();

Or

return AllFoos().Where(matches)
                .OrderBy(f => f.Center.Dist(pos))
                .FirstOrDefault();

Answer 3

I think your solution is fast (O(n)), simple & stupid(in term of KISS) enough that even a first year CS student could understand.

One problem I can see is that you should take declaration of

float dist;

out of the loop. It may cause memory fragmentation. This is really a minimal concern since it's just a float.

The other would be changing

if (dist <= bestDist)

to

if (dist < bestDist)

to save some CPU cycles of variable assignment. But this has some side impacts because it will change the returned object from last best match to first best match.