Scala列表的上三角循环习惯用法 [英] Upper-triangular loop idiom for Scala Lists

问题描述

从我在命令式编程方面的背景开始，我就习惯了

From my background in imperative programming, I'm accustomed to doing

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

检查一百万个元素数组中的所有唯一对. doSomething是在对角线上产生平凡结果而在对角线上产生对称或反对称结果的某些运算，这就是为什么我只想在上三角上工作的原因. (有一个较小的变体，其中i == j的情况很有趣；很容易解决.)

to examine all unique pairs in a million element array. doSomething is some operation that yields trivial results on diagonal and symmetric or antisymmetric results off diagonal--- that's why I only want to work on the upper triangle. (There's a minor variant of this where the i == j case is interesting; that's easy to fix.)

我发现自己很奇怪地试图在Scala中这样做.我有一个很大的List，想对所有成对组合进行操作，但是

I find myself oddly stuck trying to do this in Scala. I have a large List and want to do something to all the pairwise combinations, but

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

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

includes all the redundant or trivial cases (a factor of two too much work) and

(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/任何内容中的链接列表上编写一个有效的上三角循环.

would be very wrong because Lists are not random access (a factor of N^2 too much work). I could convert my Lists to Arrays, but that feels like it misses the point. Lists are linked lists, so the j + 1 element from my imperative example is only a step away from the i I'm currently examining. I'm sure I could write an efficient upper-triangular loop over linked lists in C/Python/whatever.

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

I suppose I can just swallow the factor of two for now, but this is such a common situation to run into that it feels like there ought to be a nice solution to it.

此外，这个上三角回路"是否有一个通用名称?我找不到合适的搜索字符串.

Also, does this "upper-triangular loop" have a common name? I couldn't find a good search string for it.

这是一个不好的解决方案的示例:

Here's an example of a bad solution:

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

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

because it still visits the unwanted nodes.

推荐答案

您可能希望查看

You may want to look at the Vector data type, it allows for quick indexed based look up.

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

Also, there is a built in combinations method that will give you what it looks like you are looking for.

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

这篇关于Scala列表的上三角循环习惯用法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！