3

Scala プロジェクトの 1 つで Low-Pass-Filter が必要だったので、次のように思いつきました。

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

しかし、それはコンパイルされません。

これら2つの問題を改善する方法を提案する人はいますか?

4

6 に答える 6

3

インデックス ルックアップが問題 ( O(n) with ) である場合は、persistent vectorListを使用できます。これにより、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

Scalaはわかりませんが、ここではリングバッファを使用しません。私が理解しているように、各配列位置で、先行するfilterSize要素の平均を取りたいと思います。したがって、配列を左から右に調べ、前のfilterSize要素の合計を保持するアキュムレータを保持し（各ステップで右端を加算し、左端を減算します）accumulator/filterSize、その位置の値として生成します。filterSizeの係数は追加が少なく、原則として純粋関数型です。Scalaでコーディングするのは不便ですか？

（オーバーフローが問題にならない場合は、もう少し単純で並列化可能な方法を実行します。配列全体の現在の合計を計算し（scanl (+) 0 numbersHaskellで）、現在の合計から現在の合計が置き換えられたfilterSizeの位置を差し引いたものを生成します。）

于 2009-01-24T18:58:35.653 に答える
1

入力が Seq ではなく List である可能性がある場合は、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

わかりましたので、それらを少しきれいにしました。3 つの可能なデータ型に対して 3 つの関数があります (問題 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
  })
}
于 2009-01-24T17:51:52.447 に答える
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 に答える