c# - Linq 中嵌套选择的替代方案

Question

在一个集群项目上工作时，我偶然发现了这一点，我试图弄清楚是否有比我想出的更好的解决方案。

问题：给定List<Point> PointsR^n 中的 a 个点（您可以将每个 Point 视为维度 n 的双精度数组）、adouble minDistance和 a distance Func<Point,Point,double> dist，编写一个 LINQ 表达式，该表达式为每个点返回列表中其他点的集合根据 dist 比 minDistance 更接近他。

我的解决方案如下：

        var lst = Points.Select( 
                x => Points.Where(z => dist(x, z) < minDistance)
                    .ToList() )
                .ToList();

所以，注意到之后

• 使用 LINQ 可能不是最好的主意，因为您要计算每个距离两次
• 这个问题没有太大的实际用途
• 我的代码，即使看起来很糟糕，也可以工作

我有以下问题：

1. 是否可以在查询表达式中翻译我的代码？如果是这样，如何？
2. 有没有更好的方法来用点表示法解决这个问题？

Answer 1

您想要“对于每个点，其他点的集合”的问题定义使得如果没有内部查询就无法解决 - 您可以巧妙地伪装它。如果您可以更改数据存储策略，并且不坚持使用 LINQ，那么，一般来说，有很多方法可以解决最近邻搜索问题。例如，您可以将根据其值排序的点保留在一个轴上，这可以通过消除早期的一些候选者而无需进行全距离计算来加快对邻居的查询。这是采用这种方法的论文：灵活度量最近邻分类。

Answer 2

Because Points is a List you can take advantage of the fact that you can access each item by its index. So you can avoid comparing each item twice with something like this:

var lst = 
    from i in Enumerable.Range(0, Points.Length)
    from j in Enumerable.Range(i + 1, Points.Length - i - 1)
    where dist(Points[i], Points[j]) < minDistance
    select new 
    {
        x = Points[i], y = Points[j]
    };

This will return a set composed of all points within minDistance of each other, but not exactly what the result you wanted. If you want to turn it into some kind of Lookup so you can see which points are close to a given point you can do this:

var lst = 
    (from i in Enumerable.Range(0, Points.Length)
     from j in Enumerable.Range(i + 1, Points.Length - i - 1)
     where dist(Points[i], Points[j]) < minDistance
     select new { x = Points[i], y = Points[j] })
    .SelectMany(pair => new[] { pair, { x = pair.y, y = pair.x })
    .ToLookup(pair => pair.x, pair => pair.y);

Answer 3

Property我认为您可以在您的课程中添加一些 bool来Point标记它已被浏览，以防止两次调用 to dist，如下所示：

public class Point {
   //....
   public bool IsBrowsed {get;set;}
}
var lst = Points.Select( 
                 x => {
                       var list = Points.Where(z =>!z.IsBrowsed&&dist(x, z) < minDistance).ToList();
                       x.IsBrowsed = true;
                       return list;
                      })
                 .ToList();