5

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

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

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

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

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

ありがとう！

4

4 に答える 4

3

Apache CommonsCollectionsHashBagクラスを使用していると思います。代わりにTreeBagの使用を検討しましたか？同じBagインターフェースを実装しますが、提供するコンパレーターに従ってデータを効率的にソートします。

とは言うものの、ソート順を変更する必要がある場合、通常、コレクションを別のコンパレーターを使用して新しいコレクションにコピーするよりも良い答えはありません。

于 2012-11-02T02:25:08.300 に答える
3

Apache の代わりにGuava を使用した場合(ほぼ類似していますが、スタイルが異なります)、ほとんどの作業を変換せずに行うことができます。 要素とカウントのペアを効果的に表す を返します。これは、要素とカウントのペアを操作する必要性に対処するためのおそらく最良の方法のように思えます。を反復するように、それを反復できます。 MultisetBagMultiset.entrySet()Set<Entry<E>>Entry<E>Map.entrySet()

を使用Multisets.copyHighestCountFirst(Multiset)して、頻度の高い順で並べ替えられたマルチセットを取得TreeMultisetし、要素で直接並べ替えることができます。

（開示：私はGuavaに貢献しています。）

于 2012-11-02T02:28:22.513 に答える
2

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

コレクションの型を変換する必要がある場合があります。必要な場合、「汚い」、「優雅でない」、または「愚か」は実際には関係ありません。

これらのことを前もって考えすぎるのも間違いです。実際の計算上のトレードオフは、把握するのが難しいことがよくあります。たとえば、HashBag を TreeBag に変更した場合、挿入は からO(1)に移動しO(logN)ますが、ソートとコピーのオーバーヘッドを回避できます。「Big Oh」の分析/思考では、明確な答えは得られません。実際、実際のパフォーマンスは、スケーリング係数、N の値、バッグ内のヒットとミスの比率などに依存します。

明白な方法で物事を実装してみて、それが十分に機能するかどうかを確認することをお勧めします...そうでない場合は、データ構造が主なボトルネックであるかどうかを確認するためにプロファイリングします。次に、プロファイリングと入力データセットのその他の測定値に基づいて、ベースラインの実装からパフォーマンスを向上させる最善の方法を見つけます。

于 2012-11-02T03:23:31.053 に答える
0

私自身の質問に答えます！

Multiset上記の Louis Wasserman による Guava ライブラリが提供するさまざまなタイプの をいくつか試してみました。私の特定のテスト ケースでは、1 GB の XML ファイル (書籍と著者のデータベース) を解析し、非常に大きなマルチセットを作成しています (各著者が DB に表示される回数をカウントします)。解析の最後に到達したら、複数x回表示された著者のみを含む新しい Multiset を取得する必要があります。ここで、x はしきい値です。また、最終セットを著者名でソートしたいと考えています。

私が試した2つの異なる方法を次に示します（特に）：

1) a で元のカウントをTreeMultiset収集し、しきい値を満たさないものを削除します 2) a で元のカウントを収集し、しきい値を満たすカウントを持つハッシュ セットから各項目を追加HashMultisetする新しい を作成しますTreeMultiset

2 番目の方法は、変換と余分なメモリ使用量にもかかわらず、大幅に高速 (約 25%) であることが判明しました。明らかに、これの大きな部分は、バイナリ ツリーから削除するのは非常に非効率的であるということです。

したがって、ここでの明確な結論は、この状況では、変換は適切な方法であるということです (変換を許可しないメモリの制約がない限り)。

ルイさん、Guava ライブラリにアクセスしていただき、ありがとうございます。

于 2012-11-05T00:14:53.957 に答える