c-数组元素似乎任意变化[并行快速排序/前缀和]

Question

所以我正在使用Cilk在C中实现并行快速排序，遇到了一个奇怪的问题。我的代码的相关部分，供参考（并提前为长度道歉）：

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#include <cilk/cilk.h>
#include <cilk/cilk_api.h>
void prefixSum(int* input,int* output, int length){
   if(length == 1){
      output[0] = input[0];
      return;
   }
   int i;
   int nPairs = (int) floor(((double)length)/2);
   int pairs = (int) ceil(((double)length)/2);
   int z[pairs];
   int w[pairs];
   cilk_for(i=0;i<nPairs;i++){
      z[i] = input[2*i]+input[2*i+1];
   }
   if(pairs>nPairs){
      z[pairs-1] = input[length-1];
   }
   prefixSum(z,w,pairs);
   cilk_for(i=0;i<length;i++){
      if(i==0){
         output[i] = input[i];
      } 
      else if((i-1)%2==0){
         output[i] = w[(i-1)/2];
      }
      else{
         output[i] = w[(i-2)/2] + input[i];
      }
   }
   return;
}
void prefixScan(int* input, int length){
   int i;
   for(i=length-1;i>0;i--){
      input[i] = input[i-1];
   }
   input[0] = 0;
}
void paraSort(double* array, int length){
   if(length==1){
      return;
   }
   int pivot = rand() % length;
   int lowSet[length];
   int highSet[length];
   int equalSet[length];
   int i;
   cilk_for(i=0;i<length;i++){
      if(array[i]==array[pivot]){
         lowSet[i] = 0;
         highSet[i] = 0;
         equalSet[i] = 1;
      } else if(array[i]<array[pivot]){
         lowSet[i] = 1;
         highSet[i] = 0;
         equalSet[i] = 0;
      } else {
         lowSet[i] = 0;
         highSet[i] = 1;
         equalSet[i] = 0;
      }
   }
   int lowIndex[length];
   int highIndex[length];
   int equalIndex[length];
   prefixSum(lowSet,lowIndex,length);
   int numLow = lowIndex[length-1];
   prefixScan(lowIndex,length);
   prefixSum(highSet,highIndex,length);
   int numHigh = highIndex[length-1];
   prefixScan(highIndex,length);
   prefixSum(equalSet,equalIndex,length);
   int numEqual = equalIndex[length-1];
   prefixScan(equalIndex,length);
   double lowList[imin(numLow,1)];
   double highList[imin(numHigh,1)];
   double equalList[numEqual];
   cilk_for(i=0;i<length;i++){
      if(lowSet[i]==1){
         lowList[lowIndex[i]] = array[i];
      } else if(highSet[i]==1){ 
         highList[highIndex[i]] = array[i];
      } else if(equalSet[i]==1){
         equalList[equalIndex[i]] = array[i];
      }
   }
   if(numLow>0 && numHigh>0){
      cilk_spawn paraSort(lowList,numLow);
      paraSort(highList,numHigh);
      cilk_sync;
   } else if(numLow==0 && numHigh>0){
      paraSort(highList,numHigh);
   } else if(numLow>0 && numHigh==0){
      paraSort(lowList,numLow);
   }
   cilk_for(i=0;i<length;i++){
      if(i<numLow){
         array[i] = lowList[i];
      } else if(i<numLow+numEqual){
         array[i] = equalList[i-numLow];
      } else {
         array[i] = highList[i-(numLow+numEqual)];
      }
   }
   return;
}

现在，当我在一个有50个元素的测试用例上运行这个程序时（为了便于调试，按顺序），我深入递归一层，然后遇到一个分段错误，它似乎是由equalList[equalIndex[i]] = array[i];行中的越界索引引起的。

进一步检查，在分配equalIndex之后，它中的值是完全任意的。这是意料之中的事；我还没有分配任何东西。prefixSum是在一个元素列表上调用的，该列表除了倒数第二个元素为1之外，其余元素均为零。（这是一个位图，将元素标记为等于pivot。）它将前缀和运算的结果放入equalIndex中，我将其作为指向数组的指针传入，以便结果在调用之外持久存在。

完成此操作后，调试printf命令显示，除了最后两个元素外，equalIndex现在都是零，这两个元素都是一个。这是预期的前缀和结果；到目前为止还不错。prefixScan是一个简单的帮助函数，可以帮助我处理从零开始的索引；它将给定数组中的所有元素向右移动一个空间，用零填充第一个元素。在将equalIndex传递给它之后，调试语句显示equalIndex除了最后一个元素是一之外都是零。

问题出现的地方紧随其后，在cilk_for循环中，该循环将每个元素复制到其适当的数组中。在这个循环的主体中，printf语句现在显示的值与以前的值一点也不匹配——有些是零，有些是我之前用prefixSum初始化这个数组之前看到的那种非常大的正整数或负整数。一旦它达到其中一个极值并试图将其用作数组索引，程序就会崩溃。

我的最佳猜测是，不知何故，equalIndex中的值没有正确分配（因此出现了奇怪的行为，就好像我没有初始化数组一样），但我很难弄清楚到底出了什么问题以及哪里出了问题。

Answer 1

你自相矛盾。有一次你说

equalIndex是除最后一个元素外的所有零，该元素是一个

但后来你推测

不知何故，equalIndex中的值没有正确分配

你不能两全其美。

我不知道Cilk，但从C中推断，我倾向于认为你在破坏自己的数据。特别考虑一下这个代码，它似乎是问题的根源：

double lowList[imin(numLow,1)];
double highList[imin(numHigh,1)];
double equalList[numEqual];
cilk_for(i=0;i<length;i++){
    if(lowSet[i]==1){
       lowList[lowIndex[i]] = array[i];
    } else if(highSet[i]==1){ 
       highList[highIndex[i]] = array[i];
    } else if(equalSet[i]==1){
       equalList[equalIndex[i]] = array[i];
    }
}

阵列lowList和highList有多长？在回答之前先研究一下他们的声明。现在，如果您试图将值分配给超出其边界的数组元素，您会认为会发生什么？