Java 8：流和埃拉托色尼筛法

Question

Java 8：流和埃拉托色尼筛法

javahaskelljava-streamprimessieve-of-eratosthenes

8

使用Haskell可以非常简洁地实现欧拉筛法，利用惰性生成无限列表，然后从其尾部移除列表头的所有倍数：

primes :: [Int]
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x > 0]

我正在学习如何在Java 8中使用流，但我想知道是否有一种方法来实现与上面的Haskell代码相同的结果。如果我把Haskell的lazy列表视为等效于Java的流，则似乎需要提取一个以2开头的流，并生成一个新流，其中排除了所有2的倍数，然后采用该流并生成一个新流，其中排除了所有3的倍数，以此类推......

我不知道如何继续下去。

是否有任何方法可以做到这一点，或者当我尝试将Java流视为可与Haskell列表相比较时，我是在欺骗自己？

- user1636349

2

“当我试图将Java流想象成可与Haskell列表相媲美的东西时，我是在自欺欺人吗？” - 我会说是的。也许你可以做类似的事情，但在Java中肯定会更加复杂。 - luk2302

曾经使用过C#（LINQ）和Haskell，我可以说让Java的流做类似的事情并不是一件简单的事情。我建议更接近惯用的Java。在我看来，Java缺乏内置工具来清晰、简洁地表达这些复杂的思想。 - ThreeFx

11

顺便说一下，这不是埃拉托色尼筛法。 - Benjamin Hodgson

1

@Holger 因为惰性列表就是流吗？ - Will Ness

@user1636349 那你要找的是“java-stream”标签。这样你的问题就能吸引更多熟悉Java 8 Stream的人的注意。 - Dušan

显示剩余6条评论

5个回答

3

编辑：筛法不进行优化，返回无穷多个质数的流

public static Stream<Integer> primeStreamEra() {
    final HashMap<Integer, Integer> seedsFactors =
        new HashMap<Integer, Integer>();
    return IntStream.iterate(1, i -> i + 1)
                    .filter(i -> {
                        final int currentNum = i;
                        seedsFactors.entrySet().parallelStream()
                            .forEach(e -> {
                                // Update all factors until they have
                                //the closest value that is >= currentNum
                                while(e.getValue() < currentNum)
                                    e.setValue(e.getValue() + e.getKey());
                            });
                        if(!seedsFactors.containsValue(i)) {
                            if(i != 1)
                                seedsFactors.put(i, i);
                            return true;
                        }
                        return false;
                    }).boxed();
}

测试：

public static void main(String[] args) {
    primeStreamEra().forEach(i -> System.out.println(i));
}

初始帖子：

一种更简单的解决方案，避免了一些不必要的操作（如测试偶数）。

我们迭代从3到限制的所有奇数。

在过滤函数中：

我们检测所有已发现的小于等于当前数字平方根向下取整的质数。
如果它们能够整除我们的当前数字，则返回false。
否则将其添加到发现的质数列表中并返回true。

函数：

public static IntStream primeStream(final int limit) {
    final ArrayList<Integer> primes = new ArrayList<Integer>();
    IntStream primesThreeToLimit =  
           IntStream.iterate(3, i -> i + 2)
                    .takeWhile(i -> i <= limit)
                    .filter(i -> {
                        final int testUntil = (int) Math.sqrt((double) limit);
                        for(Integer p: primes) {
                            if(i % p == 0) return false;
                            if(p > testUntil) break;
                        }
                        primes.add(i);
                        return true;
                    });
    return IntStream.concat(IntStream.of(1,2), primesThreeToLimit);
}

测试：

public static void main(String[] args) {
    System.out.println(Arrays.toString(primeStream(50).toArray()));
}

输出：[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]。

编辑提示：要从IntStream转换为Stream<Integer>，只需执行primeStream(50).boxed()。

- Nobby Nobbs

我意识到这是比 OP 更优化的试除法，但它仍然是试除法而不是筛法。 - DanaJ

1

@DanaJ 没错。我在我的答案中添加了一个实际筛法的流实现。 - Nobby Nobbs

3

如果您愿意接受Scala的解决方案，这里提供一份：

def sieve(nums:Stream[Int]):Stream[Int] = nums.head #:: sieve(nums.filter{_ % nums.head > 0})
val primes:Stream[Int] = sieve(Stream.from(2))

虽然不如Haskell解决方案优雅，但在我看来它非常接近。以下是输出：

scala> primes take 10 foreach println
2
3
5
7
11
13
17
19
23
29

