矩阵数据结构

Question

一个简单的二维数组可以在O(1)的时间内交换矩阵中的行（或者列）。有没有什么高效的数据结构，可以在O(1)的时间内同时交换矩阵的行和列呢？

Answer 1

也许 numpy数组 可以帮到你——它可以让你同时访问行和列，而且效率相当高（这是scipy的基本数据类型）

>>> def f(x,y):
...         return 10*x+y
...
>>> b = fromfunction(f,(5,4),dtype=int)
>>> b
array([[ 0,  1,  2,  3],
       [10, 11, 12, 13],
       [20, 21, 22, 23],
       [30, 31, 32, 33],
       [40, 41, 42, 43]])
>>> b[:,1]                                 # the second column of b
array([ 1, 11, 21, 31, 41])
>>> b[1:3,:]                               # the second and third row of b
array([[10, 11, 12, 13],
       [20, 21, 22, 23]])

Answer 2

你需要把你的矩阵存储成行的列表或者列的列表。这样的话，你就可以在O(1)的时间内交换行或者交换列。

不过，你可以在这个基础上再加一层，来处理列的顺序，这样你就能在O(1)的时间内重新排列列。

所以每次访问的时候，你需要做：

x = data[row][colorder[col]] 

交换行的操作是：

data[row1], data[row2] = data[row2], data[row1]

而交换列的操作是：

colorder[col1], colorder[col2] = colorder[c2], colorder[c1]