是否有一种有效的行列交换数据结构？

Question

我有一个数字矩阵，我希望能够：

1. 交换行
2. 交换列

如果我要使用指向行的指针数组，那么我可以在 O(1) 中轻松地在行之间切换，但交换列是 O (N) 其中 N 是行数。

我有一种明显的感觉，没有一个双赢的数据结构可以为这两个操作提供 O(1)，尽管我不确定如何证明它。还是我错了？

Answer 1

没有完全思考这一点：

我认为你关于行指针的想法是正确的开始。然后，为了能够“交换”列，我只需拥有另一个具有列数大小的数组，并在每个字段中存储该列当前物理位置的索引。

m = 
[0] -> 1 2 3
[1] -> 4 5 6
[2] -> 7 8 9 

c[] {0,1,2}

现在要交换第 1 列和第 2 列，只需将 c 更改为 {0,2,1}

当您想读取第 1 行时，您可以这样做

for (i=0; i < colcount; i++) {
   print m[1][c[i]];
}

Answer 2

不过这里只是随机的（没有经验知道这到底有多有效，而且这是一个没有咖啡的深夜）：

我的想法是矩阵的内部是一个哈希表而不是一个数组。

数组中的每个单元格都包含三部分信息：

1. 单元格所在的行
2. 单元格所在的列
3. 单元格的值

在我看来，这可以很容易地用元组 ((i, j) 表示, v)，其中 (i, j) 表示单元格的位置（第 i 行，第 j 列），而 v

是 a 的正常表示矩阵。但让我们在这里引出一些想法。让我们将 i 视为某种规范标识符，而不是将 i 表示为一个位置（即 0 在 1 在 2 在 3 之前等）。排。让我们对 j 执行相同的操作。 （虽然在最一般的情况下，i 和 j 可以不受限制，但让我们假设一个简单的情况，它们将保持在范围 [0..M] 和 [ 0..N] 对于 M x N 矩阵，但不表示单元格的实际坐标）。

现在，我们需要一种方法来跟踪行的标识符以及与该行关联的当前索引。这显然需要一个键/值数据结构，但由于索引的数量是固定的（矩阵通常不会增长/收缩），并且只处理整数索引，我们可以将其实现为固定的一维数组。对于 M 行的矩阵，我们可以（在 C 中）：

int RowMap[M];

对于第 m 行，RowMap[m] 给出当前矩阵中的行的标识符。

我们将对列使用相同的内容：

int ColumnMap[N];

其中 ColumnMap[n] 是第 n 列的标识符。

现在回到我在开头提到的哈希表：

由于我们拥有完整的信息（矩阵的大小），因此我们应该能够生成完美的哈希函数（无冲突）。这是一种可能性（对于适度大小的数组）：

int Hash(int row, int column)
{
    return row * N + column;
}

如果这是哈希表的哈希函数，那么对于大多数大小的数组，我们应该获得零冲突。这允许我们在 O(1) 时间内从哈希表中读取/写入数据。

最酷的部分是将每行/列的索引与哈希表中的标识符连接起来：

// row and column are given in the usual way, in the range [0..M] and [0..N]
// These parameters are really just used as handles to the internal row and
// column indices
int MatrixLookup(int row, int column)
{
    // Get the canonical identifiers of the row and column, and hash them.
    int canonicalRow = RowMap[row];
    int canonicalColumn = ColumnMap[column];
    int hashCode = Hash(canonicalRow, canonicalColumn);

    return HashTableLookup(hashCode);
}

现在，由于矩阵的接口仅使用这些句柄，而不使用内部标识符，因此可以进行交换操作行或列对应于 RowMap 或 ColumnMap 数组中的简单更改：

// This function simply swaps the values at
// RowMap[row1] and RowMap[row2]
void MatrixSwapRow(int row1, int row2)
{
    int canonicalRow1 = RowMap[row1];
    int canonicalRow2 = RowMap[row2];

    RowMap[row1] = canonicalRow2
    RowMap[row2] = canonicalRow1;
}

// This function simply swaps the values at
// ColumnMap[row1] and ColumnMap[row2]
void MatrixSwapColumn(int column1, int column2)
{
    int canonicalColumn1 = ColumnMap[column1];
    int canonicalColumn2 = ColumnMap[column2];

    ColumnMap[row1] = canonicalColumn2
    ColumnMap[row2] = canonicalColumn1;
}

所以应该是这样 - 具有 O(1) 访问和变异以及 O(1) 访问和变异的矩阵(1) 行交换和O(1) 列交换。当然，即使是 O(1) 的哈希访问也会比基于数组的 O(1) 访问慢，并且会使用更多的内存，但至少行/列之间是相等的。

当涉及到如何实现矩阵时，我试图尽可能保持不可知论，所以我写了一些 C 语言。如果你更喜欢另一种语言，我可以更改它（如果你理解的话那就最好了），但我认为它非常具有自我描述性，尽管我不能确保它在 C 方面的正确性，因为我实际上是一个 C++ 人员，现在正试图表现得像一个 C 人员（我是否提到过我没有咖啡？）。就我个人而言，用完整的面向对象语言编写将使条目设计更加公正，并且还使代码更美观，但正如我所说，这是一个快速完成的实现。