java - 欧拉计划 35 : HashSet gives incorrect results

Question

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

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

我的代码可以正常编译和运行，但是，根据我使用的数据结构，它会给出不同的结果。

算法是这样工作的:

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

2. 当素数集不为空时，获取下一个素数。

3. 获取该素数的所有旋转。例如。 197、971、719。这些旋转本身不需要是质数，因为无论如何我都需要验证它们。

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

5. 从素数集中移除所有旋转(如果存在)。

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

Answer: 55
Time: 76ms

如果我切换到 HashSet，性能会更差并且结果不正确。

Answer: 50
Time: 2527ms

我将代码放在顶部以在代码运行之前仔细检查这两个集合是否包含相同的值，它们总是如此。

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

2. 为什么 TreeSet 的执行速度比 HashSet 快得多，因为它必须执行所有那些不适用于哈希集？查看支持 HashSet 的 HashMap 代码，除了本地化到特定 bin 之外，没有对内容进行大小调整或混洗。此外，素数分布相当均匀。虽然没有简单的验证方法，但我希望不会出现许多项目占用表中少量 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

您的代码中有 2 个错误:

1) 顺序很重要。示例:2 是通过旋转测试的质数。 20 不是。 20 的旋转是 2。因此，如果它首先随机迭代超过 20，则您的代码将删除 2 并且不计算它。这是对 getRotations 函数的更改，它会导致 Tree/Hash Set 具有相同的结果:

int current = start;
do {
   int currMagnitude = 1;
   for (int i = current; i > 9; i /= 10) {
      currMagnitude *= 10;
   }
   if (currMagnitude == magnitude)
       results.add(current);
   current = ((current % 10) * magnitude) + (current / 10);
} while (current != start);

2) 您在迭代集合时从集合中删除元素。你不应该在 Java 中这样做。我怀疑如果您像这样修改代码，TreeSet 和 HashSet 的速度将大致相同:

Collection<Integer> primesCopy = new HashSet<>(primes);
for(Integer i in primesCopy) {
     if(!primes.contains(i)) continue;
     // rest of code as it was