串联数组

音农桑德斯

我在实现循环缓冲区时遇到了一个问题,该缓冲区有时必须对齐。

说我有两个数组,leftArrrightArr我想将右边的数组移到byteArr左边,并将左边的数组移到右边数组byteArr的长度上。双方leftArrrightArr都大于byteArrrightArr大于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中的间隙。在一般情况下,这四个区域中的任何一个或全部可以具有零长度。

然后,您可以像下面这样进行:

  1. 首先部分或全部填充 byteArr
    • 如果Left的长度为零,则通过将Right移到前面(如有必要)memmove()做完了
    • 否则,如果X1与Right数组的长度相同或更大,则通过将Right数组移到该空间中,memcpy()并可能通过向上移到left数组以邻接它memmove()做完了
    • 否则,将Right数组的引导部分移到该空间中,从而产生以下布局。如果X1的长度为零,则R1的长度也为零,X2'== X2,R2 ==右。
       R1左X2'R2 
      | --- | -------- | ------ | --- ||
  1. 现在有两种选择

    • 如果R2与Left的长度相同或更长,则将Left与R2的初始部分交换以产生(仍然不按比例缩放):
       R1'X2''左R2' 
      | ------ | ----- | ----------- |-|
  • 否则,将Left的初始部分与所有R2交换以产生(仍然不按比例缩放):
       R1'L2 X2''L1 
      | ------ | --- | ------- | ---- |
  1. 现在认识到,无论哪种情况,都存在与原始形式相同的严格较小的问题,其中新的byteArr是原始区域的尾部,紧接在区域R1'之后。在第一种情况下,新的leftArr是(最终)左区域,新的rightArr是区域R2'。在其他情况下,新的leftArr是区域L2,新的rightArr是区域L1。重置参数以反映此新问题,然后循环回到步骤(1)。

请注意,我说要循环回到步骤1。您当然可以递归地实现此算法,但是要实现恒定的空间使用,您将需要依赖编译器来优化尾部递归,否则消耗的辅助空间与两个子阵列中的较大子阵列与较小子阵列的长度比例成比例。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章