列表中满足条件的所有元素的最小值

Question

我有一个二维点class如下：

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（初始化为 1e6）和一个 minID，遍历列表以找到最小值。在遍历之外，我检查了这个最小值是否小于阈值。成功了。

但我想看看是否有 better/cleaner 方法来实现它，最后我得到了这个：

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

有几点可以改进：

删除第一个 Select 语句，因为它没有用？你对这一点什么都不做；这也允许您删除第二个 Select 语句。
不要使用ToList：反正你对构建这个列表不感兴趣；
Math.Pow是一种用于任意幂的方法，而且不是那么精确，用x*x代替Math.Pow(x,2)；
你在大写方面犯了一些小错误，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();

如果不存在这样的项目（满足 Where 子句），这将 return null。然而，在大多数情况下，这并不是绝对最有效的实施方式。

另一种方法是先实现一个扩展方法：

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 和我自己的两种方法，尽管使用的是你提供的小测试集，所以结果在科学上并不有效，并使用csharp 互动 shell:

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 2

我宁愿使用下面的，它进行 O(N) 距离计算和 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;

Answer 3

我对问题的两个解决方案有一些想法，这里是原始的 class，去掉了不必要的下划线。通常 id 是唯一的，所以 readonly 我从@CommuSoft 的回答中借用了 Distance 方法，因为他对那个方法是正确的：

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

共享部分：

        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 在使用 memory/allocation 和计算效率方面最有效：

        //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 为 null 或最接近 p.

的实例

基准：

必须在发布模式下构建，
必须运行没有调试，在 VisualStudio 之外，
两个场景的测试运行ning 5 次，
场景X：3项，1000万次，所有方法，时间毫秒，
场景 Y：300 万次，1 次，所有方法，时间以毫秒为单位，

the code is here

基准测试结果：

B - 列表的迭代次数，
I - 列表中的项目数，
所有数字以毫秒为单位，
CommuSoft 是 CommuSoft 的答案中的解决方案，
Ivan Stoev 提出了匿名类型的解决方案，其行为类似于带有结构的 VersionA2，
显然 IpavluVersionA2 是最佳性能。

B[10000000] I[3]: CommuSoft: 3521 IpavluA1: 371 IpavluA2: 195 IpavluB: 1587

B[10000000] I[3]: CommuSoft: 3466 IpavluA1: 371 IpavluA2: 194 IpavluB: 1583

B[10000000] I[3]: CommuSoft: 3463 IpavluA1: 370 IpavluA2: 194 IpavluB: 1583

B[10000000] I[3]: CommuSoft: 3465 IpavluA1: 370 IpavluA2: 194 IpavluB: 1582

B[10000000] I[3]: CommuSoft: 3471 IpavluA1: 372 IpavluA2: 196 IpavluB: 1583

B1 I[3000000]: CommuSoft: 919 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

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

B1 I[3000000]: CommuSoft: 962 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

B1 I[3000000]: CommuSoft: 969 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

B1 I[3000000]: CommuSoft: 961 IpavluA1: 21 IpavluA2: 17 IpavluB: 75

列表中满足条件的所有元素的最小值

Minimum value of all elements that satisfy a condition in a list

c#

list

traversal