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

发布时间：2020-12-16 18:19:49 所属栏目：安全来源：网络整理

导读：我有一个无限的素数primeStream流(从2开始增加).我还有另一个Ints流,它的数量增加,我想测试这些是否都是素数. 有效的方法是什么？我可以定义 def isPrime(n: Int) = n == primeStream.dropWhile(_ n).head 但这似乎效率低下,因为它需要每次迭代整个流. prime

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

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

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
  }

解决方法

如果问题是关于实现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)
   }
}

所以你可能属于(yourStream,primeStream)

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!