測試一個有序的無限流是否包含一個值

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值，素數更密集，它會漸近地快得多。此外，當測試具有小除數（大多數具有）的非素數時，它非常快速。

如果您想測試另一個增加的流的元素的素數可能會不同。您可能會考慮類似於合併排序。你沒有說明你想如何得到你的結果，這裏是一個布爾流，但它不應該太難適應其他東西。

/** 
* 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中的元素往往是素數或者只有大的除數，那更不用說了。

Answer 2

1. 你只需要儘可能sqrt(s)閱讀您的首要流。
2. 當您從主要流中檢索每個p時，請檢查p是否均勻分配s。

這將給你一個初步檢查的試用劃分方法。

Answer 3

爲了解決確定的一般問題的有序有限清單是否包括完全有序，但無限流的元素：

最簡單的方法是

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) 
}