Appliquer la fonction memmove à un tableau 3d

Question

J'essaie d'obtenir la fonction fftshift (de MATLAB) en C++ avec for loop et cela prend beaucoup de temps. voici mon code:

const int a = 3; 
    const int b = 4; 
    const int c = 5; 
    int i, j, k; 
    int aa = a/2; 
    int bb = b/2; 
    int cc = c/2; 

    double ***te, ***tempa; 
    te = new double **[a]; 
    tempa = new double **[a]; 
    for (i = 0; i < a; i++) 
    { 
     te[i] = new double *[b]; 
     tempa[i] = new double *[b]; 
     for (j = 0; j < b; j++) 
     { 
      te[i][j] = new double [c]; 
      tempa[i][j] = new double [c]; 
      for (k = 0; k < c; k++) 
      { 
       te[i][j][k] = i + j+k; 
      } 

     } 
    } 
    /*for the row*/ 
    if (c % 2 == 1) 
    { 
     for (i = 0; i < a; i++) 
     { 
      for (j = 0; j < b; j++) 
      { 
       for (k = 0; k < cc; k++) 
       { 
        tempa[i][j][k] = te[i][j][k + cc + 1]; 
        tempa[i][j][k + cc] = te[i][j][k]; 
        tempa[i][j][c - 1] = te[i][j][cc]; 
       } 
      } 
     } 
    } 
    else 
    { 
     for (i = 0; i < a; i++) 
     { 
      for (j = 0; j < b; j++) 
      { 
       for (k = 0; k < cc; k++) 
       { 
        tempa[i][j][k] = te[i][j][k + cc]; 
        tempa[i][j][k + cc] = te[i][j][k]; 
       } 
      } 
     } 
    } 

    for (i = 0; i < a; i++) 
    { 
     for (j = 0; j < b; j++) 
     { 
      for (k = 0; k < c; k++) 
      { 
       te[i][j][k] = tempa[i][j][k]; 
      } 
     } 
    } 

    /*for the column*/ 
    if (b % 2 == 1) 
    { 
     for (i = 0; i < a; i++) 
     { 
      for (j = 0; j < bb; j++) 
      { 
       for (k = 0; k < c; k++) 
       { 
        tempa[i][j][k] = te[i][j + bb + 1][k]; 
        tempa[i][j + bb][k] = te[i][j][k]; 
        tempa[i][b - 1][k] = te[i][bb][k]; 
       } 
      } 
     } 
    } 
    else 
    { 
     for (i = 0; i < a; i++) 
     { 
      for (j = 0; j < bb; j++) 
      { 
       for (k = 0; k < c; k++) 
       { 
        tempa[i][j][k] = te[i][j + bb][k]; 
        tempa[i][j + bb][k] = te[i][j][k]; 
       } 
      } 
     } 
    } 

    for (i = 0; i < a; i++) 
    { 
     for (j = 0; j < b; j++) 
     { 
      for (k = 0; k < c; k++) 
      { 
       te[i][j][k] = tempa[i][j][k]; 
      } 
     } 
    } 

    /*for the third dimension*/ 
    if (a % 2 == 1) 
    { 

     for (i = 0; i < aa; i++) 
     { 
      for (j = 0; j < b; j++) 
      { 
       for (k = 0; k < c; k++) 
       { 
        tempa[i][j][k] = te[i + aa + 1][j][k]; 
        tempa[i + aa][j][k] = te[i][j][k]; 
        tempa[a - 1][j][k] = te[aa][j][k]; 
       } 
      } 
     } 
    } 
    else 
    { 
     for (i = 0; i < aa; i++) 
     { 
      for (j = 0; j < b; j++) 
      { 
       for (k = 0; k < c; k++) 
       { 
        tempa[i][j][k] = te[i + aa][j][k]; 
        tempa[i + aa][j][k] = te[i][j][k]; 

       } 
      } 
     } 
    } 

    for (i = 0; i < a; i++) 
    { 
     for (j = 0; j < b; j++) 
     { 
      for (k = 0; k < c; k++) 
      { 
       cout << te[i][j][k] << ' '; 
      } 
      cout << endl; 
     } 
     cout << "\n"; 
    } 
    cout << "and then" << endl; 
    for (i = 0; i < a; i++) 
    { 
     for (j = 0; j < b; j++) 
     { 
      for (k = 0; k < c; k++) 
      { 
       cout << tempa[i][j][k] << ' '; 
      } 
      cout << endl; 
     } 
     cout << "\n"; 
    } 

maintenant je veux réécrire avec memmove pour améliorer l'efficacité en cours d'exécution. Pour la 3ème dimension, j'utilise:

memmove(tempa, te + aa, sizeof(double)*(a - aa)); 
    memmove(tempa + aa+1, te, sizeof(double)* aa); 

