我有一個簡單的 2D（行、列）矩陣，我目前根據下面的演算法對其進行重新排序，使用另一個陣列作為交換專案的最終容器。
問題是我需要節省記憶體（代碼在非常低端的設備上運行），因此我需要想辦法就地重新排序陣列。
演算法如下：
for (int iRHS = 0; iRHS < NUM_VARS; iRHS )
for (int iRow = 0; iRow < _numEquations; iRow ) {
coef[iRHS][iRow] = _matrixCoef(iRow, iRHS);
}
注意：coef 是一個指向通過下標訪問的 double 的指標，_matrixCoef 是一個矩陣輔助類，并使用 operator(row,col) 訪問的 double 的向量。在這里，我想消除 coef，以便所有值都在 _matrixCoef 中就地重新排序。
編輯：NUM_VARS 是一個定義設定為 2。
畢竟這可能就地嗎？
編輯2：
這是上面通過運算子多載 (row, col) 訪問的矩陣類：
struct Matrix
{
/// Creates a matrix with zero rows and columns.
Matrix() = default;
/// Creates a matrix with \a rows rows and \a col columns
/// Its elements are initialized to 0.
Matrix(int rows, int cols) : n_rows(rows), n_cols(cols), v(rows * cols, 0.) {}
/// Returns the number or rows of the matrix
inline int getNumRows() const { return n_rows; }
/// Returns the number or columns of the matrix.
inline int getNumCols() const { return n_cols; }
/// Returns the reference to the element at the position \a row, \a col.
inline double & operator()(int row, int col) { return v[row col * n_rows]; }
/// Returns the element at the position \a row, \a col by value.
inline double operator()(int row, int col) const { return v[row col * n_rows]; }
/// Returns the values of the matrix in column major order.
double const * data() const { return v.data(); }
/// Returns the values of the matrix in column major order.
double * data() { return v.data(); }
/// Initialize the matrix with given size. All values are set to zero.
void initialize(int iRows, int iCols)
{
n_rows = iRows;
n_cols = iCols;
v.clear();
v.resize(iRows * iCols);
}
void resize(int iRows, int iCols)
{
n_rows = iRows;
n_cols = iCols;
v.resize(iRows * iCols);
}
private:
int n_rows = 0;
int n_cols = 0;
std::vector<double> v;
};
uj5u.com熱心網友回復：
在您發布代碼后，我會建議另一種解決方案，它實施起來相當簡單且快速。
在您當前的 Matrix 類中：
struct Matrix
{
// ...
// add this:
void transpose()
{
is_transposed = !is_transposed;
}
// ...
// modify these:
/// Returns the number or rows of the matrix
inline int getNumRows() const { return (is_transposed) ? n_cols : n_rows; }
/// Returns the number or columns of the matrix.
inline int getNumCols() const { return (is_transposed) ? n_rows : n_cols; }
/// Returns the reference to the element at the position \a row, \a col.
inline double & operator()(int row, int col)
{
if (is_transposed)
return v[col row * n_rows];
return v[row col * n_rows];
}
/// Returns the element at the position \a row, \a col by value.
inline double operator()(int row, int col) const
{
if (is_transposed)
return v[col row * n_rows];
return v[row col * n_rows];
}
private:
// ...
// add this:
bool is_transposed = false;
};
您可能想要修改其他成員函式，具體取決于您的應用程式。
uj5u.com熱心網友回復：
好吧，假設您的矩陣是方陣，即 NUM_VARS == _numEquations，這是可能的。否則生成的矩陣的大小將不允許就地轉置。在這種情況下，解決方案是修改下游計算以在執行操作時交換行/列索引。
但如果它是方形的，你可以試試這個：
for (size_t r = 0; r < NUM_VARS; r)
for (size_t c = 0; c < NUM_VARS; c)
{
if (&_matrixCoef[r][c] < &_matrixCoef[c][r])
std::swap(_matrixCoef[r][c], _matrixCoef[c][r]);
}
uj5u.com熱心網友回復：
如果要顯式就地重新排序資料陣列：
考慮這篇文章，詳細介紹了給定排列的陣列的就地重新排序。我只是稍微修改了它。在恒定記憶體空間中應用置換的演算法
置換的運算式可以推匯出如下：
對于索引k = i j * rows，j = k / rows和i = k - j * rows（整數除法）。轉置矩陣的索引為k_transpose = j i * cols。現在的代碼：
int perm(int k, int rows, int cols)
{
int j = k / rows;
int i = k - j * rows;
return j i * cols;
}
template<typename Scalar>
void transpose_colmajor(Scalar* A, int rows, int cols)
{
//tiny optimization: for (int i = 1; i < rows * cols - 1; i )
for (int i = 0; i < rows * cols; i ) {
int ind = perm(i, rows, cols);
while (ind > i)
ind = perm(ind, rows, cols);
std::swap(A[i], A[ind]);
}
}
帶有符號矩陣的示例：
int rows = 4;
int cols = 2;
char entry = 'a';
std::vector<char> symbolic_matrix;
for (int col = 0; col < cols; col )
{
for (int row = 0; row < rows; row )
{
symbolic_matrix.push_back(entry);
entry ;
}
}
for (char coefficient : symbolic_matrix)
std::cout << coefficient << ",";
std::cout << "\n\n";
transpose_colmajor(symbolic_matrix.data(), rows, cols);
for (char coefficient : symbolic_matrix)
std::cout << coefficient << ",";
std::cout << "\n\n";
輸出：
a,b,c,d,e,f,g,h,
a,e,b,f,c,g,d,h,
當然，您還必須使用正確的行和列更新結構。漸近的計算復雜度不保證是線性的，但是沒有輔助資料結構消耗你寶貴的記憶體！
編輯：我不得不承認，我從這個問題中學到了很多。我想知道為什么轉置方陣如此直觀，而矩形則不然。它與排列的回圈有關。該演算法https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/計算給定排列所需的最小交換。如果插入上面的置換運算式，您可以看到最小交換次數在 時急劇增加rows != cols。例如，4 x 4矩陣需要6交換，而4 x 3矩陣需要8，這對我來說非常違反直覺！我發布的演算法需要rows * cols - 2交換，這不是最佳的。然而，基于矩形矩陣的隨機實驗，最小交換之間的差距似乎非常小，對于較大的矩陣不太重要。絕對值得專門用于方陣的轉置例程，因為最小交換總是n * (n - 1)/2。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/363469.html