3

我在我的一个 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
  })
}

但是，有一些我不喜欢它的地方：

  • 它使用 map（功能很好），但需要一个可变变量（ringBufferIndex - BAD）。

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

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

但这不会编译。

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

4

6 回答 6

3

如果索引查找有问题（O(n) with 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请注意，这不是尾递归，因此当太大时它会崩溃。解决这个问题很容易，但我现在很懒。

于 2009-01-25T03:08:43.447 回答
2

要让您的方法采用泛型集合类型并返回相同的类型，我相信您需要更高种类的类型，如更高种类的泛型论文中所述。不幸的是，当前的集合库早于 Scala 中的此功能，但这将在 2.8 中得到纠正。

于 2009-01-26T14:52:30.117 回答
1

如果输入可以是 List 而不是 Seq，则可以使用 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。

于 2009-01-24T17:15:43.113 回答
1

好的，所以我清理了一些。三种可能的数据类型有三个函数（自动解决问题#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
  })
}
于 2009-01-24T17:51:52.447 回答
1

虽然我不了解 Scala，但我不会在这里使用环形缓冲区。据我了解，您希望在每个数组位置取前面 filterSize 元素的平均值。因此，从左到右遍历数组，保持一个累加器保存先前 filterSize 元素的总和（在每个步骤中添加最右边的元素并减去最左边的元素）并accumulator/filterSize作为该位置的值产生。一个因素 filterSize 的添加更少，而且原则上纯粹是功能性的。在 Scala 中编写代码不方便吗？

（如果溢出不是问题，我会做一些更简单和更可并行化的事情：计算整个数组的运行总和（scanl (+) 0 numbers在 Haskell 中）并产生运行总和减去运行总和置换 filterSize 位置。）

于 2009-01-24T18:58:35.653 回答
0

这是我为解决第一个问题而提出的较短版本：

  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
    })
  }

它的缺点是索引查找对于“列表”之类的东西可能非常糟糕。

于 2009-01-24T17:12:35.257 回答