如何修改Akka Streams Prime筛子以排除已知质数的模检验？ [英] How can I modify my Akka streams Prime sieve to exclude modulo checks for known primes?

问题描述

我使用 akka 流编写了一个筛子，以查找 Int 任意来源的主要成员：

I wrote a sieve using akka streams to find prime members of an arbitrary source of Int:

object Sieve extends App {

  implicit val system = ActorSystem()
  implicit val mat = ActorMaterializer(ActorMaterializerSettings(system))
  implicit val ctx = implicitly[ExecutionContext](system.dispatcher)

  val NaturalNumbers = Source.fromIterator(() => Iterator.from(2))

  val IsPrimeByEurithmethes: Flow[Int, Int, _] = Flow[Int].filter {
    case n: Int =>
      (2 to Math.floor(Math.sqrt(n)).toInt).par.forall(n % _ != 0)
  }

  NaturalNumbers.via(IsPrimeByEurithmethes).throttle(100000, 1 second, 100000, ThrottleMode.Shaping).to(Sink.foreach(println)).run()
}

好的，所以这似乎工作得很好。但是，至少存在一些潜在的关注领域：

Ok, so this appears to work decently well. However, there are at least a few potential areas of concern:

1. 模检查使用 par.forall运行。 ，即它们完全隐藏在过滤器 s的 Flow 中，但是我可以看到将 Map 从候选n 到另一个 Map 有什么用？每个 n％中的code>。也许。


2. 我不必要地检查了太多候选人-都在检查我已经知道不是的 n 方面根据先前的结果，并检查 n％_ 是否多余。实际上，即使我认为 n 是素数，也只需要检查到那时的已知素数即可。

1. The modulo checks are run using par.forall, ie they are totally hidden within the Flow that filters, but I can see how it would be useful to have a Map from the candidate n to another Map of each n % _. Maybe.
2. I am checking way too many of the candidates needlessly - both in terms of checking n that I will already know are NOT prime based on previous results, and by checking n % _ that are redundant. In fact, even if I think the n is prime, it suffices to check only the known primes up until that point.

第二点是我最直接的担忧。

The second point is my more immediate concern.

我认为我可以很容易地证明有一种更有效的方法-通过过滤给定每个新素数的来源。

I think I can prove rather easily that there is a more efficient way - by filtering out the source given each NEW prime.

然后....

2, 3, 4, 5, 6, 7, 8, 9, 10, 11... => (after finding p=2)

2, 3,    5,    7,    9,   , 11... => (after finding p=3)

2, 3,    5,    7,         , 11... => ...

现在找到 p 之后然后过滤源，我们需要知道下一个候选对象是否是 p 。好吧，我们可以肯定地说，如果最大已知质数大于其根，那将是质数，我相信这将始终发生，因此只需选择下一个元素就足够了。

Now after finding a p and filtering the source, we need to know whether the next candidate is a p. Well, we can say for sure it is prime if the largest known prime is greater than its root, which will Always happen I believe, so it suffices to just pick the next element...

2, 3, 4, 5, 6, 7, 8, 9, 10, 11... => (after finding p=2) PICK n(2) = 3

2, 3,    5,    7,    9,   , 11... => (after finding p=3) PICK n(3) = 5

2, 3,    5,    7,         , 11... => (after finding p=5) PICK n(5) = 7

在我看来，这就像是重写

This seems to me like a rewriting of the originally-provided sieve to do far fewer checks at the cost of introducing a strict sequential dependency.

另一个想法-我可以通过用术语解决问题来消除约束符号，例如需要素数的最小模检验集等等。

Another idea - I could remove the constraint by working things out in terms of symbols, like the minimum set of modulo checks that necessitate primality, etc.

我吠叫错误的树吗？如果不是，我该如何用这种方式弄乱我的源代码？

Am I barking up the wrong tree? IF not, how can I go about messing with my source in this manner?

推荐答案

我最近才开始摆弄akka流因此可能有比这更好的解决方案（尤其是因为代码对我来说很笨拙）-但是您的第二点似乎对我来说是正确的挑战，我想在akka流中构建反馈循环。

I just started fiddling around with akka streams recently so there might be better solutions than this (especially since the code feels kind of clumsy to me) - but your second point seemed to be just the right challenge for me to try out building a feedback loop within akka streams.

在此处找到我的完整解决方案： https://gist.github.com / MartinHH / de62b3b081ccfee4ae7320298edd81ee

Find my full solution here: https://gist.github.com/MartinHH/de62b3b081ccfee4ae7320298edd81ee

主要思想是累积已经找到的素数，并将它们与传入的自然数流合并，以便进行素数检查可以根据不超过N的结果来完成，例如：

The main idea was to accumulate the primes that are already found and merge them with the stream of incoming natural numbers so the primes-check could be done based on the results up to N like this:

def isPrime(n: Int, primesSoFar: SortedSet[Int]): Boolean =
  !primesSoFar.exists(n % _ == 0) &&
    !(primesSoFar.lastOption.getOrElse(2) to Math.floor(Math.sqrt(n)).toInt).par.exists(n % _ == 0)

这篇关于如何修改Akka Streams Prime筛子以排除已知质数的模检验？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！