問題タブ [tree]

カテゴリのリストを含む xml ドキュメントがあります。

そして製品のリスト：

製品のカテゴリが 12 の場合、「構成/モニター/CRT モニター」に変換する必要があります (カテゴリ 12 を取得すると、親 (13) など)。親が 0 の場合、停止します。

XSL 変換を使用してこれを行うエレガントな方法はありますか?

だから、私は、複数のスレッドが同時に読み取りと書き込みの両方のアクセス権を持つバイナリツリーでローテーションするときにノードをロックするためのこのスキームを思いつきました。これには、ローテーションごとに4つのノードをロックすることが含まれますが、これは非常に多いようです。必要なロックを減らす方法を思いついたので、ある方法を賢く考えましたが、グーグルはあまり現れませんでした（とにかく間違った用語を使用している可能性があります）。

これは私の現在のスキームです。オレンジと赤のノードは回転によって移動または変更されるため、ロックする必要があります。緑のノードは、回転の影響を受けるがそれ自体の影響を受けないノードに隣接しています。

二分木の回転

これを行うにはもっと良い方法が必要だと思いました。影響を受ける4つのノードのスナップショットを取り、スナップショット内でそれらをローテーションしてから、現在のノードをスナップショットのノードに置き換えるというアイデアがあります（ローテーションを行っていました）-これにより、ほぼロックフリーになりますが、ローテーションがかなり迅速な操作（3つのポインターの再割り当て）であることを考えると、メモリのオーバーヘッドが非常に大きくなる可能性がありますか？

これを効率的に行う方法についての指針（しゃれなし）を探していると思います。

私は最近、ネストされたセットモデルのがらくたを使用しています。私は、ほぼすべての有用な操作とビューのクエリを楽しく設計してきました。私が行き詰まっていることの 1 つは、ノードの直接の子 (および子のみであり、それ以上の子孫ではない!) を選択する方法です。

正直なところ、私はその方法を知っていますが、それには手に負えない量の SQL が含まれます。もっと簡単な解決策があると確信しています。

たとえば、犬の繁殖情報、植物の遺伝的交雑、複雑な人間関係などを保持するための標準的なデータ構造が必要です。

簡単なツリー構造だと思うかもしれませんが、子孫ごとに2つ（または遺伝子工学の場合はそれ以上）の親、親セットごとに複数の異なる子孫、親の複数の動き（スタッド馬は他の多くの馬と交配する）、養子縁組などにより、これは非常に断片化された構造になります。

私は誰かが以前にこれに取り組んだことを期待しています。調べる必要のあるリソースはありますか？

私は日々の開発で多くの階層を扱っています。ファイルシステム、AutodeskMayaのネストされたDAGノードなど。

オブジェクトの階層をトラバースして比較するために特別に設計されたPython用の優れたモジュールはありますか？

特に興味深いのは、2つのほぼ同一の階層間で「あいまいな」比較を行う方法です。これを行う理由のいくつかは、アニメーションを一方から他方に転送するために、2つの異なるキャラクターからのMayaの2つのノード階層を一致させるためです。

私が読んでいることに基づいて、2つのノード名が互いにどれだけ近いかを比較するために、名前のしきい値（自分で作成できるもの）を持つものがおそらく必要になるでしょう。次に、子ノードが階層に表示される順序をオプションで無視する方法が必要です。最後に、ノードが階層の上下にわずかに移動した可能性がある場合に備えて、深度のしきい値を処理する必要があります。

学校のプロジェクトの締め切りの数時間前にそれを達成できるかどうかを確認するために、これを決定する必要がありますが、データ構造についてあまり理解していないため、提案が必要です...

私がしなければならないことが 2 つあります。それらはおそらく異なるデータ構造を使用するでしょう。

1. プロファイル レコードを保持するためのデータ構造が必要です。プロファイルは、名前と社会保障番号で検索できる必要があります。SSN は独自のものなので、それを有利に利用できるでしょうか? ここではハッシュマップが最善の策だと思いますか? しかし、ハッシュ マップで SSN を使用して、特定のプロファイルを探す際の利点として使用するにはどうすればよいでしょうか? 基本的で分かりやすい説明は大歓迎です。

2. 都市に関するレコードを保持するためのデータ構造が必要です。訪問者が最も多い都市、訪問者が少ない都市、および特定の都市を訪問するクライアント (クライアントに関するデータのプロファイルは #1 のデータ構造から取得されます)を知る必要があります。

これは私のプロジェクトに必要な 3 番目のデータ構造であり、どこから始めればよいか分からないデータ構造です。使用するデータ構造のタイプに関する提案は、可能であれば、上記のデータを太字で古いものにする方法の例とともに高く評価されます。

注:最初のデータ構造は既に完了しています (以前の質問
で話しました)。2 つ目はここ #1 に投稿されています。他のグループ メンバーが対応していますが、私たちがやろうとしていることが「最善の」アプローチであるかどうかを知る必要があります。3 番目は #2 で、私が最も助けを必要としているものです。

それ自体がツリー構造を持つテーブルがあります。

ルート ノードの下にあるサブツリー全体を取得したいと考えています。ルート ノードが「x」の場合、ノードのセット {1, 5, 6, 7, 10, 11, 12} を取得したいと考えています。どうすればlinqでそれを行うことができますか?

ツリーのノードに同値類を構築するための優れたデータ構造を探しています。理想的な構造では、次の操作は高速（必要に応じてO（1）/ O（n））で簡単（ミステリーコードの段落なし）である必要があります。

• （A）根から木を歩きます。各ノードで->子遷移は子ノードのすべての同等のバージョンを列挙します
• （B）2つの同値類をマージする
• （C）既存のノード（子）およびその他のデータのリストから新しいノードを作成します
• （D）ノードと構造的に同等のノードを見つけて（つまり、同じ数の子を持ち、対応する子は同じ同値類に属し、それらの「他のデータ」は等しい）、新しい（または新しく変更された）ノードを配置できるようにします正しい同値類（マージを介して）

これまで私が検討した（これらのいくつかは組み合わせて使用​​できる）：

• 子がノードではなくノードのコレクションへの参照であるパフェ。（A）高速、（B）マージされたコレクションを指すようにツリーをウォークしてノードを更新する必要がある、（C）新しいノードの各子を含むコレクションを見つける必要がある、（D）ツリーをウォークする必要がある
• ノードの特性によってノードのハッシュを維持します。これにより、（D）ははるかに高速になりますが、（B）は遅くなります（等価クラスがマージされたときにハッシュを更新する必要があるため）
• ノードをまとめて循環リンクリストにまとめます。（A）は高速です、（B）は高速ですが、循環リストの「マージ」部分が実際にリストを分割するという事実のために、（C）は高速であり、（D）はツリーを歩く必要があります
• 上記と同様ですが、各ノードに追加の「上」ポインターがあり、循環リストの正規メンバーを見つけるために使用できます。

私は甘い代替品を逃していますか？