Scala中的有限可增長陣列

我希望能夠將一個類似數組的結構增大到最大尺寸，然後每當添加一個新元素時，最老的（第1個）元素將從結構中刪除。我不知道做這件事的最好方法是什麼，但一種方法是擴展ArrayBuffer類，並覆蓋+ =運算符，以便如果達到最大大小，則每當新的一個被添加。我還沒有想出如何正確擴展集合。我到目前爲止是：Scala中的有限可增長陣列

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

有人可以建議一個更好的路徑和/或幫助我沿着這一個嗎？注：我將需要在+ =操作之間多次訪問結構中的元素。

謝謝

來源

2011-03-22 Bruce Ferguson

聽起來[環形緩衝區（https://secure.wikimedia.org/wikipedia/en/wiki/Circular_buffer） – ziggystar 2011-03-22 12:37:43

@ziggystar。同意，聽起來像一個環形緩衝區可能會做的伎倆... – 2011-03-22 12:53:44

@ziggstar。 ...但是，這會給我O（1）訪問結構中的隨機元素，還是它更適合入隊/出隊類型處理？ – 2011-03-22 13:01:52

正如其他人所討論的，你需要一個環形緩衝區。但是，您還必須決定是否真的需要所有收集方法，如果是這樣，當您過濾最大尺寸爲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-22 15:02:18

謝謝，這真的很酷！ – 2011-03-22 16:47:53

Scala中的有限可增長陣列

回答

相關問題