Каков самый быстрый способ вычесть два массива в scala

У меня есть два массива (которые я вытащил из матрицы (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
}

Результаты, которые, как мне казалось, я получил в первый раз, были прямо противоположными... Должно быть, я неправильно понял или перепутал методы.

Мои извинения за некорректный вопрос.


scala micro-optimization scala-2.9
person Mike Lavender    schedule 18.12.2012    source источник
comment
Как вы измеряете производительность? Вы уверены, что список быстрее, чем массив? Разница в производительности действительно имеет значение?   -  person Zane    schedule 19.12.2012
comment
Когда больше ничего не помогает, вы можете попробовать напрямую поиграть с памятью (как в C) с помощью sun.misc.Unsafe. Я слышал, что прямое манипулирование байтовыми буферами может ускорить сложную математику до 30% (думаю, потому что у нас нет проверок границ массива, но они также могут быть устранены HotSpot), но лично не пробовал. . Обратите внимание, что это крайняя мера.   -  person om-nom-nom    schedule 19.12.2012
comment
Кстати, я очень сомневаюсь, что List здесь может быть быстрее, чем массив, вы уверены, что делаете правильные измерения?   -  person om-nom-nom    schedule 19.12.2012
comment
@ Зейн, посмотри мой ответ. Измеренная производительность с помощью Scalameter.   -  person Brian    schedule 19.12.2012

Ответы (2)


arrow_upward
5
arrow_downward

Этот код является самым быстрым, с которым вы можете работать в однопоточном режиме, используя стандартную JVM. Если вы думаете, что List работает быстрее, вы либо обманываете себя, либо на самом деле не говорите нам, что делаете. Помещение Int в List требует создания двух объектов: одного для создания элемента списка и одного для создания целого числа. Создание объектов занимает примерно в 10 раз больше времени, чем доступ к массиву. Так что это действительно невыгодно делать это любым другим способом.

Если вам действительно нужно работать быстрее и вы должны оставаться с одним потоком, вам, вероятно, следует переключиться на C++ или тому подобное и явно использовать инструкции SSE. См., например, этот вопрос.

Если вам действительно нужно работать быстрее и можно использовать несколько потоков, то проще всего упаковать такой кусок работы (т. е. разумное количество пар векторов, которые необходимо вычесть — вероятно, по крайней мере несколько миллионов элементов на блок) в список, длина которого равна количеству процессоров на вашем компьютере, а затем вызовите list.par.map(yourSubtractionRoutineThatActsOnTheChunkOfWork).

Наконец, если ты можешь быть разрушительным,

a(i) -= b(i)

во внутреннем цикле, конечно, быстрее. Точно так же, если вы можете повторно использовать пространство (например, с System.arraycopy), вам лучше, чем если бы вам приходилось постоянно его выделять. Но это меняет интерфейс по сравнению с тем, что вы показали.

person Rex Kerr    schedule 18.12.2012

arrow_upward
1
arrow_downward

Вы можете использовать Scalameter, чтобы протестировать две реализации, для которых требуется как минимум JRE 7 update 4 и Scala 2.10. быть запущенным. Я использовал Скала 2.10 RC2.

Скомпилируйте с 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. Я предполагаю, что это потому, что он много раз измеряет производительность.

person Brian    schedule 19.12.2012