寻找包含单元格的一组区域的算法

Question

我正在处理一些电子表格数据，其中有一组任意边界的单元格区域。给定任何一个单元格，确定包含该单元格的区域子集的最快方法是什么？

目前，我最好的办法是按照以下方式对区域进行排序：首先按区域起始行索引排序，其次是结束行索引、起始列索引，然后是结束列索引。当我想要基于给定的单元格进行搜索时，我二分查找第一个起始行索引在该单元格行索引之后的区域，然后检查该区域之前的所有区域是否包含该单元格，但这种方法太慢了。

- Mike Dour

---

区域集合是否会改变，还是可以预处理它们？ - Marcelo Cantos

它们可能会改变，但不会经常改变，因此让我们假设它们可以被预处理。 - Mike Dour

如果您不介意的话，这个应用程序是什么？ - jtolle

我有一个读写Excel文件的代码库，但它也可以解决公式。当单元格值被设置时，我需要使引用该单元格的所有公式无效。如果公式引用了区域并且单元格在该区域内，那么该公式也必须无效。因此，如果单元格B2的值更改，而存在一个公式为=SUM(A1:C3)，则需要重新计算该公式。我正在调查客户的性能错误，并发现他们的Excel文件中加载了大约70,000个引用区域的公式。 - Mike Dour

Answer 1

根据一些谷歌搜索，这是二维点包围搜索问题的一个例子，或者称为“刺穿问题”。请参见：

http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf

从这里开始（从第21/52页）：

http://www.cs.brown.edu/courses/cs252/misc/slides/orthsearch.pdf

涉及的关键数据结构是线段树：

http://en.wikipedia.org/wiki/Segment_tree

对于二维情况，看起来可以构建一个包含线段树的线段树，并获得O(log^2(n))的查询复杂度。（我认为你当前的解决方案是O(n)，因为平均而言，你只会用二分查找排除一半的区域。）

然而，你说“电子表格”，这意味着你可能有一个相对较小的区域要处理。更重要的是，你有整数坐标。而且你说“最快”，这意味着你可能愿意为更快的查询交换空间和设置时间。

你没有说哪个电子表格，但下面的代码是一个极其低效但非常简单的Excel/VBA实现的二维查找表，一旦设置完成，具有O(1)的查询复杂度：

Public Sub brutishButShort()
    Dim posns(1 To 65536, 1 To 256) As Collection

    Dim regions As Collection
    Set regions = New Collection

    Call regions.Add([q42:z99])
    Call regions.Add([a1:s100])
    Call regions.Add([r45])

    Dim rng As Range
    Dim cell As Range
    Dim r As Long
    Dim c As Long

    For Each rng In regions
        For Each cell In rng
            r = cell.Row
            c = cell.Column

            If posns(r, c) Is Nothing Then
                Set posns(r, c) = New Collection
            End If

            Call posns(r, c).Add(rng)
        Next cell
    Next rng

    Dim query As Range
    Set query = [r45]

    If Not posns(query.Row, query.Column) Is Nothing Then
        Dim result As Range
        For Each result In posns(query.Row, query.Column)
            Debug.Print result.address
        Next result
    End If
End Sub

如果您需要处理更大的网格或者区域相对于网格来说很大，那么使用两个一维查找表可以节省大量空间和设置时间。但是，这样您就需要进行两次查找，并取两个结果集的交集。

- jtolle

---

谢谢，这非常有帮助。我不能使用暴力算法，因为我正在处理Excel 2007数据，所以可能有1048576行乘以65536列，那将会使用太多的内存。我也不能使用线段树，因为虽然区域不经常添加，但它们偶尔会被添加，所以建立树的时间会导致太大的减速。但我认为两个一维区间树可能是正确的方法。我会试一下。 - Mike Dour

实际上我想要的是两个简单的一维查找，而不是真正的树形结构。你可以像上面那样建立它们，只需将每个区域的行预处理为行查找，列为列查找等。然后你仍然需要找出两个查找结果之间的唯一区域，但这可以通过 Scripting.Dictionary 轻松完成。 - jtolle

而且逐步添加到查找表非常容易。使用上述方法从中删除需要在集合中使用字符串键。只要您确定您的区域永远不相同，就可以使用区域地址。 - jtolle

哦，我明白了。这不是一个坏主意，除了现在我将分配多达1114112个集合，我想这并不可怕。我可能会尝试采用混合方法，创建您的查找表，但是每次创建128行/列的块。这将限制我的最大集合计数为8704，但会稍微增加查找时间，因为我必须检查返回集中的每个区域以查看它是否包含单元格。我认为我会实现这个以及两个一维区间树，并查看哪个在实际代码中更快。再次感谢。 - Mike Dour

是的，根据您对区域数量和分布的了解，空间和时间之间存在各种潜在的中间权衡。我建议从最简单/粗暴的方式开始，然后根据需要逐步转向更复杂/高效的方式。 - jtolle

经过一些工作后，我意识到可以使用线段树（类似的东西）。我创建了一个一维线段树，当添加段时生成线段。我能够做到这一点是因为行和列的数量是有限的。我只是假设每一行或每一列都可能成为未来某个线段的终点，并且需要完整的树。但是在实际需要存储线段或者它们有一个必须存储线段的子节点之前，我不会在树中创建任何节点。我为行和列各使用一个树，然后取交集以得到单元格的结果。 - Mike Dour

Answer 2

我认为您想确定单元格和区域的交集是否为空

Sub RegionsContainingCell(rCell As Range, ParamArray vRegions() As Variant)

    Dim i As Long

    For i = LBound(vRegions) To UBound(vRegions)
        If TypeName(vRegions(i)) = "Range" Then
            If Not Intersect(rCell, vRegions(i)) Is Nothing Then
                Debug.Print vRegions(i).Address
            End If
        End If
    Next i

End Sub

Sub test()

    RegionsContainingCell Range("B50"), Range("A1:Z100"), Range("C2:C10"), Range("B1:B70"), Range("A1:C30")

End Sub

- Dick Kusleika

---

这是一个O(N)算法。由于我正在处理大量区域，所以我需要更快的算法。不过还是谢谢你的帮助。 - Mike Dour