3

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

目前，我最好的方法是对区域进行排序，主排序​​字段是区域的起始行索引，然后是结束行索引，起始列索引，然后是结束列索引。当我想基于给定的单元格进行搜索时，我对第一个区域进行二进制搜索，该区域的起始行索引在单元格的行索引之后，然后我检查该区域之前的所有区域以查看它们是否包含该单元格，但这太慢了.

4

2 回答 2

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

如果您需要担心较大的网格或相对于网格较大的区域，则可以通过使用两个一维查找表来节省大量空间和设置时间。但是，您有两个查找，加上需要取两个结果集的交集。

于 2010-10-29T04:05:42.233 回答
0

我想你想确定单元格和区域的相交是否为 Nothing

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
于 2010-10-29T12:53:28.160 回答