Linq中嵌套Select的替代方案是什么？

Question

在一个集群项目上工作时，我遇到了这个问题，并且正在尝试找出比我想出的更好的解决方案。

问题：给定一个点列表List Points在R^n中的点（您可以将每个点视为维度n的双数组），一个double minDistance和一个距离Func dist，请编写一个LINQ表达式，对于每个点，返回在列表中比minDistance更接近他的其他点集合，根据dist计算。

我的解决方案如下：

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

因为要计算每个距离两次，使用LINQ可能不是最佳选择。

这个问题没有太多实际用途。

即使我的代码看起来很糟糕，但它也能工作。

我有以下问题：

1. 是否可以将我的代码转换为查询表达式？如果可以，如何转换？
2. 是否有更好的使用点表示法解决此问题的方法？

- Save

---

编译器似乎不喜欢双引号中的“from x in Points”。为什么？你尝试了什么？出现了什么错误？ - SLaks

你认为在内部查询中，Points.Select(y => y) 相对于 Points 有什么好处？ - Jon Skeet

@Jon Skeet：你说得完全正确，内部选择根本不需要。现在我感觉很愚蠢 :) - Save

@SLaks：在写了两个from x in points和第二个的where子句之后，我无法弄清如何返回正确的列表...编译器部分只是我的疏忽。 - Save

Answer 1

问题定义是想要“对于每个点，找到其他点的集合”，这使得没有内部查询是不可能解决的 - 你只能巧妙地伪装它。如果您可以改变数据存储策略，并且不坚持使用LINQ，那么通常有许多方法来解决最近邻搜索问题（Nearest Neighbour Search）。例如，您可以根据一个轴上的值对点进行排序，这可以通过在完全距离计算之前消除一些候选项来加速邻居查询。这是一个采用此方法的论文：Flexible Metric Nearest Neighbor Classification。

- BartoszKP

Answer 2

因为Points是一个List，所以您可以利用它可以通过索引访问每个项目的事实。因此，您可以避免像这样两次比较每个项目：

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

这将返回一个由所有彼此之间距离小于minDistance的点组成的集合，但不完全是您想要的结果。如果您想将其转换为某种Lookup，以便查看哪些点靠近给定点，则可以执行以下操作：

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

- p.s.w.g

Answer 3

我认为你可以在Point类中添加一些布尔型Property，以标记它是否已被浏览，以防止两次调用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();

- King King