13

次のようなツリー構造があります。モデルにはルート ノードがあり、各ノードには任意の数の子ノードと任意の数のメッシュがあります。

私のアプリケーションでは、多くの時間がこのツリーをたどり、視錐台カリングや行列乗算などの計算に費やされています。現在、各ノードには子ノードとメッシュのベクトルがあり、ツリーは再帰的に走査されます。これは非常に遅いです。

私はデータ指向の設計を見てきましたが、非常にキャッシュフレンドリーであるという考えが気に入っています。私はこのようなことを考えてきました：

struct Mesh
{
    // misc data
    MeshID mMeshID;
}

// probably needs more information?
struct Node
{
    // begin and end index into Models 'mNodes'
    uint32_t mChildrenBegin;
    uint32_t mChildrenEnd;

    // as above but for meshes
    uint32_t mMeshesBegin;
    uint32_t mMeshesEnd;
}

struct Model
{
    std::vector<Node> mNodes;
    std::vector<Mesh> mMeshes;
}

ここで、ツリーを走査して可視メッシュのリストを取得する必要があります。各ノードで、ノードが表示されているかどうかを確認する必要があります。次のブランチ:

  • ノードが表示されます。その下のすべての子ノードとメッシュも表示されます。このブランチに深く入り込まないでください。同じ深さの他のノードを確認してください。
  • ノードは表示されません。このノードまたはその下の子ノードまたはメッシュは表示されません。このブランチに深く入り込まないでください。同じ深さの他のノードを確認してください。
  • ノードが部分的に表示されます。一部のノードおよび/または一部のメッシュが表示されます。階層をさらに深くする必要があります。

ツリーは静的です。モデルがアプリケーションに読み込まれると、ツリーが変更されることはありません。したがって、この情報を使用して効率的な構造を取得できるはずです。

私はこれにどのようにアプローチするか困惑しています。

いくつか質問があります。

  1. ノードをメモリに配置するにはどうすればよいですか? 最初のインデックスのルート ノードですか? 他のノードは深度に基づいて追加されますか?
  2. 再帰を使用せずにツリーを反復するにはどうすればよいですか? 本当に必要でない限り、各ノードにアクセスしたくありません。たとえば、depth=2 のノードが表示されない場合、そのすべてのメッシュと子 (およびそれらのメッシュ) をテストするのではなく、完全にスキップする必要があります。
4

3 に答える 3

5

深さ優先の走査順序でメモリ内の単一の配列としてツリーを表すことができます

struct Node {
    ... node data ...
    int next;
};

std::vector<Node> nodes;

nextフィールドは、次のノードのインデックスを同じかそれ以上のレベルに保ちます。ノードの最初の子は、シーケンス内の現在のノードに続くノードであるため、明示的には述べられていません (next もそれを指している場合を除きます。その場合、現在のノードには子がありません)。たとえば、ツリーでは次のようになります。

ここに画像の説明を入力

赤い矢印はnextが指している場所を表します。

たとえば、レンダリングのトラバースは次のようになります。

void check(int ix) {
    switch(nodes[ix].visibility()) {
        case VISIBLE:
            // Draw whole subtree, no more checking needed
            for (int i=ix,e=nodes[ix].next; i!=e; i++) {
                nodes[i].draw();
            }
            break;
        case PARTIALLY_VISIBLE:
            nodes[ix].draw();
            for (int c=ix+1, e=nodes[ix].next; c!=e; c=nodes[c].next) {
                check(c);
            }
            break;
    }
}

明示的なスタックを保持することで、同じコードを非再帰に変換することもできます (ノードの操作とチェックが非常に高速であるか、ツリーが非常に深い場合を除き、なぜそれが良い考えなのかはわかりません)。

于 2015-02-21T07:47:44.430 に答える
2

短いバージョン: 代わりに 6502 の予約注文の回答を使用してください。興味深いコードとコメントがまだいくつかあるため、以前の回答を以下に残しておきます。

ストレージ アレイをセミ プレオーダー方式でレイアウトします。つまり、センチネル エンド ノード、ルート、最初のルートの子、最初のルートの最初の子の子、最初のルートの最初の孫の子などです。次に、直接の祖先とその兄弟のインデックス情報のコピーをスタックに保持する、再帰的なセミプレオーダー トラバーサルを使用してツリーをトラバースします。このように、トラバーサルはストレージ アレイを左から右にバックトラッキングなしでスキャンします。再帰を使用してすべてのノードにアクセスする必要はありません。サブツリーをスキップしても、ストレージ アレイ内でスキャンがジャンプするだけです。

