問題タブ [bag]

Java の宿題の問題について助けが必要です。文字列、、および を含む 2 つのバッグとbag1、文字列A、B、CおよびDをbag2含む2 つのバッグがあります。これら 2 つのバッグを結合するための BagInterface を作成してから、クラス呼び出しを作成する必要があります。EFGHArrayBag<T> implements BagInterface<T>

BagInterface 私は次のようなことを考えていました:

私がこれを持っていると言うように

私は、ポリモーフィック データ型 Bag の定義と、リストを Bag に変換し、2 つの Bag が同じかどうかをチェックするなどのいくつかの単純な関数を含む Haskell プログラムを作成する任務を負っています。

私の問題は、私が Haskell を初めて使用することです。そのため、バッグの使用方法がわかりません。バッグに関するリソースの方向性を教えてもらえますか?

申し訳ありませんが、次のアルゴリズムのアルゴリズムまたは問題の名前がわかりません。私は問題を述べ、次に私が試したことを述べます。おそらく誰かが私を正しい方向に向けることができます.

あなたがアイテムのバッグを持っていると想像してください（注文されていない、重複は許可されています）。実際には、この緩和が役立つ場合に備えて、バッグには 2 ～ 20 個のアイテムが含まれる場合があります。

目標は、バッグ内のすべてのアイテムを任意の順序で含む最小の長さのチェーン (チェーンの概念が異なる場合の順序付けられたリンク リスト) を見つけることです。

チェーンは、開始トークン (バッグに存在しない) とそれに続く任意の数のアイテムと、それに続く終了トークン (これもバッグに存在しない) で構成されます。

チェーンは、n 個のタプル (順序が重要です) をつなぎ合わせることによって形成されます。さらに緩和するために、n の値はすべてのタプルで同じであるとしましょう。実際には、n = 3 で作業しています。要素が重複している場合、チェーンは連結ではなく「ブレンド」される場合があります。たとえば、(a,b,c) と (c,d,e) を考えてみましょう。は (a,b,c,d,e) のように結合できます。同様に、(a,b,c) と (b,c,d) を結合して (a,b,c,d) にすることもできます。一部のタプルでは最初の位置に開始トークンがあり、一部のトークンでは最後の位置に終了トークンがあり、もちろん問題の解決策が得られます。

したがって、問題の正確な解決策は一般的に扱いにくいように思えます。問題の「良い」解決策を得るには、ある種の最適化アルゴリズムが必要です。私が一緒に暮らすことができる「良い」ソリューション。

私が始めたのは貪欲なアプローチです。最初のパスで、バッグ内の要素の数が最も多いタプルを見つけ、恣意的に関係を壊します。これまでに構築したチェーンを保持するデータ構造を作成し、選択したタプルをこのデータ構造に貼り付けます。問題を開始トークン側と終了トークン側の 2 つのサブ問題に分割します。サブ問題 1 のデータ構造の最初のトークンが開始トークンになり、サブ問題 2 の最後のトークンが終了トークンになるまで、できるだけ早く停止条件を見つけようとするように (開始または終了トークンに応じて) チェーンを成長させます。副問題について）できるだけ早くバッグの中身を使い果たしようとします。

この問題をどこかで見た人はいますか? このアルゴリズムを改善する (または正しく動作させる) 方法について何か考えはありますか? これは私が取り組んでいる実際の問題であり、はるかに大きなシステムのスマートな部分であり、おもちゃの問題でも宿題の問題でもありません。

編集

今日はパソコンから離れていてごめんなさい。些細すぎず、複雑すぎて見えない解決策の例を投稿しようと思います。

与えられた:

1. Bag = {A, B, C, D} （例としてセットにしていますが、各アイテムは複数回出現する可能性があります）
2. / = Start Token
3. \ = End Token

4. 3-タプル (トリプル): 命名を簡単にするために、これらに ag というラベルを付けます。この問題では、小文字には実際の機能はありません。

   /li>

解決策: b、d、および f を連結すると、 が得られ(/,C,D,B,A,\)ます。
これは、開始トークンと終了トークンの両方を数える場合、長さ 6 のバッグ内のすべての要素を含む可能な限り短いチェーンです。一般に、可能な最短経路の長さは |BAG| です。+ 2 (実際に存在する場合)。私の問題文がより意味のあるものになることを願っています。

この質問が、StackOverflow に適していると見なされるほど具体的であることを願っています。FAQ を確認しましたが、具体的でプログラミングに関連しているため、これで十分だと思います。

Java で複雑なデータ マイニング アルゴリズム (FP 成長) を実装しています。アルゴリズムの初期段階のいくつかでは、大規模なデータベースをスキャンして、見つかった各項目タイプの現在のカウントを維持する必要があります。Hashbagこれはインターフェイスに完全に適しているようです。Apache Commons で、うまくいくと思われるものを見つけました。

これで、私の HashBag は [itemType, count] エントリ (ペア) でいっぱいになりました。アルゴリズムの後半では、これらのペアに対して多くのリストのような操作を行う必要があります。場合によっては、コレクションを itemType でソートする必要があります。他の場合は、カウントでソートする必要があります。Listこれはインターフェイスに完全に適しているようです。

Hasbag を List に変換する必要があるという結論に達しました。それなのにどこか汚く、空間と時間の無駄のように感じる。これを行うためのよりスマートな方法はありますか?それとも、コレクションを異なる時間に異なる方法で処理する必要があり、変換が必要悪であるというプログラミングの問題が発生するのは一般的な状況ですか?

