Минимального значения всех элементов, удовлетворяющих условию в списке

Question

У меня есть класс точки 2D следующим образом:

class Point 
{ 
    public int id_; 
    public float x_, y_; 

    public Point(int i, float x, float y) 
    { 
     id_ = i; 
     x_ = x; 
     y_ = y; 
    } 

    public float Distance(Point otherPoint) 
    { 
     return (float)Math.Sqrt(Math.Pow(x_ - otherPoint.x_, 2) + Math.Pow(y_ - otherPoint.y_, 2)); 
    } 
} 

В моем основном коде у меня есть список этих точек. Мне представлено новое замечание. Я хочу найти эту точку в моем списке, которая является кратчайшим расстоянием от новой точки, если она удовлетворяет минимальным пороговым критериям.

Я изначально написал это прямо, получив minValue (инициализированный 1е6) и minID, пройдя через список, чтобы найти минимальное значение. И за пределами обхода я проверил, было ли это минимальное значение меньше порога. Это сработало.

Но я хотел бы видеть, был ли лучше/уборщик способ осуществить это, и я закончил с этим:

var list = new List<Point>(); 
list.Add(new Point(0, 10.0f, 1.0f)); 
list.Add(new Point(1, 1.0f, 0.0f)); 
list.Add(new Point(2, 0.0f, 0.0f)); 

var p = new Point(3, 0.6f, 0.0f); 
var subList = list.Select((item, index) => new { item, index }) 
        .Where(x => (x.item.distance(p) <= 1.0)) 
        .Select(x => x.item).ToList(); 

Point minPoint = subList[Enumerable.Range(0, subList.Count).Aggregate((a, b) => (subList[a].Distance(p) < subList[b].Distance(p) ? a : b))]; 
Console.WriteLine(minPoint.id_); 

Есть ли лучший способ сделать это?

Answer 1

Я бы некоторые идеи о двух решений задачи, здесь оригинальный класс , лишенный лишних подчеркиваний. Обычно идентификатор является уникальным, так чтения и я позаимствовал Distance метод от @ ответа CommuSoft, как он прав насчет этого метода:

class Point 
{ 
    public readonly int id; 
    public float x; 
    public float y; 
    public Point(int id, float x, float y) 
    { 
     this.id = id; 
     this.x = x; 
     this.y = y; 
    } 
    public float Distance(Point p) 
    { 
     float dx = this.x - p.x; 
     float dy = this.y - p.y; 
     return (float)Math.Sqrt(dx * dx + dy * dy); 
    } 
} 

Shared часть:

 List<Point> list = new List<Point>(); 
     list.Add(new Point(0, 10.0f, 1.0f)); 
     list.Add(new Point(1, 1.0f, 0.0f)); 
     list.Add(new Point(2, 0.0f, 0.0f)); 

     Point p = new Point(3, 0.6f, 0.0f); 

Следующая решение IpavluVersionA1 İŞ наиболее эффективными в использовании памяти/распределения и вычислительной эффективностью:

 //VersionA1, efficient memory and cpu usage 
     Point closest_to_p = null; 
     float shortest_d = float.MaxValue; 

     //list.ForEach because it is iterating list through for cycle, most effective 
     list.ForEach(point => 
     { 
      //Distance is computed only ONCE per Point! 
      var d = point.Distance(p); 
      if (d > 1.0f) return; 
      if (closest_to_p == null || shortest_d > d) 
      { 
       closest_to_p = point; 
       shortest_d = d; 
      } 
     }); 
     //closest_to_p is cloases point in range with distance 1.0 
     //or below or is null, then does not exist 

Следующие один IpavluVersionA2, лучшее исполнение мудро:

 //VersionA2, most efficient memory and cpu usage 
     Point closest_to_p = null; 
     float shortest_d = float.MaxValue; 
     int max = list.Count; 

     for (int i = 0; i < max; ++i) 
     { 
      var point = list[i]; 
      var d = point.Distance(p); 
      if (d > 1.0f) continue; 
      if (closest_to_p == null || shortest_d > d) 
      { 
       closest_to_p = point; 
       shortest_d = d; 
      } 
     } 
     //closest_to_p is closest point in range with distance 1.0 
     //or below or is null, then does not exist 

