查找數組中每個元素的出現次數並更新與每個元素相關的信息

我有一個很大的二維數組，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。任何有關如何處理這個問題的建議。

來源

2012-11-05 user1510866

就我個人而言，我會寫一個散列函數來直接爲十六進制值的結果數組建立索引。那麼很簡單：

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-05 17:59:20 md5

結果是什麼[/ * ... * /]是什麼意思？ – user1510866

散列C中的lib函數嗎？或者我需要自己寫一個散列函數？ – user1510866

你需要自己寫一個。這取決於你的目標是什麼（碰撞等）。註釋表示'result'數組的大小。 – md5

排序很慢，因爲您使用冒泡排序來排序數據。泡泡排序具有二次平均複雜度，這意味着它必須執行超過1000億次的比較和交換來對陣列進行排序。爲此，never use bubble sort。相反，學會使用qsort庫函數並將其應用於您的問題。

此外，您的排序代碼至少有一個錯誤：當交換數組第二列的值時，您將得到具有錯誤列索引[3]而不是[1]的值。

來源

2012-11-05 18:01:15 user4815162342

[3]是打字錯誤，已經解決了。 – user1510866

對於您的場景插入排序是正確的解決方案，同時做插入本身，你可以使#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應該指向新陣列的尾部而不是「我」

來源

2012-11-05 18:06:37 kalyan

查找數組中每個元素的出現次數並更新與每個元素相關的信息

回答

相關問題