c# - 在二维数组中选择相似项目组的算法

Question

有一个二维数组(在我的例子中，它们被称为Intersections)。

某个项目作为开始。任务是找到所有直接或间接连接到该项目的满足特定功能的项目。

所以基本算法是这样的:

将开始添加到结果列表中。 重复直到没有修改:将满足函数的数组中的每一项添加到结果列表中的任何一项。

我目前的实现是这样的:

private IList<Intersection> SelectGroup (
    Intersection start,
    Func<Intersection, Intersection, bool> select)
{
    List<Intersection> result = new List<Intersection> ();

    Queue<Intersection> source = new Queue<Intersection> ();
    source.Enqueue (start);

    while (source.Any ()) {
        var s = source.Dequeue ();
        result.Add (s);

        foreach (var neighbour in Neighbours (s)) {
            if (select (start, neighbour)
                && !result.Contains (neighbour)
                && !source.Contains (neighbour)) {
                source.Enqueue (neighbour);
            }
        }
    }

    Debug.Assert (result.Distinct ().Count () == result.Count ());
    Debug.Assert (result.All (x => select (x, result.First ())));

    return result;
}

private List<Intersection> Neighbours (IIntersection intersection)
{
    int x = intersection.X;
    int y = intersection.Y;

    List<Intersection> list = new List<Intersection> ();

    if (x > 1) {
        list.Add (GetIntersection (x - 1, y));
    }
    if (y > 1) {
        list.Add (GetIntersection (x, y - 1));
    }
    if (x < Size) {
        list.Add (GetIntersection (x + 1, y));
    }
    if (y < Size) {
        list.Add (GetIntersection (x, y + 1));
    }

    return list;
}

(select 函数接受起始项并返回 true，前提是第二项满足。)

这完成了它的工作，结果证明对于通常的数组大小(大约 20*20)来说速度相当快。但是，我对进一步改进很感兴趣。有什么想法吗？

示例(X 满足与其他 X 的关系，. 永远不会满足):

....
XX..
.XX.
X...

在这种情况下，有 2 个组:一个由 4 个项目组成的中央组和左下角的一个由单个项目组成的组。选择组(例如通过起始项 [3, 3])返回前者，而后者可以使用起始项和唯一返回值 [1, 4] 选择。

示例 2:

.A..
..BB
A.AA

这次有4组。 3 个 A 组没有连接，因此它们作为单独的组返回。较大的 A 和 B 组已连接，但 A 与 B 无关，因此它们作为单独的组返回。

Answer 1

第 1 步:微小的改变带来巨大的 yield
简单、即时的改进:您的 result.Contains 和 source.Contains 成员资格都在列表类型中，因此它们的大小为 O(n)，效率不高。由于您真的不关心任何特定的顺序，我会将它们都更改为 HashSet 以进行恒定时间查找。
请注意，在最坏的情况下，您当前的实现将是 O(n^2)，这发生在整个数组有效时(当您插入最后几个元素时，您将检查每个元素与整个其余网格)。

第二步:进一步优化
更好的结构更改:保留一个与 Intersection 数组大小相同的 bool visited 数组，并且每次查看 Intersection 时，将其标记为已访问。这样，您不必每次都检查 result 或 source 中是否有内容，更好的是，您不必重新评估您的 选择 谓词。否则，给出这样的东西:

XXX
X.X
XXX

您将对中心点上的 select 求值四次，如果它很昂贵，这可能会很糟糕。这样，您的

if (select (start, neighbour)
  && !result.Contains (neighbour)
  && !source.Contains (neighbour))

条件变为:if (!visited(neighbor) && select(start, neighbour)，它只会在任何给定的交叉点上最多评估一次 select。< br/> 此外，如果您这样做，您甚至不需要再制作 result 和 contains 哈希，因为您不会对它们进行包含检查。