Поиск выделенных границ из импорта в Excel - PullRequest
Новая
       20

Поиск выделенных границ из импорта в Excel

0 голосов
/ 13 марта 2010

Я импортирую огромное количество данных из Excel, которые имеют различные макеты таблиц. У меня достаточно хороших процедур обнаружения таблиц и обработки ячеек слияния, но я сталкиваюсь с проблемой, когда дело доходит до работы с границами. А именно производительность. Граничные области в некоторых из этих файлов имеют значение.

Настройка данных:
Я импортирую напрямую из Office Open XML, используя VB6 и MSXML. Данные анализируются из XML в словарь данных ячейки. Это удивительно и так же быстро, как и использование docmd.transferspreadsheet в Access, но дает гораздо лучшие результаты. Каждая ячейка содержит указатель на элемент стиля, который содержит указатель на элемент границы, который определяет видимость и вес каждой границы (так же структурируются данные в OpenXML).

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

Что я сделал:
Сначала я создал подпрограмму заполнения BFS (поиск в ширину), чтобы найти эти области. Это прекрасно и быстро работает для электронных таблиц «нормального» размера, но становится слишком медленным для импорта в тысячи строк. Одна из проблем заключается в том, что граница в Excel может храниться в проверяемой ячейке или в противоположной границе в соседней ячейке. Это нормально, я могу консолидировать эти данные при импорте, чтобы уменьшить количество необходимых проверок.

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

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

1 Ответ

1 голос
/ 13 марта 2010

Ваш вопрос довольно сложный, но звучит так, как будто вам нужен алгоритм для поиска связанных компонентов графа (связанный компонент = набор узлов, все соединены друг с другом, но без других узлов), что может быть выполнено влинейное время при повторных обходах.Псевдокод: 

FindComponents(G):
    For all vertices v in G:
        Let C be a mutable empty collection
        Traverse(G, C, v)
        If C is nonempty, then it is a connected component

Traverse(G, C, v):
    If v has not been visited:
        Mark v as visited
        Add v to C
        For each neighbor w of v in G:
            Traverse(G, C, w)

Итерационный вариант Traverse: 

Traverse(G, C, r):
    Let S be an empty stack
    Push r onto S
    While S is not empty:
        Pop the top element v of S
        If v is not marked as visited:
            Mark v as visited
            Add v to C
            For each neighbor w of v in G:
                Push w onto S
...