ce code peut fonctionne bien avec tableau 1d et 2d, mais ne fonctionne pas pour le tableau 3d. En outre, je ne sais pas comment déplacer les éléments de colonne et de ligne avec memmove. Tout le monde peut m'aider avec tout cela? Merci beaucoup!!

Maintenant, j'ai modifié le code ci-dessous:

double ***te, ***tempa1,***tempa2, ***tempa3; 

    te = new double **[a]; 
    tempa1 = new double **[a]; 
    tempa2 = new double **[a]; 
    tempa3 = new double **[a]; 
    for (i = 0; i < a; i++) 
    { 
     te[i] = new double *[b]; 
     tempa1[i] = new double *[b]; 
     tempa2[i] = new double *[b]; 
     tempa3[i] = new double *[b]; 
     for (j = 0; j < b; j++) 
     { 
      te[i][j] = new double [c]; 
      tempa1[i][j] = new double [c]; 
      tempa2[i][j] = new double [c]; 
      tempa3[i][j] = new double [c]; 
      for (k = 0; k < c; k++) 
      { 
       te[i][j][k] = i + j+k; 
      } 

     } 
    } 

    /*for the third dimension*/ 
    memmove(tempa1, te + (a-aa), sizeof(double**)*aa); 
    memmove(tempa1 + aa, te, sizeof(double**)* (a-aa)); 
    //memmove(te, tempa, sizeof(double)*a); 
    /*for the row*/ 
    for (i = 0; i < a; i++) 
    { 
     memmove(tempa2[i], tempa1[i] + (b - bb), sizeof(double*)*bb); 
     memmove(tempa2[i] + bb, tempa1[i], sizeof(double*)*(b - bb)); 
    } 

    /*for the column*/ 
    for (j = 0; i < a; i++) 
    { 
     for (k = 0; j < b; j++) 
     { 
      memmove(tempa3[i][j], tempa2[i][j] + (c - cc), sizeof(double)*cc); 
      memmove(tempa3[i][j] + cc, tempa2[i][j], sizeof(double)*(c-cc)); 
     } 
    } 

mais le problème est que je définis trop de nouveaux tableaux dynamiques et aussi les résultats pour tempa3 sont incorrects. quelqu'un pourrait-il donner quelques suggestions?

Answer 1

Je crois que vous voulez quelque chose comme ça:

memmove(tempa, te + (a - aa), sizeof(double**) * aa); 
memmove(tempa + aa, te, sizeof(double**) * (a - aa)); 

ou

memmove(tempa, te + aa, sizeof(double**) * (a - aa)); 
memmove(tempa + (a - aa), te, sizeof(double**) * aa); 

selon que vous voulez échanger la première moitié « arrondie vers le haut ou vers le bas » (je suppose que vous voulez arrondi en haut, c'est la première version alors).

---

Je ne aime pas vraiment la conception de votre code si:

En premier lieu, éviter l'allocation dynamique et utiliser std::vector ou std::array lorsque cela est possible. Vous pourriez argumenter qu'il vous empêcherait d'utiliser en toute sécurité memmove au lieu de swap pour les premières dimensions (bien, ça devrait marcher, mais je ne suis pas sûr à 100% que ce n'est pas une implémentation définie) mais je ne pense pas que cela améliorerait autant l'efficacité. De plus, si vous voulez avoir un tableau à N dimensions, je préfère généralement éviter les "pointeurs de chaînage" (bien qu'avec votre algorithme, vous puissiez réellement utiliser cette structure, donc ce n'est pas si grave). Par exemple, si vous êtes catégorique sur l'allocation dynamique de votre tableau avec new, vous pouvez utiliser quelque chose comme ça pour réduire l'utilisation de la mémoire (la différence peut être négligeable, probablement aussi légèrement plus rapide mais probablement négligeable):

#include <cstddef> 
#include <iostream> 

typedef std::size_t index_t; 

constexpr index_t width = 3; 
constexpr index_t height = 4; 
constexpr index_t depth = 5; 

// the cells (i, j, k) and (i, j, k+1) are adjacent in memory 
// the rows (i, j, _) and (i, j+1, _) are adjacent in memory 
// the "slices" (i, _, _) and (i+1, _, _) are adjacent in memory 
constexpr index_t cell_index(index_t i, index_t j, index_t k) { 
    return (i * height + j) * depth + k; 
} 

int main() { 
    int* array = new int[width * height * depth](); 
    for(index_t i = 0 ; i < width ; ++i) 
    for(index_t j = 0 ; j < height ; ++j) 
     for(index_t k = 0 ; k < depth ; ++k) { 
     // do something on the cell (i, j, k) 
     array[cell_index(i, j, k)] = i + j + k; 
     std::cout << array[cell_index(i, j, k)] << ' '; 
     } 
    std::cout << '\n'; 
    // alternatively you can do this: 
    //* 
    for(index_t index = 0 ; index < width * height * depth ; ++index) { 
    index_t i = index/(height * depth); 
    index_t j = (index/depth) % height; 
    index_t k = index % depth; 
    array[index] = i + j + k; 
    std::cout << array[index] << ' '; 
    } 
    std::cout << '\n'; 
    //*/ 
    delete[] array; 
} 

