测试有序的无限流是否包含值

Question

我有一个无限的素数流primeStream(从2开始增加).我还有另一股Ints s,它的数量增加,我想测试这些是否都是素数.

有效的方法是什么？我可以定义

def isPrime(n: Int) = n == primeStream.dropWhile(_ < n).head

但这似乎效率低下,因为它需要每次迭代整个流.

实施primeStream(从其他地方无耻地复制):

  val primeStream: Stream[Int] =
  2 #:: primeStream.map{ i =>
    Stream.from(i + 1)
    .find{ j =>
      primeStream.takeWhile{ k => k * k <= j }
        .forall{ j % _ > 0 }
    }.get
  }

Answer 1

如果问题是关于实现isPrime,那么你应该按照rossum的建议去做,即使划分成本超过相等测试,并且对于较低的n值,质数更密集,它将渐近地更快.此外,在测试具有小除数的非素数时(非常多数),它非常快

如果您想测试另一个不断增加的Stream的元素的素数,则可能会有所不同.您可以考虑类似于合并排序的东西.你没有说明你想要如何得到你的结果,这里是一个布尔流,但它不应该太难以适应其他东西.

/** 
 *  Returns a stream of boolean, whether element at the corresponding position
 *  in xs belongs in ys. xs and ys must both be increasing streams.
 */
def belong[A: Ordering](xs: Stream[A], ys: Stream[A]): Stream[Boolean] = {
   if (xs.isEmpty) Stream.empty
   else if (ys.isEmpty) xs.map(_ => true)
   else Ordering[A].compare(xs.head, ys.head) match {
     case less if less < 0 => false #:: belong(xs.tail, ys)
     case equal if equal == 0 => true #:: belong(xs.tail, ys.tail)
     case greater if greater > 0 => belong(xs, ys.tail)
   }
}

所以你可能会这样做 belong(yourStream, primeStream)

然而,这个解决方案并不比每个数字的素数的单独测试更好,并且在平方根处停止.特别是如果yourStream与素数相比快速增长,那么你必须徒劳地计算许多质数,只是为了跟上.如果没有理由怀疑你的流中的元素往往是素数或只有大的除数,那就更不用说了.