問題タブ [tree-traversal]

n再帰を使用せずに-aryツリーをトラバースするにはどうすればよいですか？

再帰的な方法：

C# で再帰的なディレクトリ トラバーサル メソッドを作成しました (asp.net ページからホストされています)。コードは意図したとおりに機能します (ターゲット マシン上の共有のリストを列挙し、共有を再帰的に処理して、各ファイル/ディレクトリを TreeView に追加します)。残念ながら、これは大量のメモリを消費し、実行に非常に長い時間がかかります。aspx ページを開くと、Webdev.Webserver の RAM 使用量が 800 メガバイトに急増し、ページを表示する Chrome インスタンスはなんと 1.5 GB の RAM を消費します! (ローカル ワークステーションでホストされている SMB 共有に対してテスト コードを実行しています) Chrome がハングしないと、ページのソースを表示することさえできません。

//break; のコメントを外します。ステートメントを実行すると、最初のディレクトリ共有のみが処理されるため、メモリの消費量がはるかに少なくなります。FileSelectList は Asp:TreeView です。

これにより、大量の TreeNode オブジェクトが作成されるため、極端なリソース使用が発生するようです。おそらくメモリ使用量を最小限に抑えるために独自のノード タイプを作成する必要がありますか、それともこれを使用可能にする別の手法はありますか?

オープンソース プロジェクトAfterthoughtをリファクタリングして、より直感的に使用できるようにすることを検討しています。基本的な考え方は、Afterthought で修正を作成する開発者は、特定の .NET 型を修正し、型自体と、プロパティ、メソッド、イベント、コンストラクターなどのリスト (ツリー) を変更する機会が与えられるというものです。私が内部で使用している API Microsoft CCI Metadataは、API でビジター パターンを広範に使用しているため、以下のように、Afterthought で同様のアプローチを採用しました。

しかし、ビジター パターンは実際には、対象の問題 (クラス ライブラリのインストルメント化など) を解決するコードを、ツリーの側面に焦点を当てた一連の異なるメソッドに再配布することになることを発見しました。これは、API を作成する開発者にとっては簡単に実装できますが、消費者はやや不自然な方法でコードを展開する必要があります。ツリーをリストとして公開し、LINQ スタイルのアプローチを活用することよりも、vistor-pattern にはどのような利点があるのでしょうか。

私が検討している代替構文は次のとおりです。

したがって、この場合、Amendment の作成者は、メソッドをオーバーライドする代わりに、fluent/LINQ API を公開するリストを操作することで、すべてのコードを 1 か所 (または選択した場所) に書き込むことができます。明らかに、このアプローチはパフォーマンスがわずかに低下します (反復が増えるなど) が、これ以外にマイナス面はありますか?

私は木の横断に苦労しているので、疫病のようにそれを避けてください...通常。

私は次のような種類のクラスを持っています（ここでは少し簡略化されたバージョンですが、機能的には同じです）。

たくさんのBranchインスタンスの辞書があり、それぞれのタイトルがキーになっています。

今では、トラバーサルを効率的にするための複雑なアルゴリズム（MPTTなど）があることを知っています。特に、効率が最も重要なデータベース駆動型プロジェクトで使用する場合はそうです。私はデータベースをまったく使用しておらず、単純なメモリ内オブジェクトのみを使用しています。

のを考えると、titleそのブランチのすべての子孫（子、子の子など）をBranchから取得する必要があります。listtree

1. 私の場合、効率を上げるためにMPTTのような複雑な（私のアルゴリズムのない脳:)アルゴリズムを使用することをお勧めしますか、それとも単一の関数でこれを実現する簡単な方法がありますか？
2. もしそうなら、私がデータベースを使用していないことを知っているので、どれをお勧めしますか？
3. 例を挙げていただけますか、それとも私が思っているよりもはるかに大きいですか？

注：これは宿題ではありません。私は学校にいません。私は本当にアルゴリズムが苦手です。DBに保存されたツリーを必要とするプロジェクトにDjangoMPTTを使用しましたが、それでもよく理解できていません。

利用可能な製品オプションをフィルタリングするために使用する必要のある製品情報を含む一連のオブジェクトがあります。（つまり、顧客が値オプションID 25のラジオボタンを選択した場合、ID 25で利用可能なものに基づいて、他の2つのオプションをフィルタリングし、構成（25/1/13）からその3つの部分の組み合わせの値を取得して、その組み合わせを見つける必要があります。兄弟でsku値を返します（25/1/13 = 1761）。

キーと値の取得には成功しましたが、一致していません。私はjavascriptを使用した合計n00bです（私の経験のほとんどはjQueryを使用してアニメーション化するだけです）ので、これまでに価値のあるものを書いたかどうかはわかりません。

エンコードされたJSONから得られるものは次のとおりです（トリミングされたb / cデータは大量であるため、フォーマットが正確でない可能性があります）。JSONのフォーマットと構造を制御することはできません。

これは、製品フォームの一般的な構造です。

何か案は？ありがとう！！

編集

両方の完全なオブジェクトは次のとおりです。

次のコードを取得しました。

基本的に、「tr.issueDrawer」をアニメーション化する必要がある「a.issueDrawer」でアクションを実行しています。「a.issueDrawer」から私は現在 $(this).parent().parent().next() を実行していますが、最初の「tr.issueDrawer」をたどって見つけるためのよりクリーンな方法が必要です。

考え？

与えられたバランスの取れた二分木に対して、以下のようにノードペアを (ツリーをトラバースしながら) 出力するインプレース O(N) アルゴリズムを探します。

