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

我有一个无限素数流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 
    }

来源

2011-09-28 Luigi Plinge

如果问题是关于实现isPrime，那么你应该按照rossum的建议做，即使分裂的成本超过了平等测试的范围，并且对于更低的n值，素数更密集，它会渐近地快得多。此外，当测试具有小除数（大多数具有）的非素数时，它非常快速。

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

/** 
* 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与素数相比快速增加，那么您必须枉费计算许多素数，以便跟上。如果没有理由怀疑你的Stream中的元素往往是素数或者只有大的除数，那更不用说了。

来源

2011-09-28 21:08:53

你只需要尽可能sqrt(s)阅读您的首要流。
当您从主要流中检索每个p时，请检查p是否均匀分配s。

这将给你一个初步检查的试用划分方法。

来源

2011-09-28 20:19:20 rossum

好的创意 - 这肯定会与此特定问题的帮助。我想知道是否更普遍地有搜索无限增长流的好方法。 –

为了解决确定的一般问题的有序有限清单是否包括完全有序，但无限流的元素：

最简单的方法是

candidate.toSet subsetOf infiniteList.takeWhile(_ <= candidate.last).toSet

但如果候选人是大，即需要大量的空间，它是O（n log n），而不是O（n）。在O（n）的方法是

def acontains(a : Int, b : Iterator[Int]) : Boolean = { 
    while (b hasNext) { 
    val c = b.next 
    if (c == a) { 
     return true 
    } 
    if (c > a) { 
     return false 
    } 
    } 
    return false 
} 

def scontains(candidate: List[Int], infiniteList: Stream[Int]) : Boolean = { 
    val it = candidate.iterator 
    val il = infiniteList.iterator 
    while (it.hasNext) { 
    if (!acontains(it.next, il)) { 
     return false 
    } 
    } 
    return true 
}

（顺便说一下，如果一些有用的灵魂可以提出一个更Scalicious方式写前面，我将不胜感激。）

编辑：

在评论中，路易吉不可估量Plinge指出，我可以只写：

def scontains(candidate: List[Int], infiniteStream: Stream[Int]) = { 
    val it = infiniteStream.iterator 
    candidate.forall(i => it.dropWhile(_ < i).next == i) 
}

来源

2011-09-29 16:24:58 Malvolio

这不是我想要做的，但是在你的'acontains'方法中可以用'b.dropWhile（_ il.dropWhile（_

D'oh。令人惊讶的是，只有对函数定义的轻微误解才能做到。我在脑海中认为'dropWhile'会放弃失败的第一个元素，并且'forAll'是'forEach'的变体。顺便说一句，它没有用'next'编译，我需要'head'。 – Malvolio

而@LuigiPlinge，你做了什么*你想做什么。 – Malvolio

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

回答

相关问题