如何在斯卡拉

Question

写一个很好的低通滤波器

我需要一个低通滤波器在我的斯卡拉项目之一，本想出了：

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

为了使您的方法采用泛型集合类型并返回相同类型，我相信您需要更高固定类型，如Generics of a Higher Kind论文中所述。不幸的是，当前的集合库在Scala中早于这个特性，但是这将被修正为2.8。

Answer 2

这里是一个较短的版本，我已经想出了解决的第一个问题：

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

它的缺点是索引查找这可能是像“名单”非常糟糕。

Answer 3

如果输入可以是一个列表，而不是序列，你可以用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 
    }) 
} 

注意，返回值也是现在列表和我换成需要断言。

Answer 4

好的，我把这些清理了一下。有三种可能的数据类型（自动解决问题2）的功能。我把所有的那些从上面（一个阵列，一个列表，其中起）：

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

虽然我不知道斯卡拉，我就不会在这里使用的环形缓冲区。据我所知，你想在每个数组位置取前面的filterSize元素的平均值。因此，从左到右通过数组，保留一个累加器来保存之前的filterSize元素的和（在每个步骤中添加最右边和最左边的减去）并产生accumulator/filterSize作为该位置的值。 filterSize的因子更少，并且原则上纯粹是功能性的。在Scala中编写代码不方便吗？ （如果溢出不是一个问题，我会做一些更简单和更可并行的操作：计算整个数组的运行总和（在Haskell中为scanl (+) 0 numbers），并生成运行总和减去运行总和移位的fi​​lterSize位置。 ）

Answer 6

如果索引查找是一个问题（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) 
} 

请注意，这并不是尾递归，所以它会分解时numbers太大。解决这个问题很容易，但我现在很懒惰。