model.semiPreOrderTraversalRecur(model.getEnd());  // traverse the whole tree

...

// NOTE: pass prnt by *COPY* -- break Node into index portion and app. data portion; we only need the index portions here

void Model::semiPreOrderTraversalRecur(Node prnt)
{  
  Node children[prnt.mChildrenEnd - prnt.mChildrenBegin];  // just index info
  uint32_t i;

  // visit children of prnt; determine visibility etc.

  for (i = prnt.mChildrenBegin; i < prnt.mChildrenEnd; ++i)
  {
    cout << "Visiting " << mNodes[i].mVal << endl;
    mNodes[i].mInvisible = false;  // TODO: determine based on culling, etc.
    children[i - prnt.mChildrenBegin] = mNodes[i];  // just index info
  }

  // recurse on children as necessary

  for (i = 0; i < prnt.mChildrenEnd - prnt.mChildrenBegin; ++i)
    if (!children[i].mInvisible && children[i].mChildrenBegin != children[i].mChildrenEnd)
      semiPreOrderTraversalRecur(children[i]);
}

長いバージョン (これの一部は省略されています): Node 構造にもう少し情報を追加することで、目的を達成できると思います: Node の親のインデックスと現在の Node のインデックス。(後者は、おそらく Node へのポインタと Node ストレージ ベクトルから導出できるため、厳密には必要ない場合があります。)

これにより、ツリー内の任意のノードを指定して、必要に応じて兄弟に「上」、「下」、または「横」に簡単に移動するのに十分なコンテキスト情報が得られます。「上」に移動するには、単に親インデックスに移動します。下に移動するには、子インデックスのいずれかに移動します。兄弟に「横向き」に移動するには、現在のノードのインデックスを増減するだけです（親の最後の/最初の子ではないことを確認した後）。

ノード構造とメッシュ構造を組み合わせて、それらを 1 つのベクトルに連続して格納できるようにすることを検討してください。ガチョウに適したキャッシュ パフォーマンスは、通常、ガチョウにも適しています。メッシュが別のベクトルに保存されていると、ノードの兄弟からメモリ内で遠く離れている可能性が高く、トラバーサルの途中でそれらにアクセスすると、キャッシュにより多くの圧力がかかります。もちろん、メッシュがノードよりもはるかに多くのデータを持っている場合 (またはその逆)、またはトラバーサル中にメッシュにアクセスする必要がない場合、これはメモリを浪費するため、適切なオプションではない可能性があります。また、メッシュはターミナル ノードであり、ノードの子にアクセスするときに特殊なケースになる可能性があるため、すべてのツリー インデックスは必要ない可能性があります。詳細によっては、メッシュを個別に格納するという独自の提案が優れている場合があります。

以下のコードでは、ノード構造とメッシュ構造を組み合わせて、単一のベクトルに格納しています。

#include <cstdint>
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <thread>

using namespace std;

struct Node
{
  uint32_t mParentIndex;    // index of parent Node in Model
  uint32_t mIndex;          // index of this Node in Model (may be possible to derive this from Node pointer and Model's vector rather than storing it)

  uint32_t mChildrenBegin;  // begin and end index of children Node in Model
  uint32_t mChildrenEnd;

  bool     mInvisible;      // used during semiPreOrderTraversal to remember no need to traverse subtree rooted at this Node

  int      mVal;            // dummy data for debugging
};

struct Model
{
  vector<Node> mNodes;  // preferably private, but your call

  Model(istream *in = NULL);

  Node *getEnd(void) { return &mNodes[0]; }  // sentinel end node that always exists and has itself as parent
  Node *getRoot(void) { return getChild(getEnd()); }

  Node *getParent(Node *curr) { return &mNodes[curr->mParentIndex]; }  // always safe to call; returns end as sentinel
  Node *getNextSibling(Node *curr) { Node *prnt = getParent(curr); return (curr->mIndex && curr->mIndex + 1 < prnt->mChildrenEnd ? &mNodes[curr->mIndex + 1] : NULL); }
  Node *getPrevSibling(Node *curr) { Node *prnt = getParent(curr); return (curr->mIndex > prnt->mChildrenBegin ? &mNodes[curr->mIndex - 1] : NULL); }
  Node *getChild(Node *curr, unsigned nth_child = 0) { unsigned index = curr->mChildrenBegin + nth_child; return (index < curr->mChildrenEnd ? &mNodes[index] : NULL); }

