0

大きな 2 次元配列 がありarray[length][2]ます。length= 500000。_

、またはでarray[i][0]= hex number、 各 16 進数に関連する情報を表します。このような：array[i][1]= 01

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

e05f56f8           1

e045ac44           1

e05f57fc           1

e05f57b4           1

e05ff8dc           0

e05ff8ec           0

e05ff900           1

格納する新しい配列を取得したい: 16 進数、出現回数、同じ 16 進数の配列 [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

個人的には、結果の配列に16進値で直接インデックスを付けるハッシュ関数を記述します。次に、それは簡単です：

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

バブルソートを使用してデータをソートしているため、ソートは遅くなります。バブルソートの平均の複雑さは2次式です。つまり、配列をソートするには、1,000億を超える比較とスワップを実行する必要があります。このため、バブルソートは絶対に使用しないでください。代わりに、qsortライブラリ関数の使用方法を学び、それを問題に適用してください。

Also, your sorting code has at least one bug: when exchanging values for the second column of the array, you are getting the value with the wrong column index, [3] instead of [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;
      }

   }

したがって、2 番目の配列を作成するコストは、並べ替え自体のコストです。O(n) が最良のケース、O(n^2) が最悪のケースであり、合計とカウントを行うために再度移動する必要はありません。

この並べ替えはインプレース並べ替えであることを忘れないでください。元の配列に影響を与えたくない場合は、新しい配列を指す iHole を使用して行うこともできます。iHole は、「i」ではなく新しい配列の末尾を指す必要があります

于 2012-11-05T18:06:37.750 に答える