连接阵列

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

• 如果左长度为零然后向右移动到前（如果需要）通过
  1. 开始：

     然后，可以继续进行这样memmove()。完成。

  2. 否则，如果X1与Right阵列的长度相同或更大，则通过memcpy()将右边的阵列移动到该空间中，并且可能通过memmove()向左移动阵列以对齐它。完成。
  3. 否则，将右数组的引导部分移动到该空间中，产生下面的布局。如果X1的长度为零，那么R1的长度也为零，X2'== X2和R2 == Right。

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

现在有两种选择

• 如果R 2是相同的长度左或更长，然后切换左侧与初始部分R2产生（仍未按比例）：

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

• 否则，切换左侧的所有R2的初始部分，以产生（仍然不按比例）：

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

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

注意，我要环回说步骤1.你可以，当然，实现这个算法（tail-）递归，但随后实现恒空间的使用，您将需要依靠你的编译器优化尾部递归，否则消耗辅助空间与两个子阵列中的较大者的长度比成比例。