c++ notes

Tools‎ > ‎

Defining 1D, 2D and 3D vectors

typedef vector<float> float_1D;
typedef vector<vector<float>> float_2D;
typedef vector<vector<vector<float>>> float_3D;

float_1D A(x,0);
float_2D B(x,float_1D(y,0));
float_3D C(x,float_2D(y,float_1D(z,0)));

1D index to 2D index

If your 2D matrix is symmetric where [i][j] = [j][i], you can reduce the memory footprint by 2 fold when storing only values where i < j in a 1D vector of size l(l-1)/2; instead of a l^2. Where l = length. To access the values, you can use the follow functions:

To go from 2D index to 1D index:

int ij_n (int l, int i, int j){
   // exact solution
   return j - i - 1
       + l*(l-1)/2
       - (l-i)*((l-i)-1)/2;
}

To go from 1D index to 2D index:

int n_i_slow (int l, int n){
   // iterative solution
   int i = 0; n *= 2;
   while((i+1)*(2*l-i-2) <= n){i++;}
   return(i);
}

int n_i_fast (int l, int n){
   // approx. solution, using integer rounding
   int i = (2*l - sqrt(-8*n + 4*l*l - 4*l) - 1)/2;
   return(i);
}

int ni_j (int l, int n, int i){
   // exact solution
   return n + i + 1
       - l*(l-1)/2
       + (l-i)*((l-i)-1)/2;
}

1D index to 3D index

If your 3D matrix is symmetric where [i][j][k] = [i][k][j] = [j][i][k] = [j][k][i] = [k][i][j] = [k][j][i], you can reduce the memory footprint by 6 fold when storing only values where i < j < k in a 1D vector of size

l(l-1)(l-2)/6; instead of a l^3. Where l = length.

To go from 3D index to 1D index:

int ijk_n (int l, int i, int j, int k){
   // exact solution
   return k - j - 1
       + l*(l-1)*(l-2)/6
       - (l-i)*((l-i)-1)*((l-i)-2)/6
       + (l-i-1)*((l-i-1)-1)/2
       - (l-j)*((l-j)-1)/2;
}

To go from 1D index to 3D index:

int n_i (int l, int n){
   // iterative approach
   int i = 0; n *= 6;
   while((i+1)*(3*l*l-3*l*i-9*l+i*i+5*i+6) <= n){i++;}
   return(i);
}

int ni_j_slow (int l, int n, int i){
   int n_i = ((i+1)*(3*l*l-3*l*i-9*l+i*i+5*i+6)/6 - n) * 2;
   // iterative solution
   int j = i+1; while((j*j-2*j*l+3*j+l*l-3*l+2) >= n_i){j++;}
   return(j);
}

int ni_j_fast (int l, int n, int i){
   int n_i = (i+1)*(3*l*l-3*l*i-9*l+i*i+5*i+6)/6 - n;
   // faster using integer rounding
   int j = (2*l - sqrt(8*n_i) - 1)/2;
   return(j);
}

int nij_k (int l, int n, int i, int j){
   // exact solution
   return n + j + 1
       - l*(l-1)*(l-2)/6
       + (l-i)*((l-i)-1)*((l-i)-2)/6
       - (l-i-1)*((l-i-1)-1)/2
       + (l-j)*((l-j)-1)/2;
}

Comments