就地连接数组

Question

我在实现必须偶尔对齐的循环缓冲区时遇到了一个问题。

假设我有两个数组，leftArr 和 rightArr。我想将右数组移动到 byteArr 并将左数组移动到 byteArr + 右数组的长度。 leftArr和rightArr都大于byteArr，rightArr大于leftArr . (这和rotating a circular buffer不太一样，因为左边的数组不需要从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;
}

Answer 1

想象一下将 byteArr 分成多个区域(不一定按比例缩放):

 X1    Left   X2  Right|---|--------|---|------|

X1 和X2 是左数组开始之前和两个数组之间的byteArr 中的间隙。在一般情况下，这四个区域中的任何一个或所有区域的长度都可能为零。

然后你可以这样继续:

1. 首先部分或全部填充 byteArr 中的前导空格
   • 如果 Left 的长度为零，则通过 memmove() 将 Right 移动到前面(如果需要)。完成。
   • 否则，如果 X1 与右数组的长度相同或更大，则通过 memcpy() 将右数组移动到该空间，并可能通过 向上移动左数组以邻接它>内存移动()。完成。
   • 否则，将 Right 数组的前导部分移动到该空间，生成以下布局。如果 X1 的长度为零，则 R1 的长度也为零，X2' == X2，并且 R2 == Right。

       R1    Left     X2'  R2      |---|--------|------|---|

1. 现在有两种选择

   • 如果 R2 与 Left 的长度相同或更长，则将 Left 与 R2 的初始部分交换以产生(仍然不按比例):

       R1'    X2''  Left    R2'      |------|-----|-------|--|

• 否则，将 Left 的初始部分与 R2 的所有部分交换以产生(仍然不按比例):

       R1'    L2  X2''    L1      |------|---|-------|----|

1. 现在认识到，在任何一种情况下，您都有一个与原始问题具有相同形式的严格更小的问题，其中新的 byteArr 是紧接在区域 R1' 之后开始的原始问题的尾部。在第一种情况下，新的 leftArr 是(最终的)Left 区域，而新的 rightArr 是区域 R2'。在另一种情况下，新的 leftArr 是区域 L2，新的 rightArr 是区域 L1。重置参数以反射(reflect)这个新问题，并循环回到步骤 (1)。

请注意，我说的是循环回到第 1 步。当然，您可以(尾)递归地实现此算法，但是为了实现恒定的空间使用率，您需要依赖您的编译器优化尾递归，否则尾递归会消耗与两个子数组中较大的子数组与较小的子数组的长度比成比例的辅助空间。