就地连接数组

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中的空隙。在一般情况下，这四个区域中的任何一个或所有区域的长度可能为零。

然后您可以这样进行：

首先部分或全部填写 byteArr 中的前导 space
- 如果 Left 的长度为零，则通过 memmove() 将 Right 移到前面（如有必要）。完成。
- 否则，如果 X1 与右数组的长度相同或更大，则通过 memcpy() 将右数组移动到 space 中，并且可能向上移动左数组以通过 memmove()。完成。
- 否则，将 Right 数组的前导部分移动到 space 中，生成以下布局。如果 X1 的长度为零，则 R1 的长度也为零，X2' == X2，并且 R2 == Right。

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

现在有两个选择
- 如果 R2 与 Left 的长度相同或更长，则将 Left 与 R2 的初始部分交换以产生（仍未按比例）：

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

否则，将 Left 的初始部分与 R2 的所有部分交换以产生（仍未按比例）：

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

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

请注意，我说 loop 回到步骤 1。当然，您可以（尾）递归地实现此算法，但随后要实现常量 space 用法你需要依靠你的编译器来优化尾递归，否则会消耗辅助 space 与两个子数组中较大的子数组与较小的子数组的长度比成正比。

就地连接数组

Concatenating arrays in place

c

arrays

algorithm

buffer