1 つの選択肢は、真にリストである独自のインターフェイスを作成することですが、「バッグ スタイル」の追加が可能です。何かを追加するたびに、リストをソートしたままにし、カスタム コンパレータを使用してバイナリ検索を実行する必要がありました。そのコレクションの構築は、おそらく Hashbag の構築よりも時間がかかりますが、最後の変換ステップを省略できます。どちらが好ましいかについて何か考えはありますか？

ありがとう！

Javaにはマルチセットがあり、SmallTalkにはBagクラスがあり、それらは同じ関数であると言われています。値のセットを保持しますが、複数の値を許可します（それぞれにカウントがあります）。

しかし、マルチセットは、キーのカウントを保持するハッシュテーブルによって実装できるようです（または他の可能な実装があるかもしれません）。

マルチセットまたはバッグの一部の実装は、上記のハッシュよりも時間計算量が優れていますか？必要な操作は

1. アイテムを挿入
2. アイテムを削除
3. セット内の最小値を取得します
4. セット内の最大値を取得します

特に、上記の4つの操作のそれぞれについて、それがより良くO(n)、おそらくすべてO(log n)またはより良く行われることを望んでいます。O(log n)（上記の3と4は、値が追加または削除されるたびにマルチセットが何らかのソートされた方法で維持される場合にのみ発生すると予想されます。）

エンティティをロードしようとすると、NHibernate.Collection.PersistentBag クラスでエラーが発生します。

値 "MyProject.DomainModel.Operator" は "MyProject.DomainModel.Operator" 型ではないため、この汎用コレクションでは使用できません。

両方の値の型がまったく同じであることに注意してください。比較ツールでそれらを再確認しました。

NHibernate は、行 bag.Add(element) で List コレクションに値を追加できません。

要素変数は、実際には *object{DecoratorAopProxy_9cf850624c7e4ef9a8e2d9694bed26fd}* 型です。このリストに正常に追加できるオブジェクトはobject{MyProject.DomainModel.Operator}型であることに気付きました。このタイプは、「タイプ」列の VS2012 の「クイック ウォッチ」機能から取得されます。

NHibernate がこの特定のオブジェクトの型をプロキシに変更し、他のオブジェクトは純粋なエンティティ型を持っている理由を知っている人はいますか?

そのため、 「 AccountManagerRole accManager から個別の accManager を選択する」などの操作を行うと、ID を使用してオペレーターが一度に 1 つずつロードされ、NHibernate がそのうちの 1 つでクラッシュします。

私はこのプロジェクトで緊急に助けが必要です。プログラミング課題のクラスを実装しようとしていますが、 、、およびのメソッドでBagハングアップしています。addAll()Union()equals()

編集：割り当てによるとaddAll()、2番目の配列のすべてのオブジェクトを最初の配列に追加することになっています。実行時にエラーが発生しなくなりましたが、何らかの理由で 2 番目の配列のすべての要素が追加されず、最初の 2 つしか追加されません。

編集:についてUnion()は、最初の 2 つのバッグのすべての内容を含む 3 番目のバッグを作成することになっています。ArrayIndexOutOfBoundsExceptionこのメソッドを実行すると、エラーが発生しました。biddulph.r に続くコードを更新しましたが、これもうまく機能しています。再度、感謝します！

編集：「最初の試み」そしてequals()、バッグのサイズをチェックしてサイズが等しいことを確認し、次に同じ数字が含まれているかどうかをチェックすることになっています。したがって、現在書かれているように、私のequals()メソッドはサイズを比較してそのブール値を返しますが、実際の値を比較する方法がわかりません。

皆さんが私に与えることができる助けに本当に感謝しています、ありがとう。

編集:ご協力いただきありがとうございます。皆さんは命の恩人です。

バッグ内の個々のアイテムを文字列に折りたたむインターフェイスを作成する必要があります。例: {(a),(b)} を ab に。

まず、代数インターフェイスを使用して文字列を返すことができますか、それとも整数 (Long) に制限されていますか。

次に、代数を使用するいくつかの例にアクセスできる場所はありますか (どこでも見られる COUNT の例は別として)。

Algebraic を使用して文字列を処理できるかどうかだけ答えて、既存の UDF コード (私の問題を正確に解決するコードではない) を確認できる適切な場所があるかどうかを教えてください。

これらは私が試したことです：

1. バッグで機能するUDFコードをグーグルで検索します。どこにでも投稿されているCOUNTの例から離れて何も得られない
2. Pig でさまざまなオプションを試しています。どうやら、残念なことに、バッグ内の個々のアイテムを逆参照することはできません。

Javaの「バッグ」とは何ですか? Google で調べてみましたが、正確な答えが見つかりませんでした。グーグルで見つけたものから、バッグはマルチセットに似ていることがわかりました。グーグルで検索しても適切な答えが得られなかったので、私が正しいか間違っているか知りたいです。

主題を調査すると、著者が「Bag of Words」モデルを使用して画像の分類/検索を行っている論文を見つけることができますが、他の人は「Bag of features」モデルを使用して同様のタスクを行っています。

関連する方法 (ビジュアル ワードの検出と抽出、ビジュアル ディクショナリの構築、機械学習を使用した分類器のトレーニング) についての基本的な理解はありますが、両方のモデルの違いはまだわかりません。それらは同義語ですか？たぶん、違いを示す具体的な例/ドキュメントを見逃した...