  void semiPreOrderTraversal(void);
  void semiPreOrderTraversalRecur(Node prnt);

private:
  int  buildFromStreamRecur(Node *curr, int val, istream &in);
};

void Model::semiPreOrderTraversal(void)
{
  Node *curr = getRoot();
  Node *next;

  cout << "Beginning Semi-Pre-Order traversal of tree!" << endl;

  if (NULL == curr)
    goto DONE;

  while (1)
  {
    // TODO: visit curr; determine and record mInvisible in curr

    cout << "Visiting " << curr->mVal << endl;
    curr->mInvisible = false;

    // try to move to sibling

    if (NULL == (next = getNextSibling(curr)))
    {
      // try to move to children of siblings

      curr = getChild(getParent(curr));  // move back to oldest sibling

      cout << "No more siblings to visit! Try to visit their children. Rewinding to oldest sibling " << curr->mVal << endl;

      while (curr->mInvisible || NULL == (next = getChild(curr)))
      {
        cout << "No children to visit of " << curr->mVal << endl;

        // shouldn't visit curr's children or it has no children
        // try to move to sibling

        if (NULL == (next = getNextSibling(curr)))  
        {
          cout << "Reached end of siblings again -> completed traversal of subtree rooted by parent " << getParent(curr)->mVal << endl;
          // ascend while we can't find a uncle to check for children to visit

          do {
            if (getEnd() == (curr = getParent(curr)))  
              goto DONE;  // got back to end -> traversal complete

            cout << "Moved back up to " << curr->mVal << endl;

          } while (NULL == (next = getNextSibling(curr)));

          cout << "Found a great^Nth uncle (" << next->mVal << ") to check for children to visit!" << endl;
        }
        // else check sibling for children to visit

        curr = next;
        cout << "Trying to visit children of " << curr->mVal << endl;
      }
      // visit children of curr

      cout << "Will visit children of " << curr->mVal << endl;
    }
    else
      cout << "Will visit sibling of " << curr->mVal << endl;

    curr = next;
  }

DONE:
  cout << "Finished Semi-Pre-Order traversal of tree!" << endl;
}

void Model::semiPreOrderTraversalRecur(Node prnt)
{  
  Node children[prnt.mChildrenEnd - prnt.mChildrenBegin];  // just index info
  uint32_t i;

  // visit children of prnt; determine visibility etc.

  for (i = prnt.mChildrenBegin; i < prnt.mChildrenEnd; ++i)
  {
    cout << "Visiting " << mNodes[i].mVal << endl;
    mNodes[i].mInvisible = false;
    children[i - prnt.mChildrenBegin] = mNodes[i];  // just index info
  }

  // recurse on children as necessary

  for (i = 0; i < prnt.mChildrenEnd - prnt.mChildrenBegin; ++i)
    if (!children[i].mInvisible && children[i].mChildrenBegin != children[i].mChildrenEnd)
      semiPreOrderTraversalRecur(children[i]);
}

Model::Model(istream *in)
{
  Node dmy, *end;

  mNodes.push_back(dmy);  // create sentinel end node

  end = getEnd();
  end->mParentIndex   = 0;
  end->mIndex         = 0;
  end->mChildrenBegin = 1;
  end->mChildrenEnd   = 1;
  end->mVal           = -1;  

  if (in)
    buildFromStreamRecur(getEnd(), 0, *in);
}

