7
\$\begingroup\$

For a set of 2D or 3D points \$\{\mathbf P_0, \mathbf P_1,\cdots,\mathbf P_n\}\$, their parameters \$\mathbf T = \{t_0,t_1,\cdots,t_n \}\$ could be computed as follow:

$$\begin{align} t_0&=0\\ t_i&=\frac{\sum_{j=1}^{i}||\mathbf P_j- \mathbf P_{j-1}||}{\sum_{j=1}^{n}||\mathbf P_j-\mathbf P_{j-1}||} \qquad i=1,2,\cdots,n \end{align}$$

Here is my C implementation:

/********************************************************************
         v1 = {v1(0),v1(1),...,v1(c-1)}  
         v2 = {v2(0),v2(1),...,v2(c-1)}
     compute the 2-norm of the difference of two vector v1 and v2
*********************************************************************/
double vector_norm(double *v1, double *v2, int c) {
    int i;
    double res = 0.0;
    for (i = 0; i < c; i++) {
        res += pow(v1[i] - v2[i], 2);
    }
    return sqrt(res);
}

/********************************************************
 In general, P is a matrix of dimensions {n + 1, c}
 here, it was saved as a vector
********************************************************/
void calc_paras(double *P, int n, int c, double *paras) {
    int i;
    double len = 0.0;
    double chord;
    //compute the length and total length
    paras[0] = 0.0;
    for (i = 0; i < n; i++) {
        chord = vector_norm(P + (i + 1) * c, P + i * c, c);
        len += chord;
        paras[i+1] = len;
    }
    //normalize the paras to [0,1]
    for (i = 0; i <= n; i++) {
        paras[i] /= len;
    }
}

Is a more efficient C implemetation of calc_paras() possible?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Is a more efficient C implementation of calc_paras() possible?

Some small ideas:

  1. Use const. A compiler may employ certain optimizations knowing the pointers are to const data.

    // double vector_norm(double *v1, double *v2, int c) {
    double vector_norm(const double *v1, const double *v2, int c) {
    
  2. If the pointers never overlap, let the compiler know that and allow it additional optimizations using restrict.

    // double vector_norm(double *v1, double *v2, int c) {
    double vector_norm(const double * restrict v1, const double * restrict v2, int c) {
    
  3. pow(x,2) is questionable. Profile against res += (v1[i] - v2[i])*(v1[i] - v2[i]);

  4. Unclear why code is using int vs. size_t to denote the size of a vector. size_t is more C-like.

  5. Minor. Might as well avoid the +1

    paras[0] = 0.0;
    for (i = 1; i <= n; i++) {
      chord = vector_norm(P + i*c, P + (i-1)* c, c);
      len += chord;
      paras[i] = len;
    }
    
  6. If vector_norm() is only meant as a helper function for calc_paras(), make vector_norm() static to un-clutter the name space.

\$\endgroup\$
7
  • \$\begingroup\$ Thanks a lot:) For a C newcomer, I would like to know why pow(x, 2) is questionable. Because pow() is a built-in of math.h library. \$\endgroup\$
    – xyz
    Aug 31, 2016 at 3:25
  • \$\begingroup\$ pow() is one of the most complex math functions. Rarely is pow(x,2) more efficient/more precise than simply x*x. I have doubts as to its relative value and speed. Like much minor optimizations, profile it on your target platforms. When in doubt, code to what provides the most clarity to a reviewer. \$\endgroup\$ Aug 31, 2016 at 3:28
  • \$\begingroup\$ In addtion, I discovered that the compiler gives the error when using keywords restrict. Here is snapshots \$\endgroup\$
    – xyz
    Aug 31, 2016 at 3:36
  • \$\begingroup\$ @Shutao Tang Use an up-to-date C11 compiler if you are interested in modern optimizations, else your code lives in the past. If obiged to use an old complier why look for a "more efficient C implementation"? \$\endgroup\$ Aug 31, 2016 at 3:38
  • \$\begingroup\$ As a side note for 5. Both temporaries are unecessary. If you zero-initialize paras[0], then the body of the for loop can be written as paras[i] = paras[i-1] +vector_norm(P + i * c, P + (i-1) * c, c); However, i assume the compiler would be able to optimize that away. Also the loop should stop at <n at leaast from the vector definition in the first code snipplet \$\endgroup\$
    – miscco
    Aug 31, 2016 at 4:55
2
\$\begingroup\$

That is basically the same technique that I would use.

My only suggestion is to consistently use

for (i = 1; i <= n; i++)

for both loops, to match the stated definition.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for your suggestion, I know for (int i = 1; i <= n; i++) is C99 style, but when I compile it via the CreateLibrary[]of Wolfram Mathematica, I discovered that it didn't support that style. \$\endgroup\$
    – xyz
    Aug 30, 2016 at 14:50
  • 1
    \$\begingroup\$ It's really sad that C99 still isn't supported in 2016! \$\endgroup\$ Aug 30, 2016 at 14:52
  • \$\begingroup\$ Maybe I don't know what option I should add in CreateLibrary[] to let the code be compiled with C99 style. :) \$\endgroup\$
    – xyz
    Aug 30, 2016 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.