2

配列のような構造を最大サイズまで拡大できるようにしたいと考えています。その後、新しい要素が追加されるたびに、最も古い (1 番目の) 要素が構造から削除されます。これを行う最善の方法はわかりませんが、1 つの方法は ArrayBuffer クラスを拡張し、+= 演算子をオーバーライドして、最大サイズに達した場合に新しい要素が毎回削除されるようにすることです。 1 つ追加されます。コレクションを適切に拡張する方法がまだわかりません。私がこれまでに持っているものは次のとおりです。

class FiniteGrowableArray[A](maxLength:Int) extends scala.collection.mutable.ArrayBuffer {
    override def +=(elem:A): <insert some return type here> = {
        // append element
        if(length > maxLength) remove(0)
        <returned collection>
    }
}

誰かがより良い道を提案したり、これに沿って私を助けたりできますか? 注: += 操作の合間に、構造内の要素に何度も任意にアクセスする必要があります。

ありがとう

4

1 に答える 1

5

他の人が議論したように、リング バッファーが必要です。ただし、実際にすべてのコレクション メソッドが必要かどうかも判断する必要があります。必要な場合は、最大サイズ N のリング バッファーをフィルター処理するとどうなりますか?最大サイズを保持しますか?

リング バッファーをコレクション階層の一部として表示するだけで問題ない場合(ただし、コレクションを効率的に使用して新しいリング バッファーを生成したくない場合)、次のことができます。

class RingBuffer[T: ClassManifest](maxsize: Int) {
  private[this] val buffer = new Array[T](maxsize+1)
  private[this] var i0,i1 = 0
  private[this] def i0up = { i0 += 1; if (i0>=buffer.length) i0 -= buffer.length }
  private[this] def i0dn = { i0 -= 1; if (i0<0) i0 += buffer.length }
  private[this] def i1up = { i1 += 1; if (i1>=buffer.length) i1 -= buffer.length }
  private[this] def i1dn = { i1 -= 1; if (i1<0) i1 += buffer.length }   
  private[this] def me = this

  def apply(i: Int) = {
    val j = i+i0
    if (j >= buffer.length) buffer(j-buffer.length) else buffer(j)
  }
  def size = if (i1<i0) buffer.length+i1-i0 else i1-i0
  def :+(t: T) = {
    buffer(i1) = t
    i1up; if (i1==i0) i0up
    this
  }
  def +:(t: T) = {
    i0dn; if (i0==i1) i1dn
    buffer(i0) = t
    this
  }
  def popt = {
    if (i1==i0) throw new java.util.NoSuchElementException
    i1dn; buffer(i1)
  }
  def poph = {
    if (i1==i0) throw new java.util.NoSuchElementException
    val ans = buffer(i0); i0up; ans
  }
  def seqView = new IndexedSeq[T] {
    def apply(i: Int) = me(i)
    def length = me.size
  }
}

これを簡単に直接使用できるようになり、必要に応じて IndexedSeq に飛び出すことができます。

val r = new RingBuffer[Int](4)
r :+ 7 :+ 9 :+ 2
r.seqView.mkString(" ")    // Prints 7 9 2
r.popt                     // Returns 2
r.poph                     // Returns 7
r :+ 6 :+ 5 :+ 4 :+ 3
r.seqView.mkString(" ")    // Prints 6 5 4 3 -- 7 fell off the end
0 +: 1 +: 2 +: r
r.seqView.mkString(" ")    // Prints 0 1 2 6 -- added to front; 3,4,5 fell off
r.seqView.filter(_>1)      // Vector(2,6)

物事をリングバッファに戻したい場合は、次のことができます

class RingBufferImplicit[T: ClassManifest](ts: Traversable[T]) {
  def ring(maxsize: Int) = {
    val rb = new RingBuffer[T](maxsize)
    ts.foreach(rb :+ _)
    rb
  }
}
implicit def traversable2ringbuffer[T: ClassManifest](ts: Traversable[T]) = {
  new RingBufferImplicit(ts)
}

そして、次のようなことができます

val rr = List(1,2,3,4,5).ring(4)
rr.seqView.mkString(" ")            // Prints 2,3,4,5
于 2011-03-22T15:02:18.997 に答える