int Model::buildFromStreamRecur(Node *curr, int val, istream &in)
{
  uint32_t numChildren, i, currInd = curr->mIndex;

  // read in how many children curr will have

  in >> numChildren;

  // allocate children in mNodes and set curr's children references
  // NOTE: protect against reallocations of mNodes

  curr->mChildrenBegin = mNodes.size();

  for (i = 0; i < numChildren; ++i)
  {
    Node node;

    node.mParentIndex   = currInd;
    node.mIndex         = mNodes.size();
    node.mChildrenBegin = (uint32_t) -1;
    node.mChildrenEnd   = (uint32_t) -1;
    node.mVal           = val++;

    mNodes.push_back(node);
  }

  curr = &mNodes[currInd];
  curr->mChildrenEnd = mNodes.size();

  cout << "Node " << curr->mVal << " is complete! mParentIndex = " << curr->mParentIndex << "; mIndex = " << curr->mIndex
       << "; mChildrenBegin = " << curr->mChildrenBegin << "; mChildrenEnd = " << curr->mChildrenEnd << endl;

  // recursively build children
  // NOTE: protect against reallocations of mNodes

  for (i = 0; i < numChildren; ++i)
  {
    curr = &mNodes[currInd];
    curr = &mNodes[curr->mChildrenBegin + i];
    val = buildFromStreamRecur(curr, val, in);
  }

  return val;  
}

int main(int argc, char **argv)
{
  Model m(&cin);

  m.semiPreOrderTraversal();
  m.semiPreOrderTraversalRecur(*m.getEnd());

  return 0;
}

ツリー全体の非再帰的な事前順序走査は、次のようになります。

Node *curr = model.getRoot();  // TODO: handle empty tree
Node *next;
bool  shouldnt_visit_children;

while (1)
{
  // TODO: visit curr -- determine shouldnt_visit_children

  if (shouldnt_visit_children || NULL == (next = model.getChild(curr)))
  {
    // move to next sibling; if no siblings remain then ascend while no siblings remain

    while (NULL == (next = model.getNextSibling(curr)))
      if (model.getEnd() == (curr = model.getParent(curr)))
        goto DONE;

    curr = next;
  }
  else
    curr = next;  // descend to first child
}

DONE:;

そうは言っても、この種の実装（以前のようなリンクされた構造とは対照的に）がキャッシュパフォーマンスを大幅に向上させる可能性が高いという非常に明白な理由はわかりません。ベクターがどのように配置され、どのようにアクセスするかによって、キャッシュのパフォーマンスが決まります。とにかく、特定の方法でレイアウトしても、リンクされたツリーを同様に構築しても同様の結果が得られないという説得力のある理由はわかりません。たとえば、ベクターをセミプレオーダーの種類のツリートラバーサルでレイアウトすることを見つけた/信じている場合 (つまり、ベクターは次のようにレイアウトされます: 端、ルート、ルートの子、ルートの最初の子の子、ルートの最初の孫の子)など) アプリケーションに最適なキャッシュ パフォーマンスを提供します。その場合、メモリ アロケータが明示的に行う場合と同様の方法でツリーをメモリにパックする可能性が高いため、同じセミ プレオーダー ビルド順序を使用してリンク ツリーを構築すると、同様の結果が得られる可能性が高くなります。もちろん、構造や関連するアロケーターがインテリジェントであることに依存するのではなく、アプローチを使用してこれを確実に制御できます。

メモリ内のノードとメッシュのレイアウトを明示的に管理すると、キャッシュのパフォーマンスが向上する可能性があります。これは、オブジェクトをメモリ内に密にパックし、好みの種類のアクセス パターン/局所性を強制するように「強制」できるためです。同様の結果が得られる可能性が高く、特にツリーの構築が起動時に 1 回だけ行われる場合はそうです。

あなたの質問が示唆しているように、主に事前注文トラバーサルを行う場合は、上で説明したように、半事前注文方式でストレージ ベクトルをレイアウトすることをお勧めします: end、root、root's children、root's first child's children 、ルートの最初の孫の子供など。

PS - トラバーサルが常にルートから開始する場合は、Node の mParentIndex も削除し、代わりに、ツリーをたどって祖先の明示的なスタックを構築し、降りた後にツリーを遡ってトラバースできるようにすることができます (これはおそらく再帰は暗黙的に行いました)。任意の任意のノードからツリー内を移動できるようにする必要がある場合は、親のインデックスをノードに格納する必要があります。

編集:コメントの 1 つで述べたように、私が提案したセミ プレオーダー レイアウトには、ノードのすべての子孫メッシュを単純な数値範囲 [Node.mDescedantMeshBegin, Node.mDescendantMeshEnd) で表すことができるというプロパティもあります。提案どおりにメッシュを個別に保存します。したがって、ツリーをたどって可視メッシュの明示的なリストを作成する必要がある場合、または構築したい場合は、可視ノードを見つけるたびに、可視子孫メッシュのこの範囲全体を簡単にリストに組み込むことができます。

