Как написать функцию FindClosestMatching?

Question

Из всех объектов, соответствующих условию, найдите ближайшего к позиции. Предположительно, очень распространенная проблема. Текущий код выглядит следующим образом:

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; 
} 

Я имею в виду несколько способов, чтобы реорганизовать этот код, но не смог найти действительно хороший еще нет. Если у вас есть минута, сделайте снимок. :-)

Редактировать: Относительно вопросов Эрика. Это стандартное трехмерное пространство с евклидовой метрикой (= быстро). Вероятность кластеризации точек и вероятность нежелательных запросов неизвестны.

Answer 1

Невозможно скомпилировать прямо сейчас, но я надеюсь, что это сработает.

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

Важно отметить здесь, что каждая операция, в том числе OrderBy, подлежит отложенным исполнением, так что производительность должна быть в порядке.

Это было бы лучше, глядя решение:

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

Edit: я нашел this question быть ценным источником в этом вопросе. Поскольку OrderBy фактически заказывает список всего, он, конечно, медленный (как сказал Эрик, O (n log n). Лучшим решением было бы использовать расширенное расширение Miniby от Aggregate или Jon Skeet (см. Приведенную выше ссылку для примера).

Я на самом деле люблю решение MoreLinq, так как это уменьшает код:

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(); 

Или

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

Answer 3

Я думаю, что ваше решение быстрый (O (n)), простой & глупый (в терминах KISS) достаточно, чтобы даже первый студент CS мог понять.

Одна проблема, которую я вижу в том, что вы должны принять декларацию

float dist; 

из петли. Это может привести к фрагментации памяти. Это действительно минимальная проблема, так как это просто поплавок.

Другой бы изменение

if (dist <= bestDist) 

в

if (dist < bestDist) 

для сохранения циклов центрального процессора присваивания значения переменной. Но это имеет некоторые побочные эффекты, потому что он изменит возвращаемый объект от последнего наилучшего совпадения до первого наилучшего совпадения.