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

Question

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

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

XML Format (неизменяемый):

<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, хотя в основном я ищу идеи, а не фактический код (хотя это было бы полезно).

Answer 1

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

Хотелось бы, чтобы я знал о другом способе делать что-то.

Answer 2

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

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