scala - 如何用 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 - 不好)。

• 它的工作时间为 Seq[Double] (这很好)，但返回 Seq[Double] ，这是不好的，因为它需要调用者调用 .toList或他实际使用的任何东西。我尝试在这里使用泛型，如下所示:

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

但这不会编译。

有人对如何改善这两个问题有建议吗？

Answer 1

如果索引查找有问题(O(n) List)，您可以使用 a persistent vector 。这为您提供了 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)
}

请注意，这不是尾递归，因此当数字太大时它会崩溃。解决这个问题很容易，但我现在很懒。