Быстрый выбор элементов в DOM - PullRequest
Новая
       7

Быстрый выбор элементов в DOM

0 голосов
/ 09 ноября 2011

Фон: Для одного из моих университетских курсов я занимаюсь шахматами. GUI уже закончен с подключениями к контроллеру, все, что мне нужно сделать, это реализовать объекты. Традиционно я просто использовал бы собственные структуры, подходящие для каждого типа объектов, стек для истории перемещений (поддерживается отмена, но не повтор), 2d массив / вектор для доски и т. Д. Часть спецификации заключается в том, что мне нужно загрузить и сохранить игру в специализированном формате XML, поэтому мне хочется просто использовать DOMDocument для хранения игры целиком. Это сделало бы загрузку и сохранение чрезвычайно легкими, если бы у меня была библиотека, которая реализует действия загрузки / сохранения DOM, потому что мне больше не нужно переводить между XML и моими структурами.

Проблема: Скорость. Во всех алгоритмах в шахматах мне приходится много выбирать по локациям.

Формат XML (неизменяемый): 

<board>
        <piece type="rook" color="white" column="0" row="7"/>
        <piece type="knight" color="white" column="1" row="7"/>
        <piece type="bishop" color="white" column="2" row="7"/>
        <piece type="queen" color="white" column="3" row="7"/>
        <piece type="king" color="white" column="4" row="7"/>
        <piece type="bishop" color="white" column="5" row="7"/>
        <piece type="knight" color="white" column="6" row="7"/>
        <piece type="rook" color="white" column="7" row="7"/>
        <piece  color="white" column="3" row="6" type="pawn"/>
        <piece row="6" type="pawn" color="white" column="4" />
</board>

Теперь я должен получить все элементы фигуры и отфильтровать атрибуты, операция O (n). В реализации массива / вектора я могу легко достичь времени O (1), потому что это простая индексация. Цена O (n) слишком высока, особенно при обнаружении патовой ситуации.

Как бы вы улучшили скорость? Я в основном ищу способы индексирования DOM. У меня были некоторые идеи, но как бы вы решили эту проблему?

Для справки, я занимаюсь разработкой на C ++ и, вероятно, буду использовать библиотеку Xerces для XML, хотя я в основном ищу идеи, а не реальный код (хотя это было бы полезно) .

Ответы [ 2 ]

1 голос
/ 15 ноября 2011

Поскольку доска для шахмат имеет фиксированные размеры, я решил использовать двумерный массив DOMNode указателей.Это очень быстро, и хотя это добавляет некоторую сложность кода, он работает просто отлично.

0 голосов
/ 09 ноября 2011

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

Мне любопытно узнать о ваших проблемах со скоростью: O (n) против O (1) - это проблема, только когда n большое. Неужели будет большое количество фрагментов, в которых поиск O (n) является проблемой? Временная сложность - это просто теоретическое руководство по скорости исполнения. Вы должны иметь в виду, что это будет реализовано, и в вашей реализации компромиссы могут быть в порядке, даже если они не являются теоретически лучшим выбором (то есть выбор O (n) над O (1))

...