Scala列表的上三角循环习语

Question

从命令式编程的背景来看,我已经习惯了

for (i = 0;  i < 1000000;  i++) {
    for (j = i + 1;  j < 1000000;  j++) {
        doSomething(array[i], array[j])
    }
}

检查百万元素数组中的所有唯一对. doSomething是一些在对角线上对角线和对称或反对称结果产生微不足道结果的操作 - 这就是为什么我只想在上三角形上工作.(这里有一个很小的变体,i == j案例很有趣;这很容易解决.)

我发现自己奇怪地试图在Scala中做这件事.我有一个大的List,想要对所有成对组合做一些事情,但是

list.flatMap(x => list.map(y => doSomething(x, y))

包括所有冗余或琐碎的案例(两个太多的工作因素)和

(0 until 1000000).flatMap({i =>
  (0 until 1000000).map({j =>
    doSomething(list(i), list(j))
  })
})

会是非常错误的,因为列表不是随机访问(N ^ 2因子太多的工作).我可以把我转换Lists成Arrays,但感觉它错过了重点. Lists是链接列表,因此j + 1我的命令示例中的元素距离我i目前正在检查的仅一步之遥.我敢肯定我可以用C/Python /中的链接列表编写一个有效的上三角循环.

我想我现在可以吞下两个因子,但这是一个常见的情况,因为它应该有一个很好的解决方案.

此外,这个"上三角形环"是否有一个共同的名称？我找不到一个好的搜索字符串.

编辑:这是一个糟糕的解决方案的例子:

list.zipWithIndex.flatMap({case (x, i) =>
  list.zipWithIndex.map({case (y, j) =>
    if (j > i)
      doSomething(x, y)
    else
      Nil
  })
})

因为它仍然访问不需要的节点.

Answer 1

您可能希望查看Vector数据类型,它允许基于快速索引的查找.

此外,还有一个内置的组合方法,可以为您提供您正在寻找的样子.

scala> (1 to 3).combinations(2).mkString(" ")
res1: String = Vector(1, 2) Vector(1, 3) Vector(2, 3)

Answer 2

您可以通过以下方式使用模式匹配和尾递归:

@tailrec def walk[T](list: Seq[T]): Unit =
  list match {
    case head :: tail =>
      tail.foreach(doSomething(head, _))
      walk(tail)
    case Nil =>
  }