DOMの要素をすばやく選択する

Question

背景：私の大学のコースの1つでは、私はChessを作っています。 GUIはすでにコントローラーへのフックで終了しています。私がしなければならないことは、オブジェクトを実装することだけです。伝統的には、オブジェクトの種類ごとに固有のネイティブ構造を使用します。移動履歴のスタック（サポートを元に戻しますが、やり直しはできません）、ボードの2次元配列/ベクトルなどを使用します。仕様の一部は、特殊な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のライブラリを使用します。

Answer 1

ボードチェスは固定された次元を持っているので、私はDOMNodeポインタの2D配列を使うことにしました。それは非常に速く、いくつかのコードの複雑さを追加しますが、うまく動作します。

私は物事を行う別の方法を知りたがります。

Answer 2

XML構造を使用するように強制することで、スピード障害を自分で作成しました。これはすべて、あなたがゲームをプレイしているときよりもはるかに少ない頻度で、ゲームをプレイするよりも速く保存/読み込みできることを示しています。したがって、ネイティブ構造を使用して必要な速度を取得し、ネイティブ構造をXMLにマップするためのシリアライゼーションコードを記述することをお勧めします。

あなたのスピードの問題について興味があります：O（n）vs O（1）は、nが大きい場合にのみ問題になります。 O（n）の検索が問題であることが実際にはたくさんありますか？時間の複雑さは、実行速度の理論的ガイドにすぎません。これは実装されることに留意する必要があります。実装上、理論的に最良の選択肢でない場合でもトレードオフはOKです。