出力: bc、de、ef、fg

ここで、'a' はルート ノード、'b' は左の子、'c' は右の子などです。出力のペア 'ef' に注意してください。

以下のコメントに基づく追加情報:

1. 「ノード ペア」は、各レベルの各隣接ペアです。
2. 各ノードは、「左」と「右」に加えて「親」ポインタ/参照を持つことができます
3. O(N) とインプレースを緩和する場合、もっと単純な解決策 (再帰的および反復的) はありますか?

ページの HTML リスト ( <ul>、<li>など) があり、複数のアイテムがさまざまな深さにあります。このリストを一度に 1 要素ずつトラバースするコードを作成しようとしています。そのため、「次へ」ボタンは次の<li>要素の ID を返します。これは、現在の要素の直接の兄弟であるか、子<ul>要素にあるか、親<ul>要素にある可能性があります。同様に、「前へ」ボタンも同じことを行いますが、逆になります。

html の例を次に示します。

私は数時間jqueryをいじりましたが、これは私が得た限りです:

上記は、次のノード、または存在する場合は子ノードを返し、兄弟または子がもう存在しないが、1 レベルの深さしかない場合は親ノードを返します。HTML リストは無制限の深さにすることができるので、何らかの再帰が必要になるのでしょうか? これは、私のスキルが私を連れて行くことができる限りです。このリストを同じ方法で逆の順序で作業するために、「前の」リンクについても考え始めていません。

私はdevshedで同じことを尋ねました（数週間前）が、返事がありません.

回答ありがとうございます。

忍者、私はあなたのものを実装して成功しました。ネストされたリストを非常にうまく上下に移動できるようになりました。

さらに質問です。よろしければ、ツリー内のある点で「位置」を開始する機能が必要です。ユーザーは、ハッシュ (#post9 など) を使用してツリー内のノードを選択できます。リスト内の任意のノードをクリックして選択するか、そのノード独自のハッシュを含む URL をブックマークすることができます。

私のさらなる質問は、URL のハッシュを使用して、ツリー内のノードを見つけてその位置を取得するにはどうすればよいでしょうか? URL のハッシュは、li ノードの ID と相関しています。

木をすばやく横断する必要があり、並行して実行したいと思います。スレッドの束を手動でスピンアップするよりも、並列拡張機能を使用したいと思います。

私の現在のコードは次のようになります。

Parallel.ForEachにParallel.Whileアナログがあることを本当に望んでいました。Parallel.ForEachを使用したParallelの実装に関するStephenToubの記事に出くわしました。正しく読み取った場合、反復しようとしているキューを変更しているため、これはまだ機能しません。

タスクファクトリと再帰を使用する必要がありますか（そしてそれは危険ですか？）？または私が見落としているいくつかの簡単な解決策はありますか？

編集：@svick

ツリーには250,000を超えるノードがあります。現在の最大深度は、ルートを含めて14ノードです。

ルートから約500のノードがあり、その後のバランスはかなりランダムに分布しています。私はすぐに分布に関するいくつかのより良い統計を得るでしょう。

@Enigmativity：

はい、ツリーは多くのユーザーによって同時に変更されていますが、通常、ツリーまたはサブツリーの共有読み取りロックを使用するか、ダーティ読み取りを許可します。

node.Childrenへの呼び出しはアトミックと見なすことができます。

DoSomethingは、実際にはいくつかのデリゲートの1つです。一部の高価な操作では、ノードのスナップショットリストを収集し、トラバーサルの外部で処理します。

おそらく一般的なケース（ツリー全体ではなくサブツリーがトラバースされている）を確認する必要があることに気付きました。そのために、ツリーのすべてのノードでトラバースを実行し、合計時間を確認しました。

各トラバーサルアルゴリズムにParallel.ForEach（nodes、Traverse）を使用しました。ここで、ノードには約25万個のノードがすべて含まれていました。これは、多くの異なるノードを同時に要求する多くのユーザーをシミュレートした（一種の）ものです。

00256ms幅優先シーケンシャル

00323ms幅優先探索（作業あり）（静的カウンターを「作業」としてインクリメントしました）

01495msカークス最初の答え

01143msSvicks2番目の回答

00000ms再帰シングルスレッドは60秒後に終了しませんでした

00000ms謎の答えは60秒後に終了しませんでした

@エニグマ、私はあなたのブログをどうにかして台無しにした可能性があると思います。

結果は控えめに言っても私を驚かせた。コンパイラーがトラバーサルを魔法のように最適化していないことを確信するために、幅優先探索にいくつかの作業を追加する必要がありました。

頭を1回トラバースする場合、最初のレベルを並列化すると最高のパフォーマンスしか得られませんでした。しかし、ほんのわずかに、この数は、第2レベルにノードを追加したときに改善されました（500ではなく2000）。

私は本、Structure and Interpretation of Computer Programs を読んでいました。そこでは、再帰手順と再帰プロセスの違い、および同様に反復手順と反復プロセスの違いについて説明しています。そのため、再帰的な手順でも反復プロセスが生成される可能性があります。

私の質問は次のとおりです。再帰プロセスを生成するプロシージャが与えられた場合、同じ結果を達成するが反復プロセスを生成する別のプロシージャをいつでも作成できますか?

私が解決しようとしていた具体的な問題は、二分探索木の順序通りのトラバーサルを行うが、反復プロセスを生成する手順を作成することでした。スタックを使用して、この問題の反復手順を取得する方法を知っています。ただし、それでも再帰プロセスが生成されます (ここで間違っている場合は修正してください)。

ありがとう、
アビナフ。