14

最近、Scala 開発者の面接を受けました。そんな質問をされました

// matrix 100x100 (content unimportant)

val matrix = Seq.tabulate(100, 100) { case (x, y) => x + y }

// A

for {

   row <- matrix

   elem <- row

} print(elem)

// B

val func = print _
for {

   row <- matrix

   elem <- row

} func(elem)

問題は、A と B のどちらの実装がより効率的かということでした。

私たちは皆、理解のために翻訳できることを知っています

// A

matrix.foreach(row => row.foreach(elem => print(elem)))

// B

matrix.foreach(row => row.foreach(func))

B は次のように記述できます。matrix.foreach(row => row.foreach(print _))

printAは100倍以上の関数を作成するため、おそらく正しい答えはBです。

言語仕様を確認しましたが、まだ答えを理解できません。誰かが私にこれを説明できますか？

4

3 に答える 3

8

要するに：

例 A は理論的には高速ですが、実際には違いを測定することはできません。

長い答え:

すでにお分かりのとおり

for {xs <- xxs; x <- xs} f(x)

に翻訳されます

xxs.foreach(xs => xs.foreach(x => f(x)))

これは §6.19 SLS で説明されています。

for ループ

for ( p <- e; p' <- e' ... ) e''

ここで、... はジェネレーター、定義、またはガードの (場合によっては空の) シーケンスであり、次のように変換されます。

e .foreach { case p => for ( p' <- e' ... ) e'' }

関数リテラルを記述すると、関数を呼び出す必要があるたびに新しいインスタンスが取得されます (§6.23 SLS)。この意味は

xs.foreach(x => f(x))

と同等です

xs.foreach(new scala.Function1 { def apply(x: T) = f(x)})

ローカル関数型を導入する場合

val g = f _; xxs.foreach(xs => xs.foreach(x => g(x)))

関数リテラルを にまだ渡しているため、最適化を導入していませんforeach。実際には、内部foreachが次のように変換されるため、コードは遅くなります。

xs.foreach(new scala.Function1 { def apply(x: T) = g.apply(x) })

applyのメソッドへの追加の呼び出しがg発生する場所。ただし、書き込み時に最適化できます

val g = f _; xxs.foreach(xs => xs.foreach(g))

内側のforeachnow が変換されるため

xs.foreach(g())

これは、関数g自体が に渡されることを意味しforeachます。

これは、 for 内包表記の本体が実行されるたびに無名関数を作成する必要がないため、理論的には B の方が高速であることを意味します。ただし、上記の最適化 (関数が に直接渡されるforeach) は内包表記には適用されません。仕様にあるように、変換には関数リテラルの作成が含まれているため、不要な関数オブジェクトが常に作成されるためです (ここでは、コンパイラーもそれを最適化できますが、内包表記の最適化は難しく、2.11 ではまだ行われていないため、そうではありません)。全体として、A はより効率的ですが、for 内包表記なしで記述された場合 (そして最も内側の関数に対して関数リテラルが作成されない場合)、B はより効率的であることを意味します。

それにもかかわらず、これらのルールはすべて理論的にしか適用できません。実際には、最適化を実行できる scalac のバックエンドと JVM 自体があり、CPU によって実行される最適化は言うまでもありません。さらに、あなたの例には、すべての反復で実行される syscall が含まれています。これはおそらく、ここで最も高価な操作であり、他のすべてよりも重要です。

于 2014-05-19T14:48:17.393 に答える
2

私はsschaefAに同意し、それがより効率的なオプションだと言います.

生成されたクラス ファイルを見ると、次の無名関数とその適用メソッドが得られます。

MethodA:
  anonfun$2            -- row => row.foreach(new anonfun$2$$anonfun$1)
  anonfun$2$$anonfun$1 -- elem => print(elem)

すなわちmatrix.foreach(row => row.foreach(elem => print(elem)))

MethodB:
  anonfun$3            -- x => print(x)
  anonfun$4            -- row => row.foreach(new anonfun$4$$anonfun$2)
  anonfun$4$$anonfun$2 -- elem => func(elem)

つまりmatrix.foreach(row => row.foreach(elem => func(elem))) 、 wherefuncは を呼び出す前のもう 1 つの間接参照printです。さらに、各行funcのインスタンス ( ) でメソッド呼び出しを介して検索する必要があります。this.func()

したがって、メソッド B では、1 つの追加オブジェクトが作成され ( func)、# of elem追加の関数呼び出しがあります。

最も効率的なオプションは

matrix.foreach(row => row.foreach(func))

これは、作成されるオブジェクトの数が最も少なく、期待どおりに動作するためです。

于 2014-05-19T15:30:49.233 に答える
2

基準

概要

方法 A は、方法 B よりも 30% 近く高速です。

コードへのリンク: https://gist.github.com/ziggystar/490f693bc39d1396ef8d

実装の詳細

メソッド C (2 つの while ループ) と D (fold、sum) を追加しました。また、マトリックスのサイズを大きくし、IndexedSeq代わりに an を使用しました。また、 をより軽いものに置き換えましたprint（すべてのエントリを合計します）。

奇妙なことに、このwhile構造は最速ではありません。しかし、Array代わりに使用IndexedSeqすると、大きな差で最速になります (ファクター 5、もはやボクシングはありません)。明示的にボックス化された整数を使用すると、メソッド A、B、C はすべて等しく高速になります。特に、A、B の暗黙的にボックス化されたバージョンと比較して、50% 高速です。

結果

A
4.907797735
4.369745787
4.375195012000001
4.7421321800000005
4.35150636
B
5.955951859000001
5.925475619
5.939570085000001
5.955592247
5.939672226000001
C
5.991946029
5.960122757000001
5.970733164
6.025532582
6.04999499
D
9.278486201
9.265983922
9.228320372
9.255641645
9.22281905
verify results
999000000
999000000
999000000
999000000

>$ scala -version
Scala code runner version 2.11.0 -- Copyright 2002-2013, LAMP/EPFL

コードの抜粋

val matrix = IndexedSeq.tabulate(1000, 1000) { case (x, y) => x + y }

def variantA(): Int = {
  var r = 0
  for {
    row <- matrix
    elem <- row
  }{
    r += elem
  }
  r
}

def variantB(): Int = {
  var r = 0
  val f = (x:Int) => r += x
  for {
    row <- matrix
    elem <- row
  } f(elem)
  r
}

def variantC(): Int = {
  var r = 0
  var i1 = 0
  while(i1 < matrix.size){
    var i2 = 0
    val row = matrix(i1)
    while(i2 < row.size){
      r += row(i2)
      i2 += 1
    }
    i1 += 1
  }
  r
}

def variantD(): Int = matrix.foldLeft(0)(_ + _.sum)
于 2014-05-19T16:00:41.177 に答える