如何在斯卡拉

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太大。解決這個問題很容易，但我現在很懶惰。