7

2つの配列（行列から引き出した配列（Array [Array [Int]]）があり、一方を他方から減算する必要があります。

現在、この方法を使用していますが、プロファイルを作成すると、ボトルネックになります。

def subRows(a: Array[Int], b: Array[Int], sizeHint: Int): Array[Int] = {
   val l: Array[Int] = new Array(sizeHint)
   var i = 0
   while (i < sizeHint) {
     l(i) = a(i) - b(i)
     i += 1
   }
   l
 }

私はこれを何十億回も行う必要があるので、速度の向上はプラスです。

Listの代わりにを使用して違いを収集しようとしましたArrayが、はるかに高速ですが、に戻すとすべてのメリットが失われますArray。

ダウンストリームコードを変更して、Listそれが役立つかどうかを確認しましたが、リストの内容に順不同でアクセスする必要があるため、ここでもゲインが失われます。

あるタイプから別のタイプへの変換には費用がかかるようです。もっと速い地図などを使用する方法があるのではないかと思います。

もっと良い方法はありますか？

編集

初めて何をしたのかわからない！？

だから私がそれをテストするために使用したコードはこれでした：

def subRowsArray(a: Array[Int], b: Array[Int], sizeHint: Int): Array[Int] = {
  val l: Array[Int] = new Array(sizeHint)
  var i = 0
  while (i < sizeHint) {
    l(i) = a(i) - b(i)
    i += 1
  }
  l
}

def subRowsList(a: Array[Int], b: Array[Int], sizeHint: Int): List[Int] = {
  var l: List[Int] = Nil
  var i = 0
  while (i < sizeHint) {
    l = a(i) - b(i) :: l
    i += 1
  }
  l
}

val a = Array.fill(100, 100)(scala.util.Random.nextInt(2))
val loops = 30000 * 10000

def runArray = for (i <- 1 to loops) subRowsArray(a(scala.util.Random.nextInt(100)), a(scala.util.Random.nextInt(100)), 100)

def runList = for (i <- 1 to loops) subRowsList(a(scala.util.Random.nextInt(100)), a(scala.util.Random.nextInt(100)), 100)

def optTimer(f: => Unit) = {
  val s = System.currentTimeMillis
  f
  System.currentTimeMillis - s
}

これを初めて行ったときに得たと思った結果は正反対でした...私は方法を読み間違えたか、混同したに違いありません。

悪い質問をしてしまったことをお詫びします。

4

2 に答える 2

6

このコードは、標準のJVMを使用してシングルスレッドで管理できる最速のコードです。あなたがより速いと思うならList、あなたは自分をだましているか、実際にあなたがしていることを私たちに話していないかのどちらかです。intoIntを入れるにListは、2つのオブジェクトを作成する必要があります。1つはリスト要素を作成するためのもので、もう1つは整数をボックス化するためのものです。オブジェクトの作成には、配列アクセスの約10倍の時間がかかります。したがって、他の方法でそれを行うことは、実際には勝利の提案ではありません。

本当にもっと速くする必要があり、単一のスレッドを維持する必要がある場合は、おそらくC ++などに切り替えて、SSE命令を明示的に使用する必要があります。たとえば、この質問を参照してください。

本当にもっと速くする必要があり、複数のスレッドを使用できる場合、最も簡単なのは、このような作業のチャンクをパッケージ化することです（つまり、減算する必要のあるベクトルの適切な数のペア-おそらく少なくとも数百万チャンクあたりの要素）をマシン上のプロセッサの数だけリストに入れてから、を呼び出しますlist.par.map(yourSubtractionRoutineThatActsOnTheChunkOfWork)。

最後に、あなたが破壊的である可能性がある場合、

a(i) -= b(i)

もちろん、内側のループの方が高速です。同様に、スペースを再利用できる場合（たとえば、を使用してSystem.arraycopy）、スペースを割り当て続ける必要がある場合よりも有利です。しかし、それはあなたが示したものからインターフェースを変更します。

于 2012-12-18T22:23:52.557 に答える
1

Scalameterを使用して、少なくともJRE 7update4とScala2.10を実行する必要がある2つの実装のベンチマークを試すことができます。私はscala2.10RC2を使用しました。

でコンパイルしscalac -cp scalameter_2.10-0.2.jar RangeBenchmark.scalaます。

で実行しscala -cp scalameter_2.10-0.2.jar:. RangeBenchmarkます。

これが私が使用したコードです：

import org.scalameter.api._

object RangeBenchmark extends PerformanceTest.Microbenchmark {
  val limit = 100
  val a = new Array[Int](limit)
  val b = new Array[Int](limit)
  val array: Array[Int] = new Array(limit)
  var list: List[Int] = Nil
  val ranges = for {
    size <- Gen.single("size")(limit)
  } yield 0 until size

  measure method "subRowsArray" in {
    using(ranges) curve("Range") in {
      var i = 0
      while (i < limit) {
        array(i) = a(i) - b(i)
        i += 1
      }
      r => array
    }
  }

  measure method "subRowsList" in {
    using(ranges) curve("Range") in {
      var i = 0
      while (i < limit) {
        list = a(i) - b(i) :: list
        i += 1
      }
      r => list
    }
  }
}

結果は次のとおりです。

::Benchmark subRowsArray::
Parameters(size -> 100): 8.26E-4

::Benchmark subRowsList::
Parameters(size -> 100): 7.94E-4

あなたはあなた自身の結論を引き出すことができます。:)

スタックは、の値が大きくなると爆発しましたlimit。何度もパフォーマンスを測定しているからだと思います。

于 2012-12-19T03:02:20.350 に答える