0

我有一个大的二维数组，array[length][2]. length= 500000. _

在array[i][0]= hex number, array[i][1]= 0或1中, 表示与每个十六进制数相关的一些信息。像这样：

array[i][0]    array[i][1]

e05f56f8           1

e045ac44           1

e05f57fc           1

e05f57b4           1

e05ff8dc           0

e05ff8ec           0

e05ff900           1

我想得到一个新的数组，它存储：十六进制数、出现次数、相同十六进制数的数组 [i] [1] 的总和。

我这样写代码：

//First Sort the array according to array[][0]

int x,y,temp1,temp2;
  for (x=lines_num1-2;x>=0;x--)
    {
      for (y=0;y<=x;y++)
       {
        if(array[y][0]>array[y+1][0])
         {
            temp1=array[y][0];
            array[y][0]=array[y+1][0];
            array[y+1][0]=temp1;

            temp2=array[y][1];
            array[y][1]=array[y+1][1];
            array[y+1][1]=temp2;                
          }
       }
   }

// generate the new_array[][]
int new_array[length][3];
int n=0;
for (n=0; n<length; n++){
   new_array[n][0]=0;
   new_array[n][1]=0;
   new_array[n][2]=0;
}
int prev = array[0][0];
new_array[0][0]=array[0][0];
new_array[0][1]=1;
new_array[0][2]=array[0][2];
for (k=1;k<length;k++)
  {
     if (array[k][0] == prev)
       {
         new_array[n][1]=new_array[n][1]+1;
         new_array[n][2]=new_array[n][2]+array[k][0];
       }else{
         prev = array[k][0];
         new_array[n+1][0]=array[k][0];
         new_array[n+1][1]=new_array[n+1][1]+1;
         new_array[n+1][2]=new_array[n+1][2]+array[k][0];
         n++;
       }
   }

但代码似乎不像我预期的那样工作。首先排序太慢了。而且似乎无法生成正确的 new_array。有关如何处理此问题的任何建议。

4

3 回答 3

0

就个人而言，我会编写一个哈希函数来直接用十六进制值索引结果数组。然后很简单：

struct {
    unsigned int nocc;
    unsigned int nsum;
} result[/* ... */];

/* calculate the results */
for (i = 0; i < LENGTH; ++i) {
    int *curr = &array[i];
    unsigned int index = hash(curr[0]);    

    result[index].nocc++;
    result[index].nsum += curr[1];
}

如果要对数组进行排序，请不要重新发明轮子：使用qsort标准 C 库。

于 2012-11-05T17:59:20.863 回答
0

排序很慢，因为您使用冒泡排序对数据进行排序。冒泡排序具有二次平均复杂度，这意味着它必须执行超过 1000 亿次比较和交换才能对数组进行排序。因此，永远不要使用冒泡排序。相反，学习使用qsort库函数并将其应用于您的问题。

此外，您的排序代码至少有一个错误：在为数组的第二列交换值时，您得到的值是错误的列索引，[3]而不是[1].

于 2012-11-05T18:01:15.940 回答
0

对于您的场景，插入排序是正确的解决方案，在进行插入本身时，您可以进行 #count 和总和。排序完成后，您也将获得结果数组。

代码可能看起来像这样

int hex = 0, count = 0, sum = 0, iHole;
for (i=1; i < lines_num1 -1; i++)
{
     hex = array[i][0];
     count = array[i][1];
     sum = array[i][2];

     iHole = i
     // keep moving the hole to next smaller index until A[iHole - 1] is <= item
     while (iHole > 0 and array[iHole - 1][0] > hex)
       {
         // move hole to next smaller index
         A[iHole][0] = A[iHole - 1][0];
         A[iHole][1] = A[iHole - 1][1];
         A[iHole][2] = A[iHole - 1][2];
         iHole = iHole - 1
       }
     // put item in the hole
      if (array[iHole][0] == hex) 
      {
        array[iHole][1]++;
        array[iHole][2] += array[iHole][0];
       }
      else 
      {
        array[iHole][0]  = hex;
        array[iHole][1]  = 1;
        array[iHole][2]  = hex;
      }

   }

所以制作第二个数组的成本就是排序本身的成本。O(n) 最好的情况，O(n^2) 最坏的情况，你不必再次旅行来求和和计数。

请记住，这种排序是就地排序。如果您不想影响原始数组，也可以使用指向新数组的 iHole 来完成。iHole 应该指向新数组的尾部而不是“i”

于 2012-11-05T18:06:37.750 回答