Как написать хороший фильтр нижних частот в Scala

Question

Мне понадобился фильтр нижних частот в одном из моих проектов Scala, и он придумал следующее:

def filter(numbers: Seq[Double], filterSize: Int): Seq[Double] = {
  assert(filterSize > 0)
  val ringBuffer = new Array[Double](filterSize)
  var ringBufferIndex = 0

  numbers.map(x => {
    // update ring buffer
    ringBuffer(ringBufferIndex) = x

    // increase ring index
    ringBufferIndex += 1 
    if (ringBufferIndex == filterSize) {
      ringBufferIndex = 0
    }

    // get avarage
    ringBuffer.foldLeft(0.0)(_ + _) / filterSize
  })
}

Однако есть некоторые вещи, которые мне не нравятся:

• Он использует карту (приятно функционирующую), но нуждается в изменяемой переменной (ringBufferIndex - BAD).

• Он работает на Seq[Double] (что нормально), но возвращает Seq[Double], что плохо, поскольку он требует от вызывающего абонента вызова .toList или чего-то еще, что он фактически использует. Я попытался использовать Generics здесь, как это:

  def filter\[T <% Seq[Double]](numbers: T, filterSize: Int): T

но это не скомпилируется.

У кого-нибудь есть предложения по улучшению этих двух проблем?

Answer 1

Если поиск по индексу представляет проблему ( O (n) с List), вы можете использовать постоянный вектор . Это дает вам O (1) индексирование, а также O (1) обновление. Он также чисто функциональный (неизменный), поэтому жизнь в этом отношении все еще счастлива.

Приложив немного воображения, мы можем преобразовать ваш код напрямую в чисто функциональную версию, используя Vector:

def filter(numbers: List[Double], size: Int) = {
  def walk(numbers: List[Double], buffer: Vector[Double], i: Int): List[Double] = {
    numbers match {
      case x :: tail => {
        val nextBuffer = buffer(i) = x
        val nextI = if (i == size) 0 else i + 1

        val avg = buffer.foldLeft(0.0) { _ + _ } / size
        avg :: walk(tail, nextBuffer, nextI)
      }

      case Nil => Nil
    }
  }

  walk(numbers, Vector.empty, 0)
}

Обратите внимание, что это не хвостовая рекурсия, поэтому он сломается, когда numbers будет слишком большим. Это довольно легко решить эту проблему, но я сейчас ленивый.

Answer 2

Чтобы ваш метод взял общий тип коллекции и возвратил тот же тип, я думаю, вам понадобятся типы с более высоким родом, как описано в статье Generics of the Higher Kind . К сожалению, текущая библиотека коллекций предшествует этой функции в Scala, но это будет исправлено для 2.8.

Answer 3

Хотя я не знаю Scala, я бы не использовал здесь кольцевой буфер. Насколько я понимаю, вы хотите взять среднее значение для каждой позиции массива предыдущих элементов filterSize. Итак, пройдитесь по массиву слева направо, сохраняя аккумулятор, содержащий сумму предыдущих элементов filterSize (на каждом шаге добавляя самый правый и вычитая самый левый) и получая accumulator/filterSize в качестве значения в этой позиции. Фактор filterSize меньше дополнений, и в принципе чисто функциональный. Это неудобно для кода в Scala?

(Если переполнение не является проблемой, я бы сделал кое-что более простое и более распараллеливаемое: вычислил бы промежуточную сумму всего массива (scanl (+) 0 numbers в Haskell) и вывел бы промежуточную сумму минус бегущая сумма, смещенная в позиции filterSize .)

Answer 4

ОК, так что я их немного почистил. Существует три функции для трех возможных типов данных (что автоматически решает проблему № 2). Я взял все это сверху (один для Array, один для List, один для Seq.):

def filter(numbers: Seq[Double], filterSize: Int): Seq[Double] = {
  require(filterSize > 0)
  val ringBuffer = new Array[Double](filterSize)
  var ringBufferIndex = 0

  numbers.map(x => {
    // update ring buffer
    ringBuffer(ringBufferIndex) = x

    // increase ring index
    ringBufferIndex += 1 
    if (ringBufferIndex == filterSize) {
      ringBufferIndex = 0
    }

    // get avarage
    ringBuffer.foldLeft(0.0)(_ + _) / filterSize
  })
}

def filter(numbers: Array[Double], filterSize: Int): Array[Double] = {
  require(filterSize > 0)
  (0 until numbers.length).map(x => {
    (((x - filterSize) max 0) to x).foldLeft(0.0)((sum, index) => sum + numbers(index)) / filterSize
  }).toArray
}

def filter(numbers: List[Double], filterSize: Int): List[Double] = {
  require(filterSize > 0)
  val ringBuffer = new Array[Double](filterSize)
  numbers.zipWithIndex.map(pair => {
    val (value, index) = pair
    // update ring buffer
    ringBuffer(index % filterSize) = value
    // get avarage
    ringBuffer.foldLeft(0.0)(_ + _) / filterSize
  })
}

Answer 5

Если входные данные могут быть списком, а не последовательностью, вы можете немного его очистить с помощью zipWithIndex:

def filter(numbers: List[Double], filterSize: Int): List[Double] = {
  require(filterSize > 0)
  val ringBuffer = new Array[Double](filterSize)
  numbers.zipWithIndex.map(pair => {
    // update ring buffer
    ringBuffer(pair._2 % filterSize) = pair._1
    // get avarage
    ringBuffer.foldLeft(0.0)(_ + _) / filterSize
  })
}

Обратите внимание, что возвращаемое значение теперь тоже List, и я заменил assert на require.

Answer 6

Вот более короткая версия, которую я придумала для решения первой проблемы:

  def filter(numbers: Seq[Double], filterSize: Int): Seq[Double] = {
    assert(filterSize > 0)
    (0 until numbers.length).map(x => {
      (((x - filterSize) max 0) to x).foldLeft(0.0)((sum, index) => sum + numbers(index)) / filterSize
    })
  }

Недостатком является поиск по индексу, который может быть очень плох для таких вещей, как «Список».