矩阵¶
矩阵是一种具有多个行和列的元素矩形阵列，其中的元素通常为数字。
比如以下展示的矩阵就包含了3行4列，其中位于第一行第一列的元素为数字1、第一行第二列的元素为3、第一行第三列的元素为9、第一行第四列的元素为2，等等。
矩阵在数学、物理、三维动画等多个领域均有大量应用，是计算机最常储存和处理的数据之一，因此研究如何在Redis中高效地存储矩阵数据是非常有意义的。
需求描述¶
你想要使用Redis实现一个矩阵存储程序，以便对矩阵及其包含的元素进行设置和获取操作。
解决方案：使用列表¶
因为Redis目前尚未支持能够直接储存矩阵的数据结构，所以程序必需使用已有的数据结构来储存矩阵。最简单直接的一种方法就是使用多个列表来储存一个矩阵，其中每个列表储存矩阵中的一个行。
举个例子，对于前面展示的 \(3 \times 4\) 矩阵，程序可以使用三个列表来储存它，其中每个列表包含四个元素：
redis> RPUSH Matrix:10086:0 1 3 9 2
(integer) 4
redis> RPUSH Matrix:10086:1 5 20 32 11
(integer) 4
redis> RPUSH Matrix:10086:2 73 28 65 33
(integer) 4
这段代码通过三条命令，将矩阵的三个行分别储存在了格式为Matrix:id:row的三个列表键里面，其中id为矩阵的ID，而row则为被储存矩阵的行号。
这样一来，程序就可以通过LINDEX命令获取矩阵在指定行上某个列的值，又或者通过LRANGE命令获取矩阵在指定行上所有列的值。
比如以下代码就展示了如何获取矩阵第1列的第3个值，以及矩阵第2行所有列的值：
redis> LINDEX Matrix:10086:0 2
"9"
redis> LRANGE Matrix:10086:1 0 -1
1) "5"
2) "20"
3) "32"
4) "11"
与此类似，当程序需要对矩阵指定行列上的值进行设置的时候，只需要使用LSET命令即可。作为例子，以下代码展示了如何将第3行第4列的值从33修改为99：
redis> LINDEX Matrix:10086:2 3 -- 查看当前值
"33"
redis> LSET Matrix:10086:2 3 99 -- 设置新值
OK
redis> LINDEX Matrix:10086:2 3 -- 查看新值
"99"
代码清单 CODE_LIST_MATRIX 展示了使用上述原理实现的矩阵程序。
代码清单 CODE_LIST_MATRIX 列表实现的矩阵存储程序 list_matrix.py
def make_row_key(matrix_id, row):
return "Matrix:{0}:{1}".format(matrix_id, row)
class ListMatrix:
def __init__(self, client, matrix_id, M, N):
"""
创建一个使用ID标识，由指定数量的行和列组成的矩阵。
"""
self.client = client
self.matrix_id = matrix_id
self.M = M
self.N = N
def init(self, elements=None):
"""
根据给定数据对矩阵进行初始化。
如果没有给定数据，那么将矩阵的所有元素初始化为0。
"""
# 这个函数只能在矩阵不存在的情况下执行
key = make_row_key(self.matrix_id, 0)
assert(self.client.exists(key)==0)
# 如果未给定初始化矩阵，那么创建一个全为0的矩阵
if elements is None:
elements = []
for _ in range(self.M):
elements.append([0]*self.N)
# 检查矩阵的行数是否正确
if len(elements) != self.M:
raise ValueError("Incorrect row number, it should be {}.".format(self.M))
# 检查矩阵中每个行的列数是否正确
for row in range(self.M):
if len(elements[row]) != self.N:
raise ValueError("Incorrect col number, it should be {}.".format(self.N))
# 将给定的值推入矩阵的每一行中
for row in range(self.M):
row_key = make_row_key(self.matrix_id, row)
self.client.rpush(row_key, *elements[row])
def set(self, row, col, value):
"""
将指定行列上的元素设置为给定的值。
"""
row_key = make_row_key(self.matrix_id, row)
self.client.lset(row_key, col, value)
def get(self, row, col):
"""
获取指定行列的值。
"""
row_key = make_row_key(self.matrix_id, row)
raw_value = self.client.lindex(row_key, col)
return int(raw_value)
def get_row(self, row):
"""
获取指定行上所有列的值。
"""
row_key = make_row_key(self.matrix_id, row)
raw_cols = self.client.lrange(row_key, 0, -1)
return list(map(int, raw_cols))
def get_all(self):
"""
获取整个矩阵的所有行和列。
"""
matrix = []
# 遍历并获取矩阵的每一行
for row in range(self.M):
matrix.append(self.get_row(row))
return matrix
作为例子，以下代码展示了这个矩阵程序的具体用法：
>>> from redis import Redis
>>> from list_matrix import ListMatrix
>>> client = Redis(decode_responses=True)
>>> matrix = ListMatrix(client, "Matrix", 3, 4)
>>> matrix.init([[1, 3, 9, 2], [5, 20, 32, 11], [73, 28, 65, 33]]) # 初始化矩阵
>>> matrix.get(0, 0) # 获取指定位置上的值
1
>>> matrix.get(0, 1)
3
>>> matrix.get_row(0) # 获取指定行的所有列
[1, 3, 9, 2]
>>> matrix.get_all() # 获取整个矩阵
[[1, 3, 9, 2], [5, 20, 32, 11], [73, 28, 65, 33]]
>>> matrix.set(0, 0, 10086) # 设置指定位置的值然后获取矩阵进行检查
>>> matrix.get_all()
[[10086, 3, 9, 2], [5, 20, 32, 11], [73, 28, 65, 33]]
解决方案：使用位图¶
除了列表之外，还可以使用位图来储存矩阵数据。
使用位图储存矩阵数据需要用到BITFIELD命令以及它的SET、GET等子命令，这些命令允许程序将多个指定类型的数字储存在位图的指定偏移量上，又或者从位图的指定偏移量上获取之前储存的数字。
同样以之前展示过的这个矩阵为例：
如果想要储存这个矩阵的第一行，那么只需要执行以下命令即可：
redis> BITFIELD Matrix:10086:0 SET i64 #0 1 SET i64 #1 3 SET i64 #2 9 SET i64 #3 2
1) (integer) 0
2) (integer) 0
3) (integer) 0
4) (integer) 0
与此对应，当想要从矩阵里面取出这一行的时候，只需要执行以下代码即可：
redis> BITFIELD Matrix:10086:0 GET i64 #0 GET i64 #1 GET i64 #2 GET i64 #3
1) (integer) 1
2) (integer) 3
3) (integer) 9
4) (integer) 2
跟列表矩阵程序一样，位图矩阵程序只需要为矩阵中的每个行分别设置一个位图键，就可以将上述的存取方法从单个行扩展至整个矩阵。
代码清单 CODE_BITMAP_MATRIX 展示了使用位图实现的矩阵数据储存程序。
代码清单 CODE_BITMAP_MATRIX 位图实现的矩阵存储程序 bitmap_matrix.py
def make_row_key(matrix_id, row):
return "matrix:{0}:{1}".format(id, row)
class BitmapMatrix:
def __init__(self, client, matrix_id, M, N, type="i64"):
"""
创建一个使用ID标识，由指定数量的行和列组成的矩阵。
可选的type参数用于指定矩阵元素的类型。
"""
self.client = client
self.matrix_id = matrix_id
self.M = M
self.N = N
self.type = type
def init(self, elements=None):
"""
根据给定数据对矩阵进行初始化。
如果没有给定数据，那么将矩阵的所有元素初始化为0。
"""
# 这个函数只能在矩阵不存在的情况下执行
key = make_row_key(self.matrix_id, 0)
assert(self.client.exists(key)==0)
# 如果未给定初始化矩阵，那么创建一个全为0的矩阵
if elements is None:
# 位图的所有位置默认都被设置为0，无需另行设置
return
# 检查矩阵的行数是否正确
if len(elements) != self.M:
raise ValueError("Incorrect row number, it should be {}.".format(self.M))
# 检查矩阵中每个行的列数是否正确
for row in range(self.M):
if len(elements[row]) != self.N:
raise ValueError("Incorrect col number, it should be {}.".format(self.N))
# 遍历矩阵的每个行
for row in range(self.M):
key = make_row_key(self.matrix_id, row)
bfop = self.client.bitfield(key)
# 对行中的每一列进行设置
for col in range(self.N):
bfop.set(self.type, "#{}".format(col), elements[row][col])
bfop.execute()
def set(self, row, col, value):
"""
将指定行列上的元素设置为给定的值。
"""
key = make_row_key(self.matrix_id, row)
bfop = self.client.bitfield(key)
bfop.set(self.type, "#{}".format(col), value)
bfop.execute()
def get(self, row, col):
"""
获取指定行列的值。
"""
key = make_row_key(self.matrix_id, row)
bfop = self.client.bitfield(key)
bfop.get(self.type, "#{}".format(col))
return bfop.execute()[0]
def get_row(self, row):
"""
获取指定行上所有列的值。
"""
key = make_row_key(self.matrix_id, row)
bfop = self.client.bitfield(key)
# 遍历该行的所有列，获取它们的值
for col in range(self.N):
bfop.get(self.type, "#{}".format(col))
return bfop.execute()
def get_all(self):
"""
获取整个矩阵的所有行和列。
"""
matrix = []
# 遍历并获取矩阵的每一行
for row in range(self.M):
matrix.append(self.get_row(row))
return matrix
跟列表矩阵程序相比，位图矩阵程序的一个主要优点是：位图矩阵在默认情况下会把所有元素都看作是0，所以它无需初始化即可随时使用并对任意元素进行设置。
比如以下代码就展示了如何使用位图矩阵对稀疏矩阵中少数几个不为0的元素进行设置：
>>> from redis import Redis
>>> from bitmap_matrix import BitmapMatrix
>>> sparse = BitmapMatrix(client, "SparseMatrix", 5, 5)
>>> sparse.get_all() # 矩阵默认由元素0组成
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
>>> sparse.set(0, 0, 128) # 设置元素
>>> sparse.set(1, 0, 256)
>>> sparse.set(2, 0, 512)
>>> sparse.get_all() # 获取设置后的稀疏矩阵
[[128, 0, 0, 0, 0], [256, 0, 0, 0, 0], [512, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
可以看到，位图矩阵在默认情况下会把整个矩阵的所有元素都看作是0。
当然，对于稠密矩阵，程序仍然可以像之前那样，通过init()方法对整个矩阵进行初始化：
>>> matrix = BitmapMatrix(client, "DenseMatrix", 3, 4)
>>> matrix.init([[1, 3, 9, 2], [5, 20, 32, 11], [73, 28, 65, 33]])
>>> matrix.get_all()
[[1, 3, 9, 2], [5, 20, 32, 11], [73, 28, 65, 33]]
>>> matrix.set(0, 0, 10086)
>>> matrix.get_all()
[[10086, 3, 9, 2], [5, 20, 32, 11], [73, 28, 65, 33]]
在这种情况下，位图矩阵的行为跟列表矩阵将完全一致。
重点回顾¶
矩阵是一种具有多个行和列的元素矩形阵列，其中的元素通常为数字。
矩阵在数学、物理、三维动画等多个领域均有大量应用，是计算机最常储存和处理的数据之一，因此研究如何在Redis中高效地存储矩阵数据是非常有意义的。
储存矩阵最简单直接的一种方法就是使用多个列表来储存一个矩阵，其中每个列表储存矩阵中的一个行。
除了列表之外还可以使用位图来储存矩阵数据：跟列表矩阵程序一样，位图矩阵程序只需要为矩阵中的每个行分别设置一个位图键，就可以将储存单个行的方法扩展至储存整个矩阵。
跟使用列表储存矩阵相比，使用位图储存矩阵的一个主要优点是：位图矩阵在默认情况下会把所有元素都看作是0，所以它无需初始化即可随时使用并对任意元素进行设置。