Другое решение, IpavluVersionB, который использует LINQ подход, должно создать новую структуру объект, для того, чтобы сохранить точку и расстояние, но они скорее всего, созданы в стеке. Вычисление расстояния выполняется только один раз, тогда значение используется повторно!

 //versionB 
     var null_point = new KeyValuePair<Point,float>(null, float.PositiveInfinity); 
     var rslt_point = 
     list 
     .Select(xp => 
     { 
      var d = xp.Distance(p); 
      return d <= 1.0f ? new KeyValuePair<Point, float>(xp, d) : null_point; 
     }) 
     .Aggregate(null_point, (a, b) => 
     { 
      if (a.Key == null) return b; 
      if (b.Key == null) return a; 
      return a.Value > b.Value ? b : a; 
     }, x => x.Key); 

rslt_point является нулевым или экземпляр самой близкой точке к p.

ЭТАЛОН:

• должен быть построен в режиме выпуска,
• должен работать без отладки, вне VisualStudio,
• тест работает в 5 раз для двух сценариев,
• сценарий X : 3 предмета, 10 миллионов раз, все методы, время в милисекундах,
• сценарий Y: 3mil itmes, 1 раз, все методы, время в миллисекундах,

the code is here

BechmarkREsults:

• B - число итераций над списком,
• I - количество элементов в списке,
• все числа в миллисекундах,
• CommuSoft - это решение из ответа CommuSoft,
• Ivan Stoev предложил решение с анонимными типами, ведет себя аналогично VersionA2 со структурой,
• Ясно, что IpavluVersionA2 - лучшая производительность.

В [10000000] Я [3]: CommuSoft: 3521 IpavluA1: 371 IpavluA2: 195 IpavluB: 1587

В [10000000] Я [3]: CommuSoft: 3466 IpavluA1: 371 IpavluA2: 194 IpavluB: 1583

В [10000000] Я [3]: CommuSoft: 3463 IpavluA1: 370 IpavluA2: 194 IpavluB: 1583

В [10000000] Я [3]: CommuSoft: 3465 IpavluA1: 370 IpavluA2: 194 IpavluB: 1582

B [10000 000] Я [3]: CommuSoft: 3471 IpavluA1: 372 IpavluA2: 196 IpavluB: 1583

В 1 я [3000000]: CommuSoft: 919 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

В 1 I [ 3000000]: CommuSoft: 947 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

В 1 я [3000000]: CommuSoft: 962 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

В 1 я [3000000]: CommuSoft : 969 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

В 1 я [3000000]: CommuSoft: 961 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

Answer 2

Есть несколько вещей, которые могут быть улучшены:

1. уронить первое Select заявление, так как оно не имеет никакой пользы? Вы ничего не делаете с этим моментом; Это также позволяет отбросить второй оператор Select.

2. Не используйте ToList: вы все равно не хотите создавать этот список;

3. Math.Pow является метод, используемый для произвольных степеней, то, кроме того, не так много точнее, использовать x*x вместо Math.Pow(x,2);

4. Вы сделали некоторые небольшие ошибки в отношении колпачков, Points вместо Points, Distance вместо Distance;

Способ получения вашего Point, что не абсолютного большинства эффективны одна используют следующее заявление:

class Point { 

    public int id_; 
    public float x_, y_; 

    public Point(int i, float x, float y) { 
     id_ = i; 
     x_ = x; 
     y_ = y; 
    } 

    public float Distance(Point otherPoint) { 
     float dx = this.x_-otherPoint.x_; 
     float dy = this.y_-otherPoint.y_; 
     return (float)Math.Sqrt(dx*dx+dy*dy); 
    } 
} 

с потенциальным запросом:

var minPoint = list.Where(x => x.Distance(p) <= 1.0).OrderBy(x => x.Distance(p)).FirstOrDefault(); 

