如何将存储在嵌套字典中的稀疏三角矩阵提高到二次方？

Question

我有一个稀疏三角矩阵，我需要求它的二次方。问题是，其中一个要求是矩阵存储为嵌套字典（我需要创建一个 python 实现），因此 numpy 的标准函数不适用。（我知道这种存储矩阵的方式可能有点矫枉过正，但这是大学课程）

下面是我如何实现矩阵本身的创建（稀有相当于这里的稀疏）：

    def __init__(self, *matrix):
        self.rare_values = dict()
        if len(matrix) > 0:
            for i, line in enumerate(matrix):
                if i == 0:
                    self.n = line
                    continue
                value = line[0]
                i = line[1]
                j = line[2]
                if j > i:

                    i = line[2]
                    j = line[1]
                if i in self.rare_values.keys():
                    if j in self.rare_values[i].keys():
                        self.rare_values[i][j] += value
                    else:
                        dict_column = {j: value}
                        self.rare_values[i].update(dict_column)
                else:
                    dict_line = {i: {j: value}}
                    self.rare_values.update(dict_line)

我的问题是，是否可以实现一种算法来提高这样一个矩阵的二次方？如果是这样，如果您能提供伪代码或最简单的解释来说明我将如何处理它，我将不胜感激。

谢谢！

Answer 1

您提供的代码可以大大简化为：

class Sparse:
    def __init__(self, n=None, *matrix):
        self.rare_values = dict()
        self.n = n
        for line in matrix:
            value, *indices = line
            c,r = sorted(indices)
            # Personally, here I would have instead used
            #   r,c = sorted(indices, reverse=True)
            # as (r,c) order seems more common, but it's no big deal.
            self.rare_values.setdefault(r, {})[c] = value

这会产生与您的 __init__ 方法相同的结构，只是更清晰 (IMO)。

从那里开始，对每个值求平方就像遍历 dict-of-dicts 一样简单，例如使用嵌套的 for 循环遍历 .items():

    def square(self):
        for (r,row) in self.rare_values.items():
            for (c,val) in row.items():
                self.rare_values[r][c] = val ** 2

示例：

class Sparse:
    def __init__(self, n=None, *matrix):
        self.rare_values = dict()
        self.n = n
        for line in matrix:
            value, *indices = line
            c,r = sorted(indices)
            self.rare_values.setdefault(r, {})[c] = value

    def square(self):
        for (r,row) in self.rare_values.items():
            for (c,val) in row.items():
                self.rare_values[r][c] = val ** 2

s = Sparse(3, (0,0,0), (2,1,1), (4,0,2), (6,2,3), (8,0,4))
print(s.rare_values)  # {0: {0: 0}, 1: {1: 2}, 2: {0: 4}, 3: {2: 6}, 4: {0: 8}}
s.square()
print(s.rare_values)  # {0: {0: 0}, 1: {1: 4}, 2: {0: 16}, 3: {2: 36}, 4: {0: 64}}

Follow-up 来自评论

以下示例显示了如何将矩阵乘方（不是我上面显示的 element-wise 操作）。

注意这段代码改变了你的版本和我的原始版本的一些东西。它接受 (r,c,v) 顺序的项目，并且不会像您强制三角矩阵那样尝试“规范化”索引。

如果您想要这种行为，您必须将此版本编辑为 re-add 那个版本。

class Sparse:
    def __init__(self, n=None, entries=None):
        self.matrix = dict()
        self.n = n
        for (r,c,v) in (entries or []):
            self.set(r, c, v)

    def set(self, r, c, v):
        self.matrix.setdefault(r, {})[c] = v

    def get(self, r, c):
        return self.matrix.get(r, {}).get(c, 0)

    def square_matrix(self):
        result = Sparse(self.n)
        for r in range(self.n):
            for c in range(self.n):
                val = sum(self.get(r,i) * self.get(i,c) for i in range(self.n))
                result.set(r, c, val)

        return result

sparse = Sparse(2, [
    (0,0,1), (0,1,2),
    (1,0,3), (1,1,4),
])
print(sparse.matrix)   # {0: {0: 1, 1: 2}, 1: {0: 3, 1: 4}}
#                        = [[1 2]
#                           [3 4]]
result = sparse.square_matrix()
print(result.matrix)   # {0: {0: 7, 1: 10}, 1: {0: 15, 1: 22}}
#                        = [[ 7 10]
#                           [15 20]]

如何将存储在嵌套字典中的稀疏三角矩阵提高到二次方？

How can I raise a sparse triangular matrix stored in a nested dictionary to the 2nd power?

python

math

dictionary

matrix