4

从我在命令式编程的背景来看，我习惯于做

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/whatever 中的链表上编写一个有效的上三角循环。

我想我现在可以吞下两个因素，但这是一种很常见的情况，感觉应该有一个很好的解决方案。

另外，这个“上三角环”有一个通用名称吗？我找不到合适的搜索字符串。

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

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

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

4

3 回答 3

6

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

此外，还有一种内置的组合方法，可以为您提供所需的外观。

scala> (1 to 3).combinations(2).mkString(" ")
res1: String = Vector(1, 2) Vector(1, 3) Vector(2, 3)
于 2013-09-09T21:31:43.920 回答
5

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

@tailrec def walk[T](list: Seq[T]): Unit =
  list match {
    case head :: tail =>
      tail.foreach(doSomething(head, _))
      walk(tail)
    case Nil =>
  }
于 2013-09-09T21:31:31.253 回答
-1

关于这部分问题：

另外，这个“上三角环”有一个通用名称吗？我找不到合适的搜索字符串。

“上三角环”的通用名称是三角矩阵。（如维基百科中所述）

...三角矩阵是一种特殊的方阵。如果主对角线以上的所有项都为零，则方矩阵称为下三角矩阵。类似地，如果主对角线以下的所有项都为零，则方矩阵称为上三角矩阵。

于 2014-07-31T08:04:06.923 回答