项目Euler 35:HashSet给出不正确的结果

Question

我为Project Euler编写了一个Java程序#35:Circular Primes:

这个数字197被称为圆形素数,因为数字的所有旋转:197,971和719本身都是素数.

在100:2,3,5,7,11,13,17,31,37,71,73,79和97之下有十三个这样的素数.

一百万以下有多少个圆形素数？

我的代码编译并运行正常,但是,根据我使用的数据结构,它会给出不同的结果.

该算法的工作方式如下:

1. 获得预先计算的素数.这是对MathUtils.getPrimes(1000000)所有素数等于或小于一百万的调用.我将Set它存储在另一个中,因为它是通过返回一个子集来实​​现的,除非我将素数复制到它们自己的数据结构中,否则性能非常糟糕.

2. 虽然素数集不是空的,但是获得下一个素数.

3. 得到那个素数的所有轮换.例如197,971,719.这些旋转本身不需要是素数,因为无论如何我需要验证它们.

4. 如果素数集包含所有旋转,则将旋转计数添加到运行总计.

5. 如果存在,则从素数集中移除所有旋转.

我注意到这个代码有两个奇怪的地方.如果我使用a TreeSet存储素数,性能非常快,并产生正确的结果:

答案:55
时间:76毫秒

如果我切换到一个HashSet表现更差,结果是不正确的.

答案:50
时间:2527ms

我把代码放在顶部以仔细检查代码在代码运行之前是否包含相同的值,并且它们总是这样做.

1. HashSet与TreeSet？相比,为什么使用产品的结果不正确？没有空值或其他奇怪的值,只有正的,不同的Integer实例.这些集合开始包含完全相同的数据.算法是相同的,因为它是完全相同的代码.由于实现与数据大小之间的排序差异,几乎不可能比较算法运行时的状态.如果我减小输入大小,两者产生的结果相同,最高可达100,000.

2. 当它必须执行不适用于所有那些删除和树旋转时,为什么TreeSet执行速度比HashSet它快得多HashSet？查看HashMap后面的代码,HashSet除了本地化到特定bin之外,不会调整内容的大小或改组.此外,素数相当均匀.虽然没有简单的验证方法,但我希望不会出现表中占用少量垃圾箱的许多项目的最坏情况性能问题.

代码如下.您可以Set通过交换顶部的变量名来切换实现.

import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.NavigableSet;
import java.util.TreeSet;

public class Problem_0035 {

  public static void main(String[] args) {
    // Swap these two variable names to compare.
    Collection<Integer> primes = new TreeSet<>(sieve(1000000));
    Collection<Integer> primes2 = new HashSet<>(sieve(1000000));
    if (!primes.containsAll(primes2) || !primes2.containsAll(primes)
        || (primes.size() != primes2.size())) {
      System.out.println("Primes are not the same!");
    }
    final long start = System.currentTimeMillis();
    int result = 0;
    // Keep getting a prime and checking for its rotations. Remove the primes checked.
    while (!primes.isEmpty()) {
      Integer next = primes.iterator().next();
      Collection<Integer> rotations = getRotations(next);
      if (primes.containsAll(rotations)) {
        result += rotations.size();
      }
      primes.removeAll(rotations);
    }
    System.out.println("Answer: " + result);
    // 55
    System.out.println("Time: " + (System.currentTimeMillis() - start) + "ms");
  }

  /** Enumerate all rotations of the given integer. */
  private static Collection<Integer> getRotations(Integer argValue) {
    Collection<Integer> results = new LinkedList<>();
    final int start = argValue.intValue();

    // Count the digits
    int magnitude = 1;
    for (int i = start; i > 9; i /= 10) {
      magnitude *= 10;
    }

    int current = start;
    do {
      results.add(Integer.valueOf(current));
      current = ((current % 10) * magnitude) + (current / 10);
    } while (current != start);

    return results;
  }

  /** Sieve of Eratosthenes. */
  private static Collection<Integer> sieve(int argCeiling) {
    NavigableSet<Integer> primes = new TreeSet<>();
    for (int i = 2; i <= argCeiling; ++i) {
      primes.add(Integer.valueOf(i));
    }
    for (Integer number = primes.first(); number != null; number = primes.higher(number)) {
      int n = number.intValue();
      for (int i = n * 2; i <= argCeiling; i += n) {
        primes.remove(Integer.valueOf(i));
      }
    }
    return primes;
  }

 //
 // Filter the set through this method to remove the problematic primes.
 // See answers for an explanation.
 //

 /**
   * Any prime number with a zero or five anywhere in its number cannot have prime
   * rotations, since no prime can end in five or zero. Filter those primes out.
   */
  private static Collection<Integer> filterImpossiblePrimes(Collection<Integer> in) {
    Collection<Integer> out = new TreeSet<>();
    for (Integer prime : in) {
      if (!willBeRotatedComposite(prime)) {
        out.add(prime);
      }
    }
    return out;
  }

  /** If the prime is guaranteed to be rotated to a composite, return true. */
  private static boolean willBeRotatedComposite(Integer prime) {
    int p = prime.intValue();
    boolean result = false;
    if (p > 10) {
      while (p > 0) {
        // Primes must end in 1, 3, 7, or 9. Filter out all evens and 5s.
        if ((p % 5 == 0) || (p % 2 == 0)) {
          result = true;
          break;
        }
        p /= 10;
      }
    }
    return result;
  }

}

Answer 1

一些摆弄表明，哈希集最昂贵的部分是找到下一个素数来检查Integer next = primes.iterator().next();- 在我的机器上，使用哈希集的版本几乎需要 4 秒，其中与迭代器相关的业务花费了大约 3.9 秒。

HashSet基于HashMap，并且它的迭代器必须遍历所有桶，直到找到一个非空桶；据我从源代码的浏览中可以看出HashMap，它在删除后不会调整自身大小，即一旦将其达到一定容量，如果不插入其中，则必须手动调整大小。这可能会产生这样的效果：一旦您删除了 的相当大一部分元素HashSet，其大部分存储桶都是空的，因此查找第一个非空存储桶变得昂贵。关于为什么从 a 中删除HashSet不会触发调整大小，我的最佳猜测是，它并不是在构建时考虑到节省空间和快速迭代。

树集不会发生这种情况；它仍然很浅（log ₂ 128000 大约是 17，所以这大约是它的最大深度，因为 10^6 以下有 75k 到 80k 个素数），它所需要做的就是逐步走到最左边的元素以找到下一个。

但这并不能解释我的机器的整个问题，因为即使忽略这一点，哈希集也比树集贵大约 30%。我最好的猜测为什么会发生这种情况是散列整数是额外的负载，比在树集中查找整数键更昂贵，但这实际上只是一个猜测，当然不是一个可靠的论据。