c++ notes
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;
}