4

命令型プログラミングのバックグラウンドから、私はやることに慣れています

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

100 万要素配列内のすべての一意のペアを調べます。 doSomethingは、対角線上で自明な結果をもたらし、対角線から対称または反対称の結果をもたらす操作です。i == j(ケースが興味深い場合には、これのマイナーな変形があります。これは簡単に修正できます。)

Scalaでこれをやろうとすると、奇妙なことに立ち往生しています。私は大きなものを持ってListいて、すべてのペアワイズの組み合わせに何かをしたいのですが、

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

すべての冗長または些細なケース (作業量が 2 分の 1) を含み、

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

リストはランダムアクセスではないため、非常に間違っています（N ^ 2の要素が多すぎます）。に変換できましたListsがArrays、それは要点を逃しているように感じます。 Listsリンクされたリストであるため、私の命令型の例の要素は、現在調べているj + 1要素から一歩離れたところにあります。iC / Python /その他で、リンクされたリストに対して効率的な上三角ループを作成できると確信しています。

今のところ、係数 2 を飲み込むことができると思いますが、これは非常に一般的な状況に遭遇するため、適切な解決策があるはずだと感じています。

また、この「上三角ループ」に通称はありますか？適切な検索文字列が見つかりませんでした。

編集：これは悪い解決策の例です：

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 に答える