3

いくつかのスプレッドシートデータを使用していて、任意の境界のセル領域のセットがあります。任意のセルが与えられた場合、セルを含む領域のサブセットを決定するための最速の方法は何ですか？

現在、私が持っている最善の方法は、プライマリソートフィールドがリージョンの開始行インデックスであり、その後に終了行インデックス、開始列インデックス、終了列インデックスが続く領域をソートすることです。特定のセルに基づいて検索する場合、開始行インデックスがセルの行インデックスの後にある最初の領域をバイナリ検索し、その前のすべての領域をチェックして、セルが含まれているかどうかを確認しますが、これは遅すぎます。

4

2 に答える 2

1

いくつかのグーグルに基づいて、これは2次元のポイントエンクロージャ検索問題、または「刺し傷問題」の例です。見る：

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

ここの（p.21 / 52から）：

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

関連する主要なデータ構造は、セグメントツリーです。

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

2次元の場合、セグメントツリーを含むセグメントツリーを構築し、O（log ^ 2（n））クエリの複雑さを取得できるようです。（平均して、バイナリ検索でリージョンの半分を除外するだけなので、現在のソリューションはO（n）だと思います。）

ただし、「スプレッドシート」とおっしゃっていましたが、これはおそらく、作業する領域が比較的小さいことを意味します。さらに重要なのは、整数座標を持っていることです。そして、あなたは「最速」と言いました。これは、おそらくスペースとセットアップ時間をより高速なクエリと交換する用意があることを意味します。

どのスプレッドシートかはわかりませんが、以下のコードは非常に非効率的ですが、2Dルックアップテーブルのダートシンプルでブルートフォースの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

心配するグリッドが大きい場合、またはグリッドに比べて領域が大きい場合は、代わりに2つの1-Dルックアップテーブルを使用することで、スペースとセットアップ時間を大幅に節約できます。ただし、2つのルックアップがあり、さらに2つの結果セットの共通部分を取得する必要があります。

于 2010-10-29T04:05:42.233 に答える
0

セルと領域の交差が何もないかどうかを判断したいと思います

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 に答える