14

我对 Scala 很陌生，所以请原谅我的无知！我正在尝试迭代以最大值为界的整数对。例如，如果最大值为 5，则迭代应返回：

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5)

我选择尝试以递归方式将其作为流返回：

    @tailrec
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = {
        if (i == maximum && j == maximum) Stream.empty
        else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum)
        else (i, j) #:: _pairs(i, j + 1, maximum)
    }

如果没有 tailrec 注释，代码可以工作：

scala> _pairs(0, 0, 5).take(11)
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> _pairs(0, 0, 5).take(11).toList
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,1), (1,2), (1,3), (1,4))

但这对我来说还不够好。编译器正确地指出 _pairs 的最后一行没有返回 _pairs：

could not optimize @tailrec annotated method _pairs: it contains a recursive call not in tail position
    else (i, j) #:: _pairs(i, j + 1, maximum)
                ^

所以，我有几个问题：

  • 直接解决上面的实现，尾递归如何返回 Stream[(Int, Int)]？
  • 退后一步，迭代有界整数序列的最节省内存的方法是什么？我不想迭代 Range 因为Range 扩展 IndexedSeq，我不希望序列完全存在于内存中。还是我错了？如果我遍历 Range.view 我会避免它进入内存吗？

在 Python（！）中，我想要的只是：

In [6]: def _pairs(maximum):
   ...:     for i in xrange(maximum+1):
   ...:         for j in xrange(maximum+1):
   ...:             yield (i, j)
   ...:             

In [7]: p = _pairs(5)

In [8]: [p.next() for i in xrange(11)]
Out[8]: 
[(0, 0),
 (0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (0, 5),
 (1, 0),
 (1, 1),
 (1, 2),
 (1, 3),
 (1, 4)]

谢谢你的帮助！如果您认为我需要阅读参考资料/API 文档/其他任何内容，请告诉我，因为我很想学习。

4

2 回答 2

28

这不是尾递归

假设您正在制作一个列表而不是一个流：（让我使用一个更简单的函数来说明我的观点）

def foo(n: Int): List[Int] =
  if (n == 0)
    0 :: Nil
  else
    n :: foo(n - 1)

在这个递归的一般情况下，在foo(n - 1)返回之后，函数必须对它返回的列表做一些事情——它必须将另一个项目连接到列表的开头。所以函数不能是尾递归的，因为递归之后必须对列表做一些事情。

如果没有尾递归，对于某些较大的 值n，您会耗尽堆栈空间。

通常的列表解决方案

通常的解决方案是将 aListBuffer作为第二个参数传递，并填充它。

def foo(n: Int) = {
  def fooInternal(n: Int, list: ListBuffer[Int]) = {
    if (n == 0) 
      list.toList
    else {
      list += n
      fooInternal(n - 1, list)
    }
  }
  fooInternal(n, new ListBuffer[Int]())
}

您正在做的事情被称为“尾递归模 cons ”，这是LISP Prolog 编译器在看到尾递归模 cons 模式时自动执行的优化，因为它很常见。Scala 的编译器不会自动对此进行优化。

流不需要尾递归

流不需要尾递归来避免堆栈空间用完——这是因为它们使用了一个聪明的技巧来阻止执行递归调用到foo它出现在代码中的位置。函数调用被包装在一个 thunk 中，并且仅在您实际尝试从流中获取值时调用。一次只有一个调用foo处于活动状态——它从不递归。

我已经写了一个先前的答案，解释了#::操作员如何在 Stackoverflow 上工作。以下是调用以下递归流函数时发生的情况。（它在数学意义上是递归的，但它不会像您通常期望的那样从函数调用中进行函数调用。）

def foo(n: Int): Stream[Int] =
  if (n == 0)
    0 #:: Nil
  else
    n #:: foo(n - 1)

你调用foo(10)，它返回一个已经计算了一个元素的流，而尾部是一个 thunk ，foo(9)下次你需要流中的一个元素时会调用它。foo(9)现在没有调用——而是调用绑定到lazy val流内部的 a ，并foo(10)立即返回。当您最终确实需要流中的第二个值时，foo(9)将调用它，它会计算一个元素并将 hte 流的尾部设置为将调用foo(8). foo(9)立即返回而不调用foo(8). 等等...

这允许您创建无限流而不会耗尽内存，例如：

def countUp(start: Int): Stream[Int] = start #::countUp(start + 1)

（注意你在这个流上调用了什么操作。如果你尝试做 aforEach或 a map，你会填满你的整个堆，但是 usingtake是处理流的任意前缀的好方法。）

一个更简单的解决方案

与其处理递归和流，为什么不直接使用 Scala 的for循环呢？

def pairs(maximum:Int) =
  for (i <- 0 to maximum;
       j <- 0 to maximum)
    yield (i, j)

这会在内存中实现整个集合，并返回一个IndexedSeq[(Int, Int)].

如果您特别需要 Stream，您可以将第一个范围转换为Stream.

def pairs(maximum:Int) =
  for (i <- 0 to maximum toStream;
       j <- 0 to maximum)
    yield (i, j)

这将返回一个Stream[(Int, Int)]. 当您访问序列中的某个点时，它将被物化到内存中，并且只要您仍然引用该元素之前的流中的任何点，它就会一直存在。

通过将两个范围都转换为视图，您可以获得更好的内存使用率。

def pairs(maximum:Int) =
  for (i <- 0 to maximum view;
       j <- 0 to maximum view)
    yield (i, j)

每次需要时都会返回一个SeqView[(Int, Int),Seq[_]]计算每个元素的值，并且不存储预先计算的结果。

你也可以用同样的方法得到一个迭代器（你只能遍历一次）

def pairs(maximum:Int) =
  for (i <- 0 to maximum iterator;
       j <- 0 to maximum iterator)
    yield (i, j)

那返回Iterator[(Int, Int)]。

于 2012-05-09T23:26:03.530 回答
2

也许 Iterator 更适合您？

class PairIterator (max: Int) extends Iterator [(Int, Int)] {
  var count = -1
  def hasNext = count <= max * max 
  def next () = { count += 1; (count / max, count % max) }
}

val pi = new PairIterator (5)
pi.take (7).toList
于 2012-05-10T01:06:59.753 回答