EDIT2:コードを大幅に更新しました。半予約注文の入力ストリームに基づいて、再帰的なモデ​​ル ビルダーを追加しました。いくつかのバグを修正しました。最も重要なことは、Model の非再帰的、半事前順序トラバーサルを行う関数を追加したことです。本当の予約注文トラバーサルほど単純ではありませんが、興味があるかもしれません. 再帰バージョンの方がはるかに簡単かもしれません - それを追加することを考えます。私のテストでは、ノードの訪問は mNode で左から右に非常にうまく進みます。ただし、ツリーを上に戻ると、メモリ アクセスがストレージ アレイ内で逆方向に進むことがあります。これらの後方参照は、コピーの明示的な配列を維持することで削除できると思いますトラバーサル中のスタック上の先祖 (少なくともそれらのインデックス情報) の数。getParent() や getNextSibling() などの呼び出しの機能は、ストレージ ベクトル自体を飛び回るのではなく、この配列を使用するように書き直す必要がありますが、それは可能です。次に、mNode のメモリ アクセスは左から右にのみスライドします。これは、おそらくキャッシュ パフォーマンスにとって最適に近いものです (ツリーが十分に浅く、スタック上の祖先が常にキャッシュに存在し、過度のキャッシュ プレッシャーを生じさせないと仮定します)。

EDIT3： 再帰的なセミプレオーダートラバーサルを追加しましたが、反復バージョンに比べて簡単です。また、ノードのインデックス部分のコピーを渡してスタックに保持することも非常に簡単です。これにより、再帰が展開されたときに実際に戻ってストレージ配列の以前の部分に再度アクセスする必要がなくなります。代わりに、スタック上にあるものを確認するだけです。これは、ほぼ確実にキャッシュ内にあります-ツリーが非常に深くて幅が広いわけではないことを前提としています。特定のレベルですべての子のコピーを保存する必要があります。直系の祖先だけを保存するだけでは十分ではなく、兄弟も保存する必要があります。このコードを使用し、ストレージ ベクトルをセミ プレオーダーでレイアウトすると、トラバーサルでのすべてのメモリ アクセスは、バックトラッキングなしでストレージ アレイを左から右にスキャンします。私はあなたを思う' ほぼ最適なキャッシュ パフォーマンスが得られます。どうすればもっと良くなるかわかりません。

サンプル input.txt: 各数値は、暗黙的な現在のノードが事前注文方式で持つ子の数を表します。以下では、sentinel エンド ノードには 1 つの子のみがあり、単一のルート (コードは必要に応じて複数のルートをサポートします)、ルートには 5 つの子があり、ルートの最初の子には 0 の子があり、ルートの 2 番目の子には子供2人など。ツリー構造を視覚的に示すために間隔を使用しましたが、プログラム自体には必要ありません。

1
        5
                0
                2
                        7
                                0
                                0
                                0
                                1
                                        0
                                0
                                0
                                0
                        2
                                1
                                        0
                                0
                1
                        0
                4
                        1
                                0
                        2
                                1
                                        0
                                1
                                        0
                        0
                        0
                0

出力例:

john-schultzs-macbook-pro:~ jschultz$ clear; ./a.out < input.txt