Scala的Stream是一个懒加载列表，比Java 8 Stream更加懒惰。在文档中，你甚至可以找到示例斐波那契数列实现，该实现对应于规范的Haskell zipWith实现。

- Dušan

谢谢。我想要一个Java解决方案，而且我只玩过Scala，但我会考虑一下... :) - user1636349

1

一个替代方案是，您可以实现Collector接口。

  public static void main(String[] args)
  {
    Collector<Integer, List<Integer>, List<Integer>> sieve = new Collector<Integer, List<Integer>, List<Integer>>()
    {
      @Override
      public Supplier<List<Integer>> supplier()
      {
        return ArrayList::new;
      }

      @Override
      public BiConsumer<List<Integer>, Integer> accumulator()
      {
        return (prevPrimes, candidate) ->
        {
          if (prevPrimes.stream().noneMatch(p -> candidate % p == 0))
          {
            prevPrimes.add(candidate);
          }
        };
      }

      @Override
      public BinaryOperator<List<Integer>> combiner()
      {
        return (list1, list2) ->
        {
          list1.addAll(list2);
          return list1;
        };
      }

      @Override
      public Function<List<Integer>, List<Integer>> finisher()
      {
        return Function.identity();
      }

      @Override
      public Set<Characteristics> characteristics()
      {
        Set<Characteristics> set = new HashSet<>();
        set.add(Characteristics.IDENTITY_FINISH);
        return set;
      }
    };

    List<Integer> primesBelow1000 = IntStream.range(2, 1000)
        .boxed()
        .collect(sieve);

    primesBelow1000.forEach(System.out::println);
  }

更简洁地说：

  public static void main(String[] args)
  {

    List<Integer> primesBelow1000 = IntStream.range(2, 1000)
        .boxed()
        .collect(
            ArrayList::new,
            (primes, candidate) ->
            {
              if (primes.stream().noneMatch(p -> candidate % p == 0))
              {
                primes.add(candidate);
              }
            },
            List::addAll
        );

    primesBelow1000.forEach(System.out::println);
  }

更高效（使用Java 9的TakeWhile将O(n)改为O(sqrt(n))）：

List<Long> primesBelowLimit = LongStream.range(2, below)
        .collect(
                ArrayList::new,
                (primes, candidate) ->
                {
                    long candidateRoot = (long) Math.sqrt(candidate);
                    if (primes.stream()
                        .takeWhile(p -> p <= candidateRoot)
                        .noneMatch(p -> candidate % p == 0))
                    {
                        primes.add(candidate);
                    }
                },
                List::addAll
        );

- wilmol

对于Java 9的takewhile，我们是否可以只使用filter来获得与Java 8相同的效率？顺便说一句，回答很棒。 - user8838577

0

可能这样的解决方案可以吗？

public class ErythropheneSieveFunctionBitSet implements IntFunction<BitSet> {

    @Override
    public BitSet apply(int value) {
        BitSet set = new BitSet();
        fillSet(set, value);

        int s = set.stream().min().getAsInt();
        while (s * s <= value) {
            int temp = s;
            int i = 0;
            int multipleTemp;
            while ((multipleTemp = s * (s + i)) <= value) {
                set.clear(multipleTemp);
                i++;
            }
            s = set.stream().filter(x -> x > temp).min().getAsInt();
        }

        return set;
    }

    private void fillSet(BitSet set, int value) {
        for (int i = 2; i < value; i++) {
            set.set(i);
        }
    }
}

- Владимир Куров

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alec · Accepted Answer

当然，这是可能的，但由于Java流没有简单的方法来将其分解为头和尾（您可以轻松获取其中任何一个，但不能同时获取两者，因为流已经被消耗 - 像某人可以使用线性类型一样...）。

解决方案是保留一个可变变量。例如，可变变量可以是测试数字是否是迄今为止看到的任何其他数字的倍数的谓词。

import java.util.stream.*;
import java.util.function.IntPredicate;

public class Primes {

   static IntPredicate isPrime = x -> true;
   static IntStream primes = IntStream
                               .iterate(2, i -> i + 1)
                               .filter(i -> isPrime.test(i))
                               .peek(i -> isPrime = isPrime.and(v -> v % i != 0));

   public static void main(String[] args) {
      // Print out the first 10 primes.
      primes.limit(10)
            .forEach(p -> System.out.println(p));

   }
}

然后，您会获得预期的结果：

$ javac Primes.java
$ java Primes
2
3
5
7
11
13
17
19
23
29