algorithm - 将循环缓冲区复制到更大的缓冲区，同时保留内容和模数索引

Question

我将一个高效的循环缓冲区 buf 保存为一个数组和两个总的读写计数 bufRead 和 bufWrite 这样 bufRead % buf.length 和 bufWrite % buf.length 是当前操作缓冲区的正确索引。

现在我可能需要在某个时候“增加”数组，因为缓冲区大小扩大了。所以我想用一个更大的新数组替换 buf，但保留缓冲区中所有以前的内容同时保留上述模数属性。因此，如果在旧缓冲区中的 bufRead % buf.length 处我们找到元素 X，那么我希望再次找到该元素 X buf 更新后相同的索引 bufRead % buf.length。

例子:

trait Algorithm {
  var buf: Array[Double]
  var bufRead : Long  // this won't be needed in `resize`
  var bufWrite: Long  // this won't be needed in `resize`

  def resize(newLength: Int): Unit = {
    val newBuf = new Array[Double](newLength)
    ???
    buf = newBuf
  }
}

测试程序:

def test(in: Algorithm): Unit = {
  import in._
  import math.{min, random}
  val avail  = buf.length // (bufWrite - bufRead).toInt
  val data0  = Array.fill(avail)(random)
  val off0   = (bufRead % buf.length).toInt
  val chunk0 = min(avail, buf.length - off0)  
  val off1   = (off0 + chunk0) % buf.length
  val chunk1 = avail - chunk0

  System.arraycopy(data0, 0     , buf, off0, chunk0)
  System.arraycopy(data0, chunk0, buf, off1, chunk1)

  resize(avail * 2)  // arbitrary growth

  val data1  = new Array[Double](avail)
  val off2   = (bufRead % buf.length).toInt
  val chunk2 = min(avail, buf.length - off2)
  val off3   = (off2 + chunk2) % buf.length
  val chunk3 = avail - chunk2
  System.arraycopy(buf, off2, data1, 0     , chunk2)
  System.arraycopy(buf, off3, data1, chunk2, chunk3)

  assert(data0 sameElements data1)
}

Answer 1

有两种可能的方法:

• 重新排序内容以适应新模数

  for (i <- bufRead until bufWrite) {
      newBuf(i % newBuf.length) = buf(i % buf.length)
  }
  

• 重置read 和write 指针以适应新数组

  var j = 0
  for (i <- bufRead until bufWrite) {
      newBuf(j) = buf(i % buf.length)
      j += 1
  }
  bufWrite -= bufRead
  bufRead = 0
  

我不确定您是否要跟踪缓冲区曾经存储的所有元素的数量，如果是，那么第二种方法当然行不通。第一种方法，重新排序，应该不会太麻烦，因为无论如何您都需要将内容从旧数组复制到新数组中。