1

これは宿題ではありません。

見た目は木のように見えますが、すべてのリーフは一意です（データベースに一意のIDがあります）。それらの上の階層はやや恣意的です。各チェックボックスには、オン、オフ、および部分的な3つの状態があります。葉はチェックすることもチェックしないこともできます。子供の状態は、親の状態を駆動する必要があります。チェックボックスをクリックすると、チェックボックスが「切り替わり」、必要な変更が上下に反映されます。部分的にチェックされている親をクリックすると、完全にチェックされるはずです。各子には、親のリストへのポインターがあります（必要に応じてこれをセットに変更できます）。各親には、アルファベット順にソートされた子のリストがあります。同時に、下の写真からわかるように、この構造は表示用に拡大したり折りたたんだりできるツリーです。

このアルゴリズムは以前に発明されたものだと確信しています。葉の数は2万枚に達しているので、実際のパフォーマンスには気を配っています。しかし、コードが短くて読みやすいという犠牲を払って、パフォーマンスの最後の一滴をアルゴから絞り出そうとはしませんでした。

原則として、（行くところがあれば）歩いて、変更する必要のあるすべての葉を特定する必要があると考えました。その後、私は歩く必要があります。葉のセットから、影響を受ける可能性のある親のセットを把握する必要があります。次に、変更する必要のある親のセットとその値にフィルターをかけます。次に、それらをセットに追加します。次に、それらのノードから立ち上がって繰り返す必要があります。値だけでなく変更する必要のある葉と他のノードのセットを取得したら、それを実行する必要があります...またはそのようなものです。マトリックスベースの表現はコストがかかりすぎます。

私はこのことを一緒にC++使用してハッキングしてMFCいますが、私の質問はほとんど言語に依存しません。ただし、アルゴリズムよりも具体的な実装をお勧めします。Python、Perl、Scalaのようないくつかの言語は、あまりにも現代的なトリックを持っているかもしれません。私は、Java、C＃（マイナスLINQ）などのより一般的なものに固執しようとします。

コード、リンク、リファレンス、質問は大歓迎です。

代替テキスト

4

2 に答える 2

1

The "partial" state is an issue here.

If you are in a "partial" state, and a child pass "unchecked" should you go "unchecked" too or keep your "partial" state ? This requires querying all other children. I would suggest to modify the structure to keep 2 numbers instead of flags (for non-leaves):

  • the number of children (leaves not direct)
  • the number of checked children (leaves not direct)

You need to maintain them correct at each update, of course.

In order to update them correctly, it's a simple walk from the child to its parents. If you make sure that each child only has one reference to its parent (and the same goes for the parent...), then each time a child change its state, update each of its parents (and thus each of them).

于 2010-11-30T14:01:56.197 に答える
0

ああ、これが複雑な理由がわかります。「変更された可能性がある」リストにアイテムを追加するときに、アイテムを漸進的にトポロジ的に並べ替えたいとします。そうすれば、子を処理した後でのみ要素を処理できます。これにより、変更された要素を一度だけ処理することが保証され、DAG があると仮定すると、循環参照のために要素を処理できない状況に遭遇することはありません。

したがって、一般的なアルゴリズムは次のようになります。

  • 変化するすべてのリーフの子をノードのセットに追加して処理します。
  • 処理する子を持たないセット内のすべてのノードに対して:
    • 新しい状態を決定します。
    • その状態が変化した場合、その親を処理するノードのセットに追加します。

難しい部分は、「処理する子を持たないすべてのノード」です。しかし、それはトポロジー的な並べ替えにすぎません。

于 2010-11-29T21:39:50.890 に答える