如何培养一个存储在第二个功率嵌套词典中的稀疏三角矩阵？

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}}

来自注释的后续操作

下面的示例展示了如何对矩阵求幂（不是我上面展示的按元素运算）。

请注意，此代码更改了您的版本和我的原始版本的一些内容。它接受 (r,c,v) 顺序的项目，并且不会尝试像强制三角矩阵那样“标准化”索引。

如果您想要这种行为，则必须编辑此版本才能将其重新添加回来。

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]]