大きなNでHashSetのパフォーマンスが悪いのはなぜですか？

Question

問題Nth Ugly Numberを解決しようとしています。私はPriorityQueueに重複eleを追加しないようにHashSetを使用しようとしています。私は、HashSetのadd（）contains（）がPriorityQueue add（）O（log（n））よりも優れたO（1）であると予想しています。しかし、実装がPriorityQueueのソリューションよりも常に悪いことがわかりました。

次に、重複率を見るために競合をカウントします。それは常に10％を少し上回っています。ですから、Nが成長するにつれて、HashSetを使う方が良いでしょう（大きなnに対しては10％* log（n）>> 90％* C）。奇妙なことは、Nが成長するにつれて、HashSetを使用することがさらに悪化することです。 n = 1000,10000,100000から3倍、1,000,000では3倍、10,000,000では4倍とほぼ同じ性能です。私は最初の容量を1.5nと言っています（Fastest Java HashSet<Integer> library）。だから、HashSetは通常2.5〜3nの要素を持っています。私は4nまたは5nを私のHashSetに設定しています。それは助けにはならない。

これはどうして起こるのですか？ 何紛争（例、90％）がないとき、あなたは二回addを呼び出すこと

は

public class Test { 
    int conflict = 0; 

    public static void main(String[] args) { 
    Test test = new Test(); 
    long start = System.currentTimeMillis(); 
    int N = 10000000; 
    test.nthUglyNumber(N); 
    long end = System.currentTimeMillis(); 
    System.out.println("Time:" + (end - start)); 


    start = System.currentTimeMillis(); 
    test.nthUglyNumber2(N); 
    end = System.currentTimeMillis(); 
    System.out.println("Time:" + (end - start)); 
    } 

    public int nthUglyNumber(int n) { 
    if (n <= 0) { 
     return 0; 
    } 
    HashSet<Integer> CLOSED = new HashSet<Integer>(5 * n); 
    PriorityQueue<Integer> OPEN = new PriorityQueue<Integer>(); 
    int cur = 1; 
    OPEN.add(cur); 
    CLOSED.add(cur); 
    while (n > 1) { 
     n--; 
     cur = OPEN.poll(); 
     int cur2 = cur * 2; 
     if (CLOSED.add(cur2)) { 
     OPEN.add(cur2); 
     } 
     // else { 
     // conflict++; 
     // } 
     int cur3 = cur * 3; 
     if (CLOSED.add(cur3)) { 
     OPEN.add(cur3); 
     } 
     // else{ 
     // conflict++; 
     // } 

     int cur5 = cur * 5; 
     if (CLOSED.add(cur5)) { 
     OPEN.add(cur5); 
     } 
     // else{ 
     // conflict++; 
     // } 
    } 
    return OPEN.peek(); 
    } 

    public int nthUglyNumber2(int n) { 
    if (n == 1) 
     return 1; 
    PriorityQueue<Long> q = new PriorityQueue(); 
    q.add(1l); 

    for (long i = 1; i < n; i++) { 
     long tmp = q.poll(); 
     while (!q.isEmpty() && q.peek() == tmp) 
     tmp = q.poll(); 

     q.add(tmp * 2); 
     q.add(tmp * 3); 
     q.add(tmp * 5); 
    } 
    return q.poll().intValue(); 
    } 
} 

Answer 1

あなたの分析ではメモリ管理のオーバーヘッドを考慮していないと思います。 GCが実行されるたびに、HashSetの到達可能なオブジェクトの一部またはすべてをトレースして移動する必要があります。平均的なケースでこれを数値化することは困難ですが、最悪の場合（フルGC）には余分な作業はO(N)です。

二次的なメモリ効果もあります。例えばHashSetのバージョンではワーキングセットが大きくなり、メモリキャッシュのミスが増えます。これはガベージコレクション中に最も顕著になります。

余分な時間が実際に消費されている場所を特定するために、コードの2つのバージョンをプロファイルすることをお勧めします。

---

あなたはキャッシュを行うようにする方法を探している場合は、より良い：

• セットの専門表現のための表情。例えばBitsetまたはサードパーティのライブラリ。
• LinkedHashSetを使用し、キャッシュヒットが可能なウィンドウを通過した時点でエントリを削除することを検討してください。

Answer 2

注：HashSetの一つであり、PriorityQueueに1。 PrioertyQueue-onlyソリューションはaddを1回だけ呼び出します。

したがって、HashSetは、ケースの90％でオーバーヘッドを追加しますが、そのうち10％のスピードを上げます。