如何使这个更有效率？（在C语言中合并数组）

Question

该程序旨在合并两个数组并将它们放入一个输出数组中。我所拥有的代码如下：

void Merge(int *arr1, int *arr2, int *output, int arr1size, int arr2size) { 
   int arr2count = 0, arr1count = 0;                                        
   while (arr1count < arr1size) {                                           
      if (arr2count >= arr2size) {   /* dump arr1 because arr2 is done */                                         
         *output++ = *arr1++;                                               
         arr1count++;                                                       
      }                                                                     
      else if (*arr1 < *arr2) {                                             
         *output++ = *arr1++;                                               
         arr1count++;                                                       
      }                                                                     
      else {                                                                
         *output++ = *arr2++;                                               
         arr2count++;                                                       
      }                                                                     
   }                                                                        
   while (arr2count++ < arr2size) {    /* dump arr2 */                                     
      *output++ = *arr2++;                                                  
   }                                                                        
}

如何使这个更有效率？我的意思是，尽可能地削减代码以使其稍微更有效率。

举例来说，可以考虑下面所示的三重 while 循环实现方式不够高效。

while (arr1count < arr1size && arr2count < arr2size) { .... }
while (arr1count < arr1size) { .... }
while (arr2count < arr2size) { .... }

此外，必须使用指针符号而不是数组符号（我希望...）

- Cole Twitchell

---

“这必须使用指针符号”是什么意思？它的含义是什么，这个限制从哪里来？为了更好的性能，考虑添加 restrict 关键字，让编译器知道 arr1, arr2 和 output 三个数组不会相互重叠。 - fuz

所有其他优化此代码的尝试都严重依赖于您所期望的数据范围、您使用的编译器以及此代码所运行的平台。 - fuz

那你为什么不能使用那种表示法呢？还有其他限制我需要知道吗？你是在哪个编译器和平台上进行编程的？请尝试回答我第二条评论中的问题。 - fuz

在这种情况下，我无法帮助您。没有足够的已知参数来进行优化。任何一个体面的编译器都能更好地优化第二个变量（要评估的条件表达式较少），所以有些事情似乎不对劲。如果需要更通用的帮助，请尝试第二个变量，并将后两个“while”循环更改为“memcpy”调用，因为即使在糟糕的平台上，“memcpy”通常也会被优化得很好。 - fuz

请问您能提供一些样例输入和输出吗？ - Schwern

Answer 1

我尝试去掉变量和增量。需要注意的是这些都是微小的改进，而算法仍然需要O(m+n)的时间。

编辑：根据user2048454的建议，加入了循环中断。

编辑2：去掉了两个while循环，并用memcpy替换。感谢FUZxxl。

void Merge2(int *arr1, int *arr2, int *output, int *a1last, int *a2last) { 
   while (arr1 < a1last && arr2 < a2last) {
      if (*arr1 < *arr2) {                                             
         *output++ = *arr1++;                                                
      }                                                                     
      else {                                                                
         *output++ = *arr2++;                                               
      }                                                                     
   }                  
   /* Replaced while with memcpy () */
   memcpy(output,arr1,sizeof(int)*(a1last-arr1));
   memcpy(output,arr2,sizeof(int)*(a2last-arr2));                                                  
   }                                                                        
}

int main()
{
    int a[]={1,3,5,7};
    int b[]={2,4,6,8};
    int c[10];
    int i;
    Merge2(a,b,c,&a[4],&b[4]); //&a[4] points to the end address of the array. Do not access value at that address, it is "out of bounds"

    for(i=0; i<8; i++)
        printf("%d ",c[i]);

    printf("\n");

    return 0;
}

- Erobrere

---

任何提高效率的方法都比没有好。感谢您的建议！我从未想过使用memcpy()。 - Cole Twitchell

Answer 2

像这样的东西？

void Merge(int *arr1, int *arr2, int *output, int arr1size, int arr2size) {
  for (int i=0,i1=0,i2=0; i<arr1size+arr2size; i++) {
    if      (i1==arr1size) *output++ = *arr2++;
    else if (i2==arr2size) *output++ = *arr1++;
    else if (*arr1<*arr2)  *output++ = *arr1++, i1++;
    else                   *output++ = *arr2++, i2++;
  }
}

- Jean-Baptiste Yunès

Answer 3

从上面的代码来看，数组最初是排序的，输出也应该包含排序后的值。

考虑到您提到的限制，一个想法是不使用arr1count/arr2count，而是使用arr1last/arr2last。

其中：

"arr1last=arr1+arr1size"和"arr2last=arr2+arr2size"

这样你就不必增加计数器，编译器会处理更少的变量(--*count --*size ++*last)，只需在arr1 < arr1last上进行比较。对于arr2也是一样。

此外，如果第一个if语句为真，则始终为真，因此根据您的数组大小，如果arr2size=1，arr1size=999，并且arr2[0]将成为“output”中的前几个值，则在那一点上退出并采用您提到的三重循环实现可能更值得，因为上述两个循环实现可能效率低下。

- Nicolae Natea