algorithm - 有效检查Scala流中的​​值是否存在(以功能方式)

Question

我遇到了这个问题，对此我感到很困惑，但我不知道（而且似乎没有令人满意的答案）。我敢复制到这里：
假设我们有一个流，每个元素取决于它的前一个元素，就像对于siimple伪随机序列，例如：

def neum(a:Int): Stream[Int] = Stream.iterate(a)(a => (a*a/100)%10000)

这是一个von Neumann的随机数发生器
从给定的值开始，我们想知道序列何时进入循环。我们可以使用一组存储值的命令形式轻松地执行此操作：

// like in java
Set<Integer> values = new HashSet<>();
while (true) {
    int x = nextValueInSequence(x)
    if (values.contains(x)) {
        break;
    }
    values.add(x);
}

不过，对于scala来说，提出“功能性”解决方案是很有趣的。但是这个问题的作者似乎不知道如何保持“cccc>时间复杂性”。我也是。这里唯一的评论似乎是建议直接的 O(N)解决方案。

Answer 1

我相信，有一个算法，具有O（n log n）时间复杂度（可能会提高到O（n））和O（1）总内存消耗。也就是说，我们不必记住之前的大多数数字不过，常数因子相当高。
这种内存消耗不是用Stream计算的，而是用一个由起始元素和递归公式定义的常规数字序列计算的。例如Iterator.iterate(start)(a => a * a / 100 % 10000)。
Stream将记住以前的结果，并有效地使其成为o（n）内存。
假设序列在循环开始之前有p≥0个元素，在循环中有l≥1个元素。例如，序列[2, 10, 13, 9, 11, 17, 11, 17, ...]具有p=4和l=2。我们需要找到P+L。
在算法中，我们必须遍历序列。我将当前位置称为“指针”。在数字序列中，指针只表示一个数字。最初，指针等于序列的起始元素，要将指针向前移动一步，我们必须对其应用递归公式。
现在来看看算法：
从两个指向序列开头的指针开始：“slow”和“fast”慢速指针一次移动1步，快速指针一次移动2步（即递归公式的两个应用）。
最初指针是相等的开始向前移动，直到它们再次相等，并跟踪慢速指针的步数。让我们命名指针的步数，使其再次相等k0。可以证明，p≤k0 在这一步中，我们还应该特别注意当p=0时的情况：当指针变得相等时，如果它们也等于起始元素，我们应该设置k0=0，以便以后能够区分这种情况。
这个步骤的时间复杂度是O（n）。
现在指针肯定在序列的循环中。再次开始向前移动它们，并跟踪慢指针的步数，直到它们再次相等这个步数是序列的循环l的长度。（也可以在这个步骤中只移动慢指针，直到它回到相同的位置，但是我将重用函数来同时移动这两个函数，这不会增加时间复杂度）
这个步骤的时间复杂度是O（n）。
现在我们必须计算p。我们可以注意到，如果在算法的第2）步中，我们不是从一开始就启动“快速”指针，而是使用一些移位s:0≤s 这个步骤的时间复杂度是O（n log n），因为二进制搜索中的每一步都取O（n）。
所以我们有一个算法，它在O（N logn）和O（1）内存中工作下面是代码示例：

case class Sequence[T](start: T)(f: T => T) {
  def next = Sequence(f(start))(f)
  def forward(steps: Int) =
    Sequence(Function.chain(List.fill(steps)(f))(start))(f)
}

object Sequence {
  def neum(a: Int) = Sequence(a)(a => a * a / 100 % 10000)

  def movesToEquality[T](
    slow: Sequence[T], fast: Sequence[T], count: Int = 1
  ): (Sequence[T], Int) = {
    val nextSlow = slow.next
    val nextFast = fast.forward(2)
    if (nextSlow == nextFast) (nextSlow, count)
    else movesToEquality(nextSlow, nextFast, count+1)
  }

  def findLoopStart[T](seq: Sequence[T]): Int = {
    val (inLoop, k0) = movesToEquality(seq, seq) match {
      case (c, k) if c == seq => (c, 0)
      case other => other
    }
    val (_, loopSize) = movesToEquality(inLoop, inLoop)

    def binarySearch(lo: Int, hi: Int): Int = {
      if (lo + 1 >= hi) lo
      else {
        val mid = (lo + hi) / 2
        if (movesToEquality(seq, seq.forward(mid))._2 == k0 - mid)
          binarySearch(mid, hi)
        else
          binarySearch(lo, mid)
      }
    }

    k0 - binarySearch(0, loopSize) + loopSize
  }
}

object Main extends App {
  println(Sequence.findLoopStart(Sequence.neum(1)))
  println(Sequence.findLoopStart(Sequence.neum(4100)))
  println(Sequence.findLoopStart(Sequence.neum(5761)))
}