我将一个高效的循环缓冲区 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)
}
最佳答案
有两种可能的方法:
重新排序内容以适应新模数
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
我不确定您是否要跟踪缓冲区曾经存储的所有元素的数量,如果是,那么第二种方法当然行不通。第一种方法,重新排序,应该不会太麻烦,因为无论如何您都需要将内容从旧数组复制到新数组中。
关于algorithm - 将循环缓冲区复制到更大的缓冲区,同时保留内容和模数索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38134091/