Этих вернет null, если такой предмет не существует (что соответствует пункту Where). Однако это в большинстве случаев не будет абсолютной самой эффективной реализацией.

---

Другим способом является первым реализовать метод расширения:

public static class Utils { 

    public static T MinBy<T,R> (this IEnumerable<T> source, Func<T,R> f) where R : IComparable<R> { 
     IEnumerator<T> e = source.GetEnumerator(); 
     if(!e.MoveNext()) { 
      throw new Exception("You need to provide at least one element."); 
     } 
     T min = e.Current; 
     R minf = f(min); 
     while(e.MoveNext()) { 
      T x = e.Current; 
      R xf = f(x); 
      if(minf.CompareTo(xf) > 0) { 
       min = x; 
       minf = xf; 
      } 
     } 
     return min; 
    } 

} 

Затем вы можете использовать:

var minPoint = list.Where(x => x.Distance(p) <= 1.0).MinBy(x => x.Distance(p)); 

Этот метод работает в O (N) и, таким образом, вероятно, один из самых эффективных.

---

Бенчмарки

Я проверил как два метода @ipavlu и сам, хотя и с небольшим testset вы дали, так что результаты не действительно научно обоснованные и казнили их с использованием csharp интерактивной оболочки:

csharp> DateTime dt=DateTime.Now; for(int i = 0; i < 10000000; i++) { var minPoint = list.Where(x => x.Distance(p) <= 1.0).OrderBy(x => x.Distance(p)).FirstOrDefault(); }; DateTime dt2 = DateTime.Now; Console.WriteLine(dt2-dt); 
(1,68): warning CS0219: The variable `minPoint' is assigned but its value is never used 
00:00:09.3165310  
csharp> DateTime dt=DateTime.Now; for(int i = 0; i < 10000000; i++) { var minPoint = list.Where(x => x.Distance(p) <= 1.0).MinBy(x => x.Distance(p)); }; DateTime dt2 = DateTime.Now; Console.WriteLine(dt2-dt); 
(1,68): warning CS0219: The variable `minPoint' is assigned but its value is never used 
00:00:03.3658400 
csharp> DateTime dt=DateTime.Now; for(int i = 0; i < 10000000; i++) { Point closest_to_p = null;float shortest_d = float.MaxValue;list.ForEach(point =>{var d = point.Distance(p);if (d > 1.0f) return;if (closest_to_p == null || shortest_d > d){closest_to_p = point;shortest_d = d;}}); }; DateTime dt2 = DateTime.Now;Console.WriteLine(dt2-dt);          
00:00:10.4554550 
csharp> DateTime dt=DateTime.Now; for(int i = 0; i < 10000000; i++) { var null_point = new KeyValuePair<Point,float>(null, float.PositiveInfinity);var rslt_point = list.Select(xp =>{var d = xp.Distance(p);return d <= 1.0f ? new KeyValuePair<Point, float>(xp, d) : null_point;}).Aggregate(null_point, (a, b) =>{if (a.Key == null) return b;if (b.Key == null) return a;return a.Value > b.Value ? b : a;}, x => x.Key); }; DateTime dt2 = DateTime.Now; Console.WriteLine(dt2-dt); 
(1,146): warning CS0219: The variable `rslt_point' is assigned but its value is never used 
00:00:18.5995530 

Это, таким образом, приводит к некоторым незначительных результатов:

CommuSoft.A 00:00:09.3165310 
CommuSoft.B 00:00:03.3658400 
ipavlu.A 00:00:10.4554550 
ipavlu.B 00:00:18.5995530 

Кроме того, обратите внимание, что эти работы в режиме отладки, и что компиляторы могут иногда найти полезные оптимизации.

Answer 3

Я предпочел бы использовать следующее, что делает O вычисления (N) Distance и O (N) сравнений:

var closest = list.Select(item => new { item, distance = item.Distance(p) }) 
    .Aggregate((a, b) => a.distance <= b.distance ? a : b); 
var closestPt = closest.distance <= 1.0 ? closest.item : null;