为什么 HashSet 在大 N 时性能不好？

Question

我正在尝试解决问题 Nth Ugly Number。我正在尝试使用 HashSet 来避免将重复的元素添加到 PriorityQueue。我期望 HashSet 中的 add() contains() 是 O(1)，这比 PriorityQueue add() O(log(n)) 更好。但是，我发现我的实现总是比只有 PriorityQueue 的解决方案差。

然后，我统计冲突以查看重复率。持续略高于 10%。因此，随着 N 的增长，使用 HashSet 应该更好（对于大 n，10%*log(n)>>90%*C）。奇怪的是随着 N 的增长，使用 HashSet 变得更糟。从 n=1000,10000,100000 时几乎相同的性能到 1,000,000 时的 3 倍和 10,000,000 时的 4 倍。我读过 (Fastest Java HashSet<Integer> library) 说 1.5n 初始容量。所以，HashSet 通常有 2.5~3n 个元素。我正在为我的 HashSet 设置 4n 或 5n。它没有帮助。

有人知道为什么会这样吗？

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

请注意，当没有冲突时（90% 的情况），您调用 add 两次：一次在 HashSet 上，一次在 HashSet 上PriorityQueue;而 PrioertyQueue-only 解决方案只调用 add 一次。

因此，您的 HashSet 在 90% 的情况下增加了开销，而只加速了其中 10% 的情况。

Answer 2

我认为您的分析没有考虑内存管理开销。每次 GC 运行时，它都需要跟踪和移动 HashSet 中的部分或全部可达对象。虽然在一般情况下很难对此进行量化，但在最坏的情况下（完整的 GC），额外的工作是 O(N).

也可能存在二次记忆效应；例如具有 HashSet 的版本将具有更大的工作集，这将导致更多的内存缓存未命中。这在垃圾收集期间最为明显。

我建议您对两个版本的代码进行概要分析，以确定真正消耗额外时间的地方。

如果您正在寻找使缓存性能更好的方法：

寻找集合的专门表示；例如Bitset 或第 3 方库。
考虑使用 LinkedHashSet 并在条目通过可能命中缓存的 window 后删除条目。

为什么 HashSet 在大 N 时性能不好？

Why is HashSet performance bad in large N?

java

algorithm

performance

priority-queue

hashset