-4

パフォーマンスの観点から、Java のセット、配列、およびリンクされたリストの違いを研究しようとしているので、私が取り組んでいる例は
、配列内の 2 つの配列、2 つのセットと 2 つのリンクされたリストの間の共通オブジェクトを確認する必要がある場合です。 for ループを適用して比較し、セットでインターセクトまたはユニオンを使用しますか? しかし、タイミングには大きな違いがあります。何かアイデアはありますか?

4

2 に答える 2

0

交差するセットと交差するリストまたは配列には違いがあります。2つのセットを交差させる場合は、一方のセットを反復処理して、もう一方のセットに対応するメンバーがあるかどうかを確認する必要があります。セットの取得時間はO（1）であるため、交点はO（n）です。リストまたは配列と交差する場合、交差はO（n ^ 2）です。これは、1つのリスト/配列の各メンバーについて、他のリスト/配列全体を反復処理する必要があるためです。

于 2012-12-07T12:31:11.230 に答える
0

タイミングの違いを確認できるように、マイクロベンチマーク用のテストベッドを準備することをお勧めします。少なくとも10回の繰り返しを実行し、測定の外でウォームアップを行うようにしてください。次に、平均と標準偏差を計算します。私が正しく覚えていれば、これを提供する気の利いたグーグルプロジェクトがあります。

最初に明確にする必要があるのは、漸近的な複雑さまたは大きなOです。たとえば、集合を交差させたい場合は、最良の方法が最適です。

 SortedSet<String> set1 = new TreeSet<String>(); // and populate
 SortedSet<String> set2 = new TreeSet<String>(); // and populate
 // intersect of two sorted sets can be done in linear time

上記はO（n）ですが、他のすべての選択肢はO（n ^ 2）であり、複雑さが悪化し、処理が遅くなります。

于 2012-12-07T12:31:52.627 に答える