如何在C++中快速計算矢量的歸一化l1和l2範數？

我有一個矩陣X有n列數據向量在d維空間。給定一個矢量XJ，v [j]的是其L1範數（所有ABS（XJI的總和）），W [j]的是其L2範數的平方（在所有XJI^2），和PJ [I]的總和是通過L1和L2範數劃分條目的組合。最後，我需要輸出：pj，v，w for subsequet應用程序。如何在C++中快速計算矢量的歸一化l1和l2範數？

// X = new double [d*n]; is the input. 
double alpha = 0.5; 
double *pj = new double[d]; 
double *x_abs = new double[d]; 
double *x_2 = new double[d]; 
double *v = new double[n](); 
double *w = new double[n](); 
for (unsigned long j=0; j<n; ++j) { 
     jm = j*m; 
     jd = j*d; 
     for (unsigned long i=0; i<d; ++i) { 
      x_abs[i] = abs(X[i+jd]); 
      v[j] += x_abs[i]; 
      x_2[i] = x_abs[i]*x_abs[i]; 
      w[j] += x_2[i];  
     } 
     for (unsigned long i=0; i<d; ++i){ 
      pj[i] = alpha*x_abs[i]/v[j]+(1-alpha)*x_2[i]/w[j];  
     } 

    // functionA(pj){ ... ...} for subsequent applications 
} 
// functionB(v, w){ ... ...} for subsequent applications

我上面的算法需要O（ND）拖/時間的複雜性，任何一個可以幫助我通過使用建築functoin或新的實現在C++加快呢？減少O（nd）中的常數值對我也很有幫助。

來源

2016-12-30 olivia

是不是內存分配的瓶頸？你不能將預分配的數組傳遞給函數嗎？ – Bathsheba

你可以嘗試在第二個循環外計算'a = alpha/v [j]'和'b =（1-alpha）/ w [j]'然後計算'pj [i] = a * x_abs [i] + b * x_2 [i];'而是。然而，編譯器可能已經爲你做了這種優化，並且由於浮點錯誤，結果可能會稍微有所不同 – samgak

@Bathsheba我對內存使用沒有限制。請繼續。謝謝。 – olivia

讓我猜測：既然你有與性能相關的問題，你的向量的維度是相當大的。
如果是這樣的話，那麼它值得考慮「CPU緩存局部性」 - 關於這個in a cppcon14 presentation的一些有趣的信息。
如果數據在CPU高速緩存中不可用，那麼在CPU剛剛等待數據之前，一旦可用，將其平方化即可。

有了這一點，你可能想嘗試以下解決方案（沒有保證，這將提高性能 - 編譯器優化代碼時，可以實際應用這些技術）

for (unsigned long j=0; j<n; ++j) { 
     // use pointer arithmetic - at > -O0 the compiler will do it anyway 
     double *start=X+j*d, *end=X+(j+1)*d; 

     // this part avoid as much as possible the competition 
     // on CPU caches between X and v/w. 
     // Don't store the norms in v/w as yet, keep them in registers 
     double l1norm=0, l2norm=0; 
     for(double *src=start; src!=end; src++) { 
      double val=*src; 
      l1norm+=abs(src); 
      l2norm+= src*src; 
     } 
     double pl1=alpha/l1norm, pl2=(1-alpha)*l2norm; 
     for(double *src=start, *dst=pj; src!=end; src++, dst++) { 
      // Yes, recomputing abs/sqr may actually save time by not 
      // creating competition on CPU caches with x_abs and x_2 
      double val=*src; 
      *dst = pl1*abs(val) + pl2*val*val; 
     }  
     // functionA(pj){ ... ...} for subsequent applications 

     // Think well if you really need v/w. If you really do, 
     // at least there are two values to be sent for storage into memory, 
     //meanwhile the CPU can actually load the next vector into cache 
     v[j]=l1norm; w[j]=l2norm; 
} 
// functionB(v, w){ ... ...} for subsequent applications

來源

2016-12-30 12:15:12

如何在C++中快速計算矢量的歸一化l1和l2範數？

回答

相關問題