問題タブ [data-structures]

そのため、私は最近 C# をいじっていますが、すべてのジェネリック コレクションには少し混乱しています。ツリーのヘッドがキーと値のペアであるデータ構造を表現したいとします。その下にキーと値のペアのオプションのリストが 1 つあります (ただし、これらよりも多くのレベルはありません)。これは適切でしょうか？

これは、データをやり取りするための単純なシャントにすぎません。

Javaでリンクリストを作成する最良の方法は何ですか?

理想的には、テンプレート化された論理 Set クラスを探しています。ユニオン、インターセクションなどの標準的なセット操作がすべて含まれ、重複したアイテムを折りたたむことができます。

キーを使用するだけで、C# Dictionary<> に基づいて独自のセット クラスを作成することになりました。

過去X分間にいくつのアイテムを照会できるデータ構造が必要です。アイテムは単純な識別子またはより複雑なデータ構造である可能性があり、できればアイテムのタイムスタンプは、外部に保存されるのではなく、アイテム内にあることが望ましいです (ハッシュまたは同様のものとして、複数のアイテムが同じものを持つ問題を抱えたくないでしょう)タイムスタンプ)。

これまでのところ、LINQ を使用すると、特定の時間よりも長いタイムスタンプを持つアイテムを簡単にフィルター処理して、カウントを集計することができたようです。.NET 3.5 固有のものを自分の運用環境に取り込もうとするのはまだためらっていますが。同様のデータ構造に関する他の提案はありますか?

私が興味を持っているもう 1 つの部分は、古いデータのエージングアウトです。6 時間以内のアイテム数のみを要求する場合は、それよりも古いものをデータ構造から削除したいと思います。長時間実行されるプログラムになります。

Haskell のすべての概念を完全に理解しようとしています。

代数データ型は、C# や Java などのジェネリック型とどのように似ていますか? そして、それらはどのように違うのですか？とにかく、それらの何がそんなに代数的なのですか？

私は普遍代数とその環と体に精通していますが、Haskell の型がどのように機能するかについては漠然とした考えしか持っていません。

MySQL データベースでエッジとしてエンコードされたツリーがあります。

ツリーのリーフごとに、items.tot誰かが設定します。内部ノードの場合、そのitems.tot子の合計である必要があります。次のクエリを繰り返し実行すると、目的の結果が生成されます。

（これは実際には機能しないことに注意してくださいが、それは重要ではありません）

データベースが存在し、不変条件が既に満たされていると仮定します。

質問は：

この要件を維持しながら DB を更新する最も実用的な方法は何ですか? 更新により、ノードが移動したり、totリーフ ノードの値が変更されたりする場合があります。葉ノードは葉ノードのままであり、内部ノードは内部ノードのままであり、全体は適切なツリーのままであると想定できます。

私が持っていたいくつかの考え：

• 完全な無効化、更新後、すべてを再計算します (ええと...いいえ)
• アイテム テーブルにトリガーを設定して、更新された行の親を更新します。
  • これは再帰的です（更新は更新をトリガーし、更新をトリガーします...）
  • 動作しません。MySQL はトリガーを開始したテーブルを更新できません
• 更新される任意の行の親の更新をスケジュールするようにトリガーを設定します
  • これは反復的です（スケジュールからアイテムを取得し、それを処理してさらにアイテムをスケジュールします）
  • 何がこれを開始しますか？クライアントコードを信頼して正しく取得しますか?
  • 利点は、更新が正しく順序付けられている場合、計算する必要がある合計が少なくなることです。しかし、その順序はそれ自体が複雑です。

理想的な解決策は、他の「集約不変条件」に一般化されます

FWIW私はこれが「少しやり過ぎ」であることを知っていますが、私は楽しみのためにこれをやっています（楽しい：動詞、それを行うことによって不可能を見つける. :-)

PHP Manualを見ていますが、リストやセットなど、ほとんどの言語にあるデータ構造に関するセクションがありません。私は盲目なだけですか、それとも PHP にはこのようなものが組み込まれていませんか?

これまでのところ、ツリー構造をデータベースに格納するためのモデルとして、隣接リスト、ネストされたセット、およびネストされた間隔に遭遇しました。私はこれらを十分に知っており、木をある木から別の木へと移動させました。

他の人気モデルは？彼らの特徴は何ですか？このトピックに関する優れたリソース (書籍、Web など) は何ですか?

私は db ストレージを探しているだけでなく、ツリー全般に関する知識を広げたいと思っています。たとえば、入れ子になったセット/間隔がリレーショナル データベース ストレージに特に適していることを理解していますが、実際には他のコンテキストでは悪い選択でしょうか?

C で記述された B ツリー ライブラリの無駄のない適切に構築されたオープン ソース実装を探しています。商用アプリケーションで使用できるようにするには、非 GPL ライセンスである必要があります。理想的には、このライブラリはディスク ファイルとして格納/操作される B ツリー インデックスをサポートし、構成可能な (つまり、最小限の) RAM フットプリントを使用して大きなツリーを構築できるようにします。

注: 少し混乱しているように見えたので、バイナリ ツリーと B ツリーは同じものではありません。

In the vein of programming questions: suppose there's a collection of objects that can be compared to each other and sorted. What's the most efficient way to keep track of the smallest element in the collection as objects are added and the current smallest occasionally removed?