从一系列项目的迭代器中创建子序列迭代器

Question

如果我有一个Seq，那么生成所有长度不超过给定限制的子序列就很容易了，方法如下：

def subseqs[A](n: Int)(s: Seq[A]) = {
  (1 to n).flatMap(s.sliding)
}                                            

subseqs(3)(List(1, 2, 3, 4)) foreach println    //> List(1)
                                                //| List(2)
                                                //| List(3)
                                                //| List(4)
                                                //| List(1, 2)
                                                //| List(2, 3)
                                                //| List(3, 4)
                                                //| List(1, 2, 3)
                                                //| List(2, 3, 4)

然而，是否有一种惯用的（且相对高效）方法来处理迭代器作为输入，并产生一个迭代器（或者可能是流）作为输出？ 更新：我有一个工作实现，它实现了Iterator，并在单次遍历中完成了此操作，因此需要很少的内存，但相对较长并使用可变变量（var和ListBuffer） - 如果有帮助，可以发布此内容。我希望使用高阶函数有一种更优雅的方式...

上面的方法（使用sliding()）行不通，因为第一次遍历时迭代器已经用尽，不能重新使用。

使用sliding()和inits()的组合更好，但会错过预期子序列的尾部：

def subseqsi[A](n: Int)(i: Iterator[A]) = {
  //(1 to n).flatMap(i.sliding) 
  // no - this exhausts the iterator

  i.sliding(n).flatMap { _.inits.filterNot(_.isEmpty) } 
  //nearly, this misses off subsequences towards the end
} 
                                              //> List(1, 2, 3)
                                              //| List(1, 2)
                                              //| List(1)
                                              //| List(2, 3, 4)
                                              //| List(2, 3)
                                              //| List(2)

我的输入数据是一个大小未知（可能非常大）的迭代器。输出子序列的顺序并不重要。

- DNA

---

这是我以前用Haskell编写的高尔夫程序之一。我会提供Haskell代码，并将其翻译为Scala留给读者自行完成 :) init . tails <=< tail . inits 可以在有限和无限列表上运行，因此它本质上必须是懒惰的！鱼/<=< 运算符源自 Control.Monad 并且是Kleisli组合。 - Mysterious Dan

Answer 1

只需使用一个Stream：

def subseqs[A](n: Int)(iter: Iterator[A]) = {
  val i = iter.toStream
  1 to n flatMap i.sliding
}

流（Stream）和迭代器（Iterator）一样是惰性的，但它会存储所有已经计算出来的值。

- kiritsuku

---

这段代码很漂亮，输出也正确，但是它会急切地创建一个包含 n 个 Stream 的 IndexedSeq，在处理大量输入数据时表现不佳，例如 (1 to 1000000).iterator。如果你在 (1 to n) 中添加 toStream，我认为它会更懒惰一些...？ - DNA

"1 to n" 是严格的，当然。toStream 或 iterator 使其变为惰性。 - kiritsuku

好的，toStream 有所帮助，但不幸的是随着 n 的增加，它仍然非常消耗内存（可能是因为我们最终会记忆化整个序列？）。对于 n 最多到1000左右，差异很小；对于 n=1,000,000，我在当前堆大小下遇到了GC问题。使用 iterator 更好；n=1,000,000 可以，但再增加10倍就会再次出现问题。 - DNA

当然，当你增加n时，你需要更多的内存。Scala的stdlib不支持一种数据结构，如果n太大，它会自动清理其缓存，你要么必须找到一个库来实现这个功能，要么自己构建它。 - kiritsuku

Answer 2

这里有另一种使用流的方法 - 它使用flatMap/sliding方法来处理最后几个元素，比起之前提到的方法要不那么优雅，但是速度更快，占用内存更少。

def subseqs[A](n: Int)(s: Iterator[A]) = {
  def loop(s: Stream[A], history: Vector[A]): Stream[Seq[A]] = {
    if (s.isEmpty) (1 to n).flatMap(history.sliding).toStream
    else if (history.length == n) 
      history.inits.filterNot(_.isEmpty).toStream #::: loop(s.tail, history.tail :+ s.head)
    else loop(s.tail, history :+ s.head)
  }
  loop(s.toStream, Vector())
}

这个函数会在有n个元素之前建立起一个历史记录，输出“inits”，然后将历史记录向前移动。然而，这段代码不仅令人困惑，而且返回的结果也是以一种不美观的顺序排列，因为需要将流的末尾视为特殊情况进行处理：

subseqs(3)(List(1, 2, 3, 4)) foreach println  > Vector(1, 2, 3)
                                              | Vector(1, 2)
                                              | Vector(1)
                                              | Vector(2)
                                              | Vector(3)
                                              | Vector(4)
                                              | Vector(2, 3)
                                              | Vector(3, 4)
                                              | Vector(2, 3, 4)

我仍然希望一个优雅且快速的解决方案是可能的...

- DNA

---

你看到我的 Haskell 解决方案了吗？ - Mysterious Dan

我看了，谢谢 - 看起来很酷，但我目前不知道如何将其翻译成Scala，或者它的性能如何 - 显然Haskell和Scala在惰性、编译等方面有很大的不同。 - DNA