問題タブ [tree]

こんにちはスタックオーバーフラワー！

200.000 文字列エントリの単語リストがあり、平均文字列長は約 30 文字です。この単語のリストがキーであり、各キーにはドメイン オブジェクトがあります。キーの一部を知っているだけで、このコレクション内のドメイン オブジェクトを見つけたいと考えています。たとえば、検索文字列「kov」は、キー「stackoverflow」と一致します。

現在、私は通常 100 ミリ秒以内にアイテムを見つける三分探索木 (TST) を使用しています。ただし、これは私の要件には遅すぎます。TST の実装は、いくつかの小さな最適化によって改善される可能性があり、ツリーのバランスを取ることができました。しかし、これらのことは、私が目指している 5 倍から 10 倍の速度向上にはつながらないと考えました。非常に遅い理由は、基本的にツリー内のほとんどのノードにアクセスする必要があるためだと思います。

アルゴリズムの速度を改善する方法についてのアイデアはありますか? 私が見なければならない他のアルゴリズムはありますか？

前もってありがとう、オスカー

データベースにツリー構造を格納するテーブルがあります。関連するフィールドは次のとおりです。

idすべてのリーフノード（つまり、別のレコードではないレコードparentid）を検索したい

私はこれを試しました：

しかし、それは空のセットを返しました。不思議なことに、「NOT」を削除すると、すべての非リーフノードのセットが返されます。

誰かが私がどこで間違っているのか見ることができますか？

更新：回答の皆さんに感謝します、それらはすべて正しく、私のために働いています。クエリが機能しなかった理由（NULLのこと）も説明しているので、ダニエルを受け入れました。

C++ STL が「ツリー」コンテナを提供しないのはなぜですか? 代わりに使用するのに最適なものは何ですか?

パフォーマンス向上のためにツリーを使用するのではなく、オブジェクトの階層をツリーとして保存したい...

これは簡単な修正かもしれませんが、バイナリ サーチ ツリーのすべてのノード (Node クラスの Size プロパティ) を合計しようとしています。以下の私の BST クラスには、これまでのところ次のものがありますが、0 が返されます。

Node クラス内には、指定されたプロパティに Size と Name を格納する Data があります。私は全体のサイズを合計しようとしています。提案やアイデアはありますか？

著者から毎日新しい本を手渡されると想像してみてください。本は進行中の作業です。彼は自分が何を変更または追加したかを教えてくれません。

あなたの仕事は、変更と追加を特定し、これらのみを出版社 (毎日本全体を読む時間がない) に渡すことです。

この問題を解決するために、本は 100 万行の ASCII テキストで構成され、拡大しています (実際には MySQL バックアップ ファイル)。

私の現在のアイデアは、各行 (1k 文字) の安全なハッシュ (たとえば SHA256) を作成し、それを HD に保存することです。ハッシュは 32 バイトしかないため、ファイルは 32MB しかありません。

次に、明日次のファイルを取得すると、1 行ずつ調べて、各行の新しいハッシュを作成し、それを前日のハッシュと比較します。

プロセスが終了すると、翌日のためにハッシュ ファイルが上書きされます。

比較は、文字列比較 ( > < オペランド) の二分探索法を使用します。これにより、平均 4 回の反復で結果が返されます。

私はまだ btree インデックス ソリューションをコーディングしていませんが、これにどのように取り組みますか?

私のSQLテーブルは次のようになります。

私の ActiveRecord モデルの次のクラスにマップします。

次のコードを使用して、ActiveRecord を使用してツリーのルートを取得しています。

これにより、正しいオブジェクト グラフが得られますが、SQL プロファイラー トレースでは、ツリー内のリーフ以外のノードごとに個別のクエリによって子ページが読み込まれていることが示されます。

ActiveRecord にすべてを前もってロードしてから、("SELECT * FROM Page")メモリ内オブジェクトをソートして必要な親子関係を与えるにはどうすればよいですか?

この質問は、Java JTree または Window .Net Tree (Winforms) または Adob​​e Flex Tree に関するものです。

クライアント/サーバー アプリケーション (Flex の場合、実際には Web です) には、階層データを含むツリーがあります (Windows Explorer タイプのインターフェイス内)。現在、ユーザーがサーバーからより多くのデータを要求すると、ツリーを遅延ロードします。これは問題なく、約 750K ノード (.Net Winforms および Adob​​e Flex で経験的にテスト済み) までは機能しますが、その後は遅くなります。しかし、データベースは急速に拡大し (主に、ユーザーが大量のノードを貼り付けることができるため)、2,000 万ノードのデータベースはまったくありそうもないことではありません。

ガベージ コレクターがメモリを解放できるように、ブランチが折りたたまれているときにツリーからデータを解放する必要がありますか? これは問題ありませんが、ユーザーが効率的でなく、ブランチを折りたたまない場合はどうなるでしょうか? しばらく触れられていないブランチを閉じるメモリ管理モジュールを実行する必要がありますか?

メモリ不足にならないようにするには、これはすべて大変な作業のように思えます。

編集:ノードの崩壊時にデータを解放する必要がありますか? もしそうなら、いつ？弱いオブジェクト キャッシュのアイデアは良いですが、UI が壊れるまで引き続き UI をいっぱいにする必要がありますか (それは悪いアイデアではないかもしれません)。

そのため、データ プロバイダーとして xmllistcollection を持つフレックス ツリー コンポーネントがあります。ドラッグ アンド ドロップでツリーの葉と枝を再配置できるようにしたいと考えています。ドロップ領域をドラッグ中のアイテムの現在のレベルに制限したい。お気に入り

これをほとんどすぐに使用できる方法はありますか?

収集したトークンを使用して、どのリーフをどのブランチに配置する必要があるかを判断し、最終的に TreeNode オブジェクトを生成する大きなメソッドを作成することもできましたが、gppg は提供された正規表現を使用してすべてを処理していたため、もっと簡単な方法はありますか？そうでない場合でも、AST を作成する問題にどのようにアプローチするのが最善かについての指針をいただければ幸いです。

ばかげたことを言って申し訳ありませんが、私はコンパイラ ゲームを始めたばかりです。:)

左と右の ID を持つデータベース (または値の配列) からツリー構造を作成できる PHP のライブラリを探しています。値を取得するときの結果については、配列のみを探しているので、任意のタイプのビューを作成できます。追加と削除については、ライブラリがすべて行ってくれるとよいでしょう。ライブラリが別のライブラリ内にある場合でも、おそらくそれを引き出して自分のライブラリに統合するので気にしません。

何か知ってる人いますか？

私はPHPとMySQLを使用しているので、少なくともPHPを使用していると助かります。それが別のデータベースである場合は、おそらく変換できますが、言語固有の機能をあまり使用しない場合は、PHP と同じかもしれません。