コレクションタイプ間で変換するのが悪いフォームと考えられますか？

Question

この質問は、StackOverflowに適していると思われるほど具体的であることを願います。私はFAQをチェックしました。これはプログラミングに特有で関連しているため、これが適格であると思います。

私はJavaで複雑なデータマイニングアルゴリズム（FP-growth）を実装しています。アルゴリズムの初期段階では、大きなデータベースをスキャンし、見つかった各アイテムタイプの実行カウントを保持する必要があります。これは、Hashbagインターフェイスに完全に適しているようです。私はApache Commonsで私のために働くようだ。

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

私は、Hasbagをリストに変換する必要があるという結論が残っています。しかし、それは何とか、空間と時間の無駄のように汚いと感じます。これを行うにはよりスマートな方法がありますか、別の時代にあなたのコレクションを別々に扱わなければならないプログラミング上の問題を抱えるのが一般的な状況ですか、変換は必要な悪ですか？

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

ありがとうございます！

Answer 1

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

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

（情報開示：私はグアバに貢献）

Answer 2

あなたはApache Commons CollectionsのHashBagクラスを使用していると仮定します。代わりにTreeBagの使用を検討しましたか？これは同じBagインタフェースを実装しますが、提供するコンパレータに応じてデータを効率的にソートします。

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

Answer 3

はまだそれは空間と時間の無駄のように、何とか汚い感じています。これを行うにはよりスマートな方法がありますか、別の時代にあなたのコレクションを別々に扱わなければならないプログラミング上の問題を抱えるのが一般的な状況ですか、変換は必要な悪ですか？

時々、コレクションの種類を変換する必要があります。それが必要な場合は、 "汚い"または "控えめな"または "ダム"は本当に関係ありません。

はまた、フロントまでこれらの事を考えて、上に間違いすることができます。実際の計算上のトレードオフはしばしば把握が難しい。たとえば、HashBagをTreeBagに変更した場合、挿入はO(1)からO(logN)になりますが、並べ替えやコピーのオーバーヘッドを避けることができます。 "ビッグオー"分析/思考はあなたに明確な答えを与えるつもりはありません。実際、実際のパフォーマンスは、倍率、Nの値、バッグ内のヒットとミスの割合などに依存します。

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

Answer 4

自分の質問に答える！

私はいくつかのルイ・ワッサーマンによって、上記のグアバlibaryによって提供さMultisetの異なる種類を試してました。私の特定のテストケースでは、1GBのXMLファイル（書籍と著者のデータベース）を解析し、非常に大きなMultisetを作成しています（それぞれの著者がDBに何回出現したかをカウントしています）。解析が終わると、x回以上出現した著者のみが含まれる新しいMultisetを取得する必要があります.xはある閾値です。私は最終的なセットを著者名でソートすることも欲しい。

1）TreeMultisetで、元のカウントを収集し、元のカウントを収集し、しきい値 2）を満たさないいずれかを削除：

は、ここで（特に）私はそれを試してみました、さまざまな方法の2つですHashMultisetで作成し、次に新たにTreeMultisetを作成し、カウントがしきい値を満たすハッシュセットから各項目を追加します。

変換と追加メモリにかかわらず、2番目の方法は大幅に高速です（約25％使用法。明らかに、これの大きな部分は、バイナリツリーから削除することはかなり非効率的です。

だからここに明確な結論は、このような状況では、変換は良い動き（あなたがそれを許可しませんメモリの制約がない限り）であるということです。

GuavaライブラリのLouisにもう一度おねがいします。