Node -1 is complete! mParentIndex = 0; mIndex = 0; mChildrenBegin = 1; mChildrenEnd = 2
Node 0 is complete! mParentIndex = 0; mIndex = 1; mChildrenBegin = 2; mChildrenEnd = 7
Node 1 is complete! mParentIndex = 1; mIndex = 2; mChildrenBegin = 7; mChildrenEnd = 7
Node 2 is complete! mParentIndex = 1; mIndex = 3; mChildrenBegin = 7; mChildrenEnd = 9
Node 6 is complete! mParentIndex = 3; mIndex = 7; mChildrenBegin = 9; mChildrenEnd = 16
Node 8 is complete! mParentIndex = 7; mIndex = 9; mChildrenBegin = 16; mChildrenEnd = 16
Node 9 is complete! mParentIndex = 7; mIndex = 10; mChildrenBegin = 16; mChildrenEnd = 16
Node 10 is complete! mParentIndex = 7; mIndex = 11; mChildrenBegin = 16; mChildrenEnd = 16
Node 11 is complete! mParentIndex = 7; mIndex = 12; mChildrenBegin = 16; mChildrenEnd = 17
Node 15 is complete! mParentIndex = 12; mIndex = 16; mChildrenBegin = 17; mChildrenEnd = 17
Node 12 is complete! mParentIndex = 7; mIndex = 13; mChildrenBegin = 17; mChildrenEnd = 17
Node 13 is complete! mParentIndex = 7; mIndex = 14; mChildrenBegin = 17; mChildrenEnd = 17
Node 14 is complete! mParentIndex = 7; mIndex = 15; mChildrenBegin = 17; mChildrenEnd = 17
Node 7 is complete! mParentIndex = 3; mIndex = 8; mChildrenBegin = 17; mChildrenEnd = 19
Node 16 is complete! mParentIndex = 8; mIndex = 17; mChildrenBegin = 19; mChildrenEnd = 20
Node 18 is complete! mParentIndex = 17; mIndex = 19; mChildrenBegin = 20; mChildrenEnd = 20
Node 17 is complete! mParentIndex = 8; mIndex = 18; mChildrenBegin = 20; mChildrenEnd = 20
Node 3 is complete! mParentIndex = 1; mIndex = 4; mChildrenBegin = 20; mChildrenEnd = 21
Node 19 is complete! mParentIndex = 4; mIndex = 20; mChildrenBegin = 21; mChildrenEnd = 21
Node 4 is complete! mParentIndex = 1; mIndex = 5; mChildrenBegin = 21; mChildrenEnd = 25
Node 20 is complete! mParentIndex = 5; mIndex = 21; mChildrenBegin = 25; mChildrenEnd = 26
Node 24 is complete! mParentIndex = 21; mIndex = 25; mChildrenBegin = 26; mChildrenEnd = 26
Node 21 is complete! mParentIndex = 5; mIndex = 22; mChildrenBegin = 26; mChildrenEnd = 28
Node 25 is complete! mParentIndex = 22; mIndex = 26; mChildrenBegin = 28; mChildrenEnd = 29
Node 27 is complete! mParentIndex = 26; mIndex = 28; mChildrenBegin = 29; mChildrenEnd = 29
Node 26 is complete! mParentIndex = 22; mIndex = 27; mChildrenBegin = 29; mChildrenEnd = 30
Node 28 is complete! mParentIndex = 27; mIndex = 29; mChildrenBegin = 30; mChildrenEnd = 30
Node 22 is complete! mParentIndex = 5; mIndex = 23; mChildrenBegin = 30; mChildrenEnd = 30
Node 23 is complete! mParentIndex = 5; mIndex = 24; mChildrenBegin = 30; mChildrenEnd = 30
Node 5 is complete! mParentIndex = 1; mIndex = 6; mChildrenBegin = 30; mChildrenEnd = 30
Beginning Semi-Pre-Order traversal of tree!
Visiting 0
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 0
Will visit children of 0
Visiting 1
Will visit sibling of 1
Visiting 2
Will visit sibling of 2
Visiting 3
Will visit sibling of 3
Visiting 4
Will visit sibling of 4
Visiting 5
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 1
No children to visit of 1
Trying to visit children of 2
Will visit children of 2
Visiting 6
Will visit sibling of 6
Visiting 7
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 6
Will visit children of 6
Visiting 8
Will visit sibling of 8
Visiting 9
Will visit sibling of 9
Visiting 10
Will visit sibling of 10
Visiting 11
Will visit sibling of 11
Visiting 12
Will visit sibling of 12
Visiting 13
Will visit sibling of 13
Visiting 14
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 8
No children to visit of 8
Trying to visit children of 9
No children to visit of 9
Trying to visit children of 10
No children to visit of 10
Trying to visit children of 11
Will visit children of 11
Visiting 15
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 15
No children to visit of 15
Reached end of siblings again -> completed traversal of tree rooted by parent 11
Moved back up to 11
Found a great^Nth uncle (12) to check for children to visit!
Trying to visit children of 12
No children to visit of 12
Trying to visit children of 13
No children to visit of 13
Trying to visit children of 14
No children to visit of 14
Reached end of siblings again -> completed traversal of tree rooted by parent 6
Moved back up to 6
Found a great^Nth uncle (7) to check for children to visit!
Trying to visit children of 7
Will visit children of 7
Visiting 16
Will visit sibling of 16
Visiting 17
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 16
Will visit children of 16
Visiting 18
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 18
No children to visit of 18
Reached end of siblings again -> completed traversal of tree rooted by parent 16
Moved back up to 16
Found a great^Nth uncle (17) to check for children to visit!
Trying to visit children of 17
No children to visit of 17
Reached end of siblings again -> completed traversal of tree rooted by parent 7
Moved back up to 7
Moved back up to 2
Found a great^Nth uncle (3) to check for children to visit!
Trying to visit children of 3
Will visit children of 3
Visiting 19
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 19
No children to visit of 19
Reached end of siblings again -> completed traversal of tree rooted by parent 3
Moved back up to 3
Found a great^Nth uncle (4) to check for children to visit!
Trying to visit children of 4
Will visit children of 4
Visiting 20
Will visit sibling of 20
Visiting 21
Will visit sibling of 21
Visiting 22
Will visit sibling of 22
Visiting 23
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 20
Will visit children of 20
Visiting 24
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 24
No children to visit of 24
Reached end of siblings again -> completed traversal of tree rooted by parent 20
Moved back up to 20
Found a great^Nth uncle (21) to check for children to visit!
Trying to visit children of 21
Will visit children of 21
Visiting 25
Will visit sibling of 25
Visiting 26
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 25
Will visit children of 25
Visiting 27
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 27
No children to visit of 27
Reached end of siblings again -> completed traversal of tree rooted by parent 25
Moved back up to 25
Found a great^Nth uncle (26) to check for children to visit!
Trying to visit children of 26
Will visit children of 26
Visiting 28
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 28
No children to visit of 28
Reached end of siblings again -> completed traversal of tree rooted by parent 26
Moved back up to 26
Moved back up to 21
Found a great^Nth uncle (22) to check for children to visit!
Trying to visit children of 22
No children to visit of 22
Trying to visit children of 23
No children to visit of 23
Reached end of siblings again -> completed traversal of tree rooted by parent 4
Moved back up to 4
Found a great^Nth uncle (5) to check for children to visit!
Trying to visit children of 5
No children to visit of 5
Reached end of siblings again -> completed traversal of tree rooted by parent 0
Moved back up to 0
Finished Semi-Pre-Order traversal of tree!
于 2015-02-19T20:30:27.403 に答える
-1

