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