La différence est l'organisation en mémoire. Ici vous avez un gros bloc de 60 * sizeof (int) octets (habituellement 240 ou 480 octets), alors qu'avec votre méthode vous auriez: - 1 bloc de 3 * sizeof (int **) octets - 3 blocs de 4 * sizeof (int *) octets - 12 blocs de 5 * sizeof (int) octets (120 octets de plus sur une architecture 64 bits, deux indirections supplémentaires pour chaque accès de cellule, et plus de code pour allouer/désallouer toute cette mémoire) Certes, vous ne pouvez plus faire array [i] [j] [k], mais quand même ...

Les mêmes stands avec vector s (vous pouvez faire un std::vector<std::vector<std::vector<int>>> ou un std::vector<int>)

Il y a aussi un peu trop répétition de code: votre algorithme permute essentiellement les deux moitiés de votre table trois fois (une fois pour chaque dimension), mais vous avez réécrit 3 fois la même chose avec quelques différences.

Il y a aussi trop de l'allocation de mémoire/copie (vos œuvres d'algorithme et peut exploiter la structure du tableau de pointeurs en échangeant simplement des pointeurs pour échanger des rangées entières/tranches, dans ce cas précis, vous peut exploiter cette structure de données pour éviter les copies avec votre algorithme ... mais vous ne le faites pas)

Vous devriez choisir des noms de variables plus explicites, cela aide. Par exemple, utiliser width, height, depth au lieu de a, b, c.

Par exemple, voici une implémentation avec des vecteurs (je ne savais pas la fonction fftshift Matlab bien, mais en fonction de votre code et ce page, je suppose qu'il est fondamentalement « permutant les coins »):

(également , compilez avec std = C++ 11)

#include <cstddef> 
#include <iostream> 
#include <vector> 
#include <algorithm> 

typedef std::size_t index_t; 
typedef double element_t; 
typedef std::vector<element_t> row_t; 
typedef std::vector<row_t> slice_t; 
typedef std::vector<slice_t> array_3d_t; 

// for one dimension 
// you might overload this for a std::vector<double>& and use memmove 
// as you originally wanted to do here 
template<class T> 
void fftshift_dimension(std::vector<T>& row) 
{ 
    using std::swap; 
    const index_t size = row.size(); 
    if(size <= 1) 
    return; 
    const index_t halved_size = size/2; 
    // swap the two halves 
    for(index_t i = 0, j = size - halved_size ; i < halved_size ; ++i, ++j) 
    swap(row[i], row[j]); 
    // if the size is odd, rotate the right part 
    if(size % 2) 
    { 
    swap(row[halved_size], row[size - 1]); 
    const index_t n = size - 2; 
    for(index_t i = halved_size ; i < n ; ++i) 
     swap(row[i], row[i + 1]); 
    } 
} 

// base case 
template<class T> 
void fftshift(std::vector<T>& array) { 
    fftshift_dimension(array); 
} 

// reduce the problem for a dimension N+1 to a dimension N 
template<class T> 
void fftshift(std::vector<std::vector<T>>& array) { 
    fftshift_dimension(array); 
    for(auto& slice : array) 
    fftshift(slice); 
} 

// overloads operator<< to print a 3-dimensional array 
std::ostream& operator<<(std::ostream& output, const array_3d_t& input) { 
    const index_t width = input.size(); 
    for(index_t i = 0; i < width ; i++) 
    { 
    const index_t height = input[i].size(); 
    for(index_t j = 0; j < height ; j++) 
    { 
     const index_t depth = input[i][j].size(); 
     for(index_t k = 0; k < depth; k++) 
     output << input[i][j][k] << ' '; 
     output << '\n'; 
    } 
    output << '\n'; 
    } 
    return output; 
} 

int main() 
{ 
    constexpr index_t width = 3; 
    constexpr index_t height = 4; 
    constexpr index_t depth = 5; 

    array_3d_t input(width, slice_t(height, row_t(depth))); 

    // initialization 
    for(index_t i = 0 ; i < width ; ++i) 
    for(index_t j = 0 ; j < height ; ++j) 
     for(index_t k = 0 ; k < depth ; ++k) 
     input[i][j][k] = i + j + k; 
    std::cout << input; 

    // in place fftshift 
    fftshift(input); 

    std::cout << "and then" << '\n' << input; 
} 

live example

Vous pourriez probablement faire un algorithme légèrement plus efficace en évitant d'échanger plusieurs fois la même cellule et/ou en utilisant memmove, mais je pense que c'est déjà assez rapide pour de nombreuses utilisations (sur ma machine, fftshift prend environ 130ms pour une table 1000x1000x100).