再帰関数を使用せずにノードのツリーを通過する方法を含む、Qt 用の XPath のまだ完全に準拠していないバージョンを実装しました。特定のノードのすべての子孫 (最終的には Self を含む) を通過するアルゴリズムを使用して、関連するセクションの 1 つのコピーがあります。

実装全体(5480 行付近)を見たい場合は、 SourceForge.net GIT リポジトリで入手できます。最新のものはgithubにあります。

    case AXIS_DESCENDANT:
    case AXIS_DESCENDANT_OR_SELF:
        switch(node_type)
        {
        case NODE_TYPE_NODE:
        case NODE_TYPE_ELEMENT:
            {
                // as far as I know the type node is considered to be
                // the same as elements (at least in XPath 1.0)
                QDomNode node(context_node);
                if(axis == AXIS_DESCENDANT_OR_SELF
                && (local_part.isEmpty() || local_part == context_node.toElement().tagName())
                && (any_prefix || prefix == context_node.prefix()))
                {
                    result.push_back(context_node);
                }
                while(!node.isNull())
                {
                    QDomNode next(node.firstChild());
                    if(next.isNull())
                    {
                        next = node;
                        while(!next.isNull()) // this should never happend since we should bump in context_node first
                        {
                            if(next == context_node)
                            {
                                // break 2;
                                goto axis_descendant_done;
                            }
                            QDomNode parent(next.parentNode());
                            next = next.nextSibling();
                            if(!next.isNull())
                            {
                                break;
                            }
                            next = parent;
                        }
                    }
                    // the local_part & prefix must match for us to keep the node
                    node = next;
                    if((local_part.isEmpty() || local_part == node.toElement().tagName())
                    && (any_prefix || prefix == node.prefix()))
                    {
                        // push so nodes stay in document order
                        result.push_back(node);
                    }
                }
axis_descendant_done:;
            }
            break;

        default:
            throw QDomXPathException_NotImplemented(QString("this axis (%1) does not support this node type (%2)").arg(static_cast<int>(axis)).arg(static_cast<int>(node_type)).toStdString());

        }
        break;
于 2015-02-20T22:47:51.563 に答える