Tools‎ > ‎

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;
}

Comments