我在实现循环缓冲区时遇到了一个问题,该缓冲区有时必须对齐。
说我有两个数组,leftArr
和rightArr
。我想将右边的数组移到byteArr
左边,并将左边的数组移到右边数组byteArr
的长度上。双方leftArr
并rightArr
都大于byteArr
和rightArr
大于leftArr
。(这与旋转循环缓冲区并不完全相同,因为左数组不需要从此处开始byteArr
)尽管左数组和右数组不重叠,但存储在的组合数组byteArr
可能与存储在leftArr
和的当前数组重叠rightArr
。可以安全地写入从byteArr
到的所有内存rightArr + rightArrLen
。一种可能的实现是:
void align(char* byteArr, char* leftArr, int leftArrLen, char* rightArr, int rightArrLen) {
char *t = malloc(rightArrLen + leftArrLen);
// form concatenated data
memcpy(t, right, rightArrLen);
memcpy(t + rightArrLen, left, leftArrLen);
// now replace
memcpy(byteArr, t, rightArrLen + leftArrLen);
free(t);
}
但是,我必须以恒定的内存复杂度来完成此操作。
我到目前为止所拥有的看起来像这样:
void align(char* byteArr, char* leftArr, int leftArrLen, char* rightArr, int rightArrLen)
{
// first I check to see if some combination of memmove and memcpy will suffice, if not:
unsigned int lStart = leftArr - byteArr;
unsigned int lEnd = lStart + leftArrLen;
unsigned int rStart = rightArr - byteArr;
unsigned int rEnd = rStart + rightArrLen;
unsigned int lShift = rEnd - rStart - lStart;
unsigned int rShift = -rStart;
char temp1;
char temp2;
unsigned int nextIndex;
bool alreadyMoved;
// move the right array
for( unsigned int i = 0; i < rEnd - rStart; i++ )
{
alreadyMoved = false;
for( unsigned int j = i; j < rEnd - rStart; j-= rShift )
{
if( lStart <= j + rStart - lShift
&& j + rStart - lShift < lEnd
&& lStart <= (j + rStart) % lShift
&& (j + rStart) % lShift < lEnd
&& (j + rStart) % lShift < i )
{
alreadyMoved = true;
}
}
if(alreadyMoved)
{
// byte has already been moved
continue;
}
nextIndex = i - rShift;
temp1 = byteArr[nextIndex];
while( rStart <= nextIndex && nextIndex < rEnd )
{
nextIndex += rShift;
temp2 = byteArr[nextIndex];
byteArr[nextIndex] = temp1;
temp1 = temp2;
while( lStart <= nextIndex && nextIndex < lEnd )
{
nextIndex += lShift;
temp2 = byteArr[nextIndex];
byteArr[nextIndex] = temp1;
temp1 = temp2;
}
if( nextIndex <= i - rShift )
{
// byte has already been moved
break;
}
}
}
// move the left array
for( unsigned int i = lStart; i < lShift && i < lEnd; i++ )
{
if( i >= rEnd - rStart )
{
nextIndex = i + lShift;
temp1 = byteArr[nextIndex];
byteArr[nextIndex] = byteArr[i];
while( nextIndex < lEnd )
{
nextIndex += lShift;
temp2 = byteArr[nextIndex];
byteArr[nextIndex] = temp1;
temp1 = temp2;
}
}
}
}
此代码在情况下有效,lStart = 0, lLength = 11, rStart = 26, rLength = 70
但在情况下失败lStart = 0, lLength = 46, rStart = 47, rLength = 53
。我可以看到的解决方案是添加逻辑以确定何时正确数组中的字节已被移动。尽管我可以做到这一点,但我想知道是否有一个针对此问题的更简单的解决方案,该解决方案以恒定的内存复杂性运行并且没有额外的读写操作?
这是一个测试实现的程序:
bool testAlign(int lStart, int lLength, int rStart, int rLength)
{
char* byteArr = (char*) malloc(100 * sizeof(char));
char* leftArr = byteArr + lStart;
char* rightArr = byteArr + rStart;
for(int i = 0; i < rLength; i++)
{
rightArr[i] = i;
}
for(int i = 0; i < lLength; i++)
{
leftArr[i] = i + rLength;
}
align(byteArr, leftArr, lLength, rightArr, rLength);
for(int i = 0; i < lLength + rLength; i++)
{
if(byteArr[i] != i) return false;
}
return true;
}
想象一下划分byteArr
为区域(不一定按比例):
X1左X2右 | --- | -------- | --- | ------ |
X1和X2是左数组开始之前和两个数组之间的byteArr中的间隙。在一般情况下,这四个区域中的任何一个或全部可以具有零长度。
然后,您可以像下面这样进行:
byteArr
memmove()
。做完了memcpy()
并可能通过向上移到left数组以邻接它memmove()
。做完了R1左X2'R2 | --- | -------- | ------ | --- ||
现在有两种选择
R1'X2''左R2' | ------ | ----- | ----------- |-|
R1'L2 X2''L1 | ------ | --- | ------- | ---- |
byteArr
是原始区域的尾部,紧接在区域R1'之后。在第一种情况下,新的leftArr
是(最终)左区域,新的rightArr
是区域R2'。在其他情况下,新的leftArr
是区域L2,新的rightArr
是区域L1。重置参数以反映此新问题,然后循环回到步骤(1)。请注意,我说要循环回到步骤1。您当然可以递归地实现此算法,但是要实现恒定的空间使用,您将需要依赖编译器来优化尾部递归,否则消耗的辅助空间与两个子阵列中的较大子阵列与较小子阵列的长度比例成比例。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句