2

データベースから (Hibernate を使用して) レコードをフェッチし、Vector. 操作のパフォーマンスに問題があったため、 を にVector置き換えてテストを行いましたHashSet。300000 レコードの場合、スピードの向上は計り知れません - 45 分から 2 分!

私の質問は、この大きな違いの原因は何ですか? のすべてのメソッドが同期されているという点だけですか、それとも配列Vectorを内部的に使用しているのに使用していないという点ですか? または、他の何か？VectorHashSet

コードはシングル スレッドで実行されます。

EDIT : コードはVector(およびその他の場合はHashSet) に値を挿入するだけです。

4

7 に答える 7

10

Vector をセットとして使用しようとしていて、レコードを追加する前にレコードの存在をチェックしている場合、ベクトルの塗りつぶしは O(n) と比較して O(n^2) 操作になりHashSetます。各要素をベクトルの最後ではなく最初に挿入すると、O(n^2) 操作にもなります。

使用しているだけなら、そのような違いは見られないと思いcollection.add(item)ます-同期はそれほど遅くありません.

さまざまな数のレコードでテストを試みることができれば、n が増加するにつれて各バージョンがどのように成長するかを確認できます。これにより、何が起こっているのかを簡単に理解できるようになります。

編集: 使用しているだけの場合はVector.add、何か他のことが起こっている可能性があります。たとえば、データベースは、異なるテスト実行間で異なる動作をしていました。ここに小さなテストアプリケーションがあります:

import java.util.*;

public class Test {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Vector<String> vector = new Vector<String>();
    for (int i = 0; i < 300000; i++) {
      vector.add("dummy value");
    }
    long end = System.currentTimeMillis();
    System.out.println("Time taken: " + (end - start) + "ms");
  }
}

出力：

所要時間: 38ms

明らかに、これはあまり正確System.currentTimeMillisではありません - 正確なタイミングを得るための最良の方法ではありません - しかし、45分もかからないことは明らかです. 言い換えれば、本当にを呼び出しているだけなら、別の場所で問題を探す必要がありますVector.add(item)。

ここで、上記のコードを使用するように変更します

vector.add(0, "dummy value"); // Insert item at the beginning

38 ミリ秒ではなく42秒かかります。これは明らかにかなり悪いですが、それでも 45 分にはほど遠いです。また、私のデスクトップがあなたのデスクトップの 60 倍速いとは思えません。

于 2010-07-06T10:03:32.223 に答える
2

それらを最後ではなく中央または最初に挿入する場合、Vectorはそれらをすべて移動する必要があります。すべての挿入。一方、ハッシュマップは実際には気にしないか、何もする必要がありません。

于 2010-07-06T10:07:42.280 に答える
2

ベクターは古くなっているため、使用しないでください。ArrayListまたはLinkedListを使用してプロファイルを作成すると（リストの使用方法によって異なります）、違いがわかります（同期と非同期）。シングルスレッドアプリケーションでVectorを使用しているのはなぜですか？

于 2010-07-06T10:09:07.460 に答える
1

通常の状況では、300,000 レコードを に挿入するのに、同じレコードを に挿入するよりも 43 分長くかかることはまったくあり得ません。VectorHashSet

しかし、私は何が起こっているのかについて可能な説明があると思います。

まず、データベースから出力されるレコードには、重複の割合が非常に高くなければなりません。または、少なくとも、レコード クラスの equals/hashcode メソッドのセマンティクスに従って重複している必要があります。

次に、ヒープをいっぱいにしようとしているに違いないと思います。

したがって、HashSetソリューションが非常に高速である理由は、ほとんどのレコードが操作によって置き換えられているset.addためです。対照的に、Vectorソリューションはすべてのレコードを保持しており、JVM はほとんどの時間を0.05%GC を何度も何度も実行して最後のメモリを絞り込もうとしています。

この理論をテストする 1 つの方法はVector、はるかに大きなヒープでアプリケーションのバージョンを実行することです。

いずれにしても、この種の問題を調査する最善の方法は、プロファイラーを使用してアプリケーションを実行し、すべての CPU 時間がどこにかかっているかを確認することです。

于 2010-07-06T10:26:26.577 に答える
1 
import java.util.*;

public class Test {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Vector<String> vector = new Vector<String>();
    for (int i = 0; i < 300000; i++) {
       if(vector.contains(i)) {
         vector.add("dummy value");
       }
     }
    long end = System.currentTimeMillis();
    System.out.println("Time taken: " + (end - start) + "ms");
  }
}

ベクトルに要素を挿入する前に重複要素をチェックすると、ベクトルのサイズに応じて時間がかかります。最善の方法は、高性能のために HashSet を使用することです。Hashset は重複を許可せず、挿入前に重複要素をチェックする必要がないためです。

于 2013-03-14T09:48:42.073 に答える
1

ベクトルはデフォルトで同期されます。HashSet は違います。それは私の推測です。アクセス用のモニターの取得には時間がかかります。

テストに読み取りがあるかどうかはわかりませんが、get()Vector エントリへのアクセスに使用される場合、Vector と HashSet は両方とも O(1) です。

于 2010-07-06T10:01:51.267 に答える
-1

ハインツ・カブッツ博士によると、彼は彼のニュースレターの1つでこれを述べました。

古いVectorクラスは、単純な方法でシリアル化を実装します。デフォルトのシリアル化を実行するだけで、Object[]そのままストリーム全体に書き込まれます。したがって、一連の要素をリストに挿入してからクリアすると、VectorとArrayListの違いは非常に大きくなります。

import java.util.*;
import java.io.*;

public class VectorWritingSize {
  public static void main(String[] args) throws IOException {
    test(new LinkedList<String>());
    test(new ArrayList<String>());
    test(new Vector<String>());
  }

  public static void test(List<String> list) throws IOException {
    insertJunk(list);
    for (int i = 0; i < 10; i++) {
      list.add("hello world");
    }
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    ObjectOutputStream out = new ObjectOutputStream(baos);
    out.writeObject(list);
    out.close();
    System.out.println(list.getClass().getSimpleName() +
        " used " + baos.toByteArray().length + " bytes");
  }

  private static void insertJunk(List<String> list) {
    for(int i = 0; i<1000 * 1000; i++) {
      list.add("junk");
    }
    list.clear();
  }
}

このコードを実行すると、次の出力が得られます。

LinkedList used 107 bytes
ArrayList used 117 bytes
Vector used 1310926 bytes

ベクターは、シリアル化されるときに驚異的な量のバイトを使用できます。ここでのレッスンは？シリアル化可能なオブジェクトのリストとしてVectorを使用しないでください。災害の可能性は大きすぎます。

于 2010-07-06T11:04:21.480 に答える