Scala: есть ли способ улучшить временную производительность этого сверточного кода? - PullRequest
Новая
       5

Scala: есть ли способ улучшить временную производительность этого сверточного кода?

0 голосов
/ 07 ноября 2018

Добрый день всем. Я пытался улучшить время выполнения этого кода в Scala: 

def TwoDimensionalConvolution(Input: => Array[Int], Height: => Int, Width: => Int, Kernel: => Array[Int]): Array[Int] = {
  val R = (Kernel.length - 1) >> 1

  val result = Array.ofDim[Int](Input.length)
  for (i <- 0 until Height) {
    for (j <- 0 until Width) {
      var acc = 0
      for (k <- j - R to j + R)
        if (k >= 0 && k < Width)
          acc += Input(i * Width + k) * Kernel(k + R - j)
      result(j * Height + i) = acc >> 8
    }
  }

  val Output = Array.ofDim[Int](Input.length)
  for (i <- 0 until Width) {
    for (j <- 0 until Height) {
      var acc = 0
      for (k <- j - R to j + R)
        if (k >= 0 && k < Height)
          acc += result(i * Height + k) * Kernel(k + R - j)
      Output(j * Width + i) = acc >> 8
    }
  }
  Output
}

Мой код выполняет двумерную свертку, используя линейную свертку строк и столбцов. Обратите внимание, что входной массив не является двумерным, но способ доступа к нему - линейный. Цикл for k позволяет выполнять итерацию по каждой строке или столбцу, не прибегая к нулю по краям.

Я также старался избегать максимально возможного сохранения промежуточных результатов, но, как вы можете видеть, переменная result, которая сохраняет свернутые строки, необходима для выполнения свертки столбцов.

Я не считаю себя экспертом в Scala и, хотя у меня есть некоторый опыт работы с C / C ++, я не могу улучшить время еще больше.

Правда в том, что я не могу думать о том, что еще я мог бы сделать с теми немногими знаниями функционального программирования, которые у меня есть.

Какой-нибудь эксперт по Scala может мне что-то подсказать? Спасибо всем заранее за чтение.

Ответы [ 2 ]

0 голосов
/ 07 ноября 2018

Одна оптимизация, которую я бы предложил, - оптимизировать цикл с помощью k. У вас есть: 

for (k <- j - R to j + R)
    if (k >= 0 && k < Height)
      acc += result(i * Height + k) * Kernel(k + R - j)

Однако, если k is < 0 || k >= Height, цикл ничего не делает, и вы выполняете итерации без необходимости.

Возможно, меняется на: 

for (k <- (j - R max 0) to (j + R min Height - 1))
     acc += result(i * Height + k) * Kernel(k + R - j)

Это исключает этот оператор if и обеспечивает отсутствие дополнительных итераций.

0 голосов
/ 07 ноября 2018

Определенно начните с избавления от параметров по имени (: => ...). Они становятся функциями, которые оцениваются при каждом использовании в методе, и даже если вы просто передаете переменные и литералы в вызов метода, все равно остаются нетривиальные издержки.

Попробуйте заменить for петли на while. Какой эффект это даст, будет зависеть от версии Scala и от того, передадите ли вы флаги оптимизации компилятору. Смотрите, например http://dynamicsofprogramming.blogspot.com/2017/01/performance-of-scala-for-loops.html для сравнения, включая Scala 2.12.

Вы также должны быть осторожны при измерении производительности: используйте Scalameter или JMH .

...