Scala for循环和迭代器

Question

让我们假设我有一个非常大的可迭代值集合(大约100,000个字符串条目,逐个从磁盘读取),我在其笛卡尔积上做了一些事情(并将结果写回磁盘,但我不会在这里显示):

for(v1 <- values; v2 <- values) yield ((v1, v2), 1)

我知道这只是另一种写作方式

values.flatMap(v1 => values.map(v2 => ((v1, v2), 1)))

这显然导致每个flatMap迭代(甚至整个笛卡尔积？)的整个集合保存在内存中.如果你使用for循环读取第一个版本,这显然是不必要的.理想情况下,只应将两个条目(正在组合的条目)保存在内存中.

如果我重新制定第一个版本:

for(v1 <- values.iterator; v2 <- values.iterator) yield ((v1, v2), 1)

内存消耗要低很多,这让我认为这个版本必须根本不同.它在第二个版本中的确有何不同？为什么Scala不会隐式使用第一个版本的迭代器？在某些情况下不使用迭代器时是否有任何加速？

谢谢!(还要感谢"lmm"谁回答了这个问题的早期版本)

Answer 1

在Scala中,yield不会产生惰性序列.我的理解是,您可以一次获取所有值,以便将它们全部索引为集合.例如,我为光线跟踪器编写了以下内容来生成光线:

def viewRays(aa:ViewHelper.AntiAliasGenerator) =
{
  for (y <- 0 until height; x <- 0 until width)
    yield (x, y, aa((x, y)))
}

它失败了(记忆力不足),因为它让所有的光线都在前面(惊喜!).通过使用该.iterator方法,您特别要求一个惰性迭代器.上面的例子可以修改为:

def viewRays(aa:ViewHelper.AntiAliasGenerator) =
{
  for (y <- 0 until height iterator; x <- 0 until width iterator)
    yield (x, y, aa((x, y)))
}

它以懒惰的方式工作.

Answer 2

第一个版本是严格评估的; 它创建了一个包含所有这些值的真实,具体的集合.第二个"just"提供了一个Iterator,它允许您遍历所有值; 它们将在您实际执行迭代时创建.

Scala默认为第一个的主要原因是因为scala作为一种语言允许副作用.如果您将两个映射写为:

for(v1 <- values; v2 <- values) yield {println("hello"); ((v1, v2), 1)}
for(v1 <- values.iterator; v2 <- values.iterator) yield {
  println("hello"); ((v1, v2), 1)}

然后第二个会发生什么可能会让你感到惊讶,特别是在一个更大的应用程序中,迭代器可能会在远离实际使用位置的地方创建.

如果映射操作本身很昂贵并且您创建一次并多次重用它,则集合将比迭代器执行得更好 - 迭代器每次都必须重新计算值,而集合存在于内存中.可以说这使得集合性能更具可预测性 - 它消耗了大量内存,但无论使用何种集合,它都是相同的数量.

如果你想要一个更愿意忽视操作和优化的集合库 - 也许是因为你已经编写了所有代码而没有副作用 - 你可能想要考虑Paul Philips的新努力.