Алгоритм нахождения множества областей, содержащих ячейку - PullRequest
Новая
       19

Алгоритм нахождения множества областей, содержащих ячейку

3 голосов
/ 28 октября 2010

Я работаю с некоторыми данными электронной таблицы, и у меня есть набор областей ячеек, которые имеют произвольные границы. Для любой ячейки, какой самый быстрый способ определить подмножество областей, которые содержат ячейку?

В настоящее время лучшее, что у меня есть, - это отсортировать регионы с основным полем сортировки, представляющим собой индекс начальной строки региона, за которым следует индекс его конечной строки, индекс начального столбца и затем индекс конечного столбца. Когда я хочу выполнить поиск по заданной ячейке, я выполняю двоичный поиск по первой области, чей начальный индекс строки находится после индекса строки ячейки, а затем проверяю все области до этой, чтобы увидеть, содержат ли они ячейку, но это слишком медленно .

Ответы [ 2 ]

1 голос
/ 29 октября 2010

Основываясь на некотором поиске в Google, это пример проблемы поиска двумерных точечных вложений или «проблемы с закалыванием». См:

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

Если вам нужно беспокоиться о более крупной сетке или о больших областях относительно сетки, вы можете сэкономить массу пространства и времени на установку, используя вместо этого две одномерные справочные таблицы. Тем не менее, у вас есть два поиска плюс необходимость пересечения двух результирующих наборов.

0 голосов
/ 29 октября 2010

Я думаю, что вы хотите определить, является ли пересечение ячейки и области 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
...