scala - Scala列表的上三角循环习惯用法

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

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 /任何版本的链表上编写一个高效的上三角循环。

我想我现在只能吞下2的倍数，但是这种情况很常见，感觉应该有一个不错的解决方案。

另外，此“上三角回路”是否有一个通用名称？我找不到合适的搜索字符串。

编辑：这是一个不好的解决方案的示例：

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

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

最佳答案

您可能要查看Vector数据类型，它允许进行基于快速索引的查找。

此外，还有一个内置的组合方法，它将为您提供所需的外观。

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