Python中的稀疏矩阵运算

Question

我从我的python课程中得到了一份工作，但即使我试图完成一周，我也无法编写正确的代码。下面的图片清楚地解释了我要做的工作，实际上我正在努力解决一些错误，但我不知道如何修复它们，我真的厌倦了一次又一次的尝试。有人能帮我吗？而且，我不能使用任何图书馆或那种东西。我只允许使用列表、元组、字典、字符串、循环等。 有关说明，请看图片。 我只实现了最后三个定义的函数，其余的代码由我的讲师编写，以指导我们了解函数

The first page of instructions

The second page of instructions

import random
import math

def sparse_mat_add(sp_matrix1, sp_matrix2):
    """ 
    This function adds two sparse matrices together.
    You do not need to do do anything to this function, it is given to you
    as an example.
    """
    if (sp_matrix1[-1][0] != sp_matrix2[-1][0]) or (sp_matrix1[-1][1] != sp_matrix2[-1][1]):
        raise Exception ("Error! Matrix dimensions must agree.")

    
    sp_matrix_res = {}
    sp_matrix_res[-1] = sp_matrix1[-1]

    # Copying the first matrix into the result matrix
    # You can directly use a built-in dictionary method for this!
    # sp_matrix_res = sp_matrix1.copy()
    
    for key in sp_matrix1.keys():
        sp_matrix_res[key] = sp_matrix1[key]
        
    # Now, just add them update
    # Remember the get method of dictionaries!
    for key in sp_matrix2.keys():
        sp_matrix_res[key] = sp_matrix_res.get(key,0)+sp_matrix2[key]
        
    return sp_matrix_res
    
def generate_random_sparse_matrix(nrow, ncol, sparsity=0.6):
    """
    This function generates a random matrix as a list of lists with a given sparsity.
    """
    
    row = [0.]*ncol
    res=[]
    for i in range(nrow):
        res.append(row[:])

    nr = int((1.-sparsity)*nrow*ncol)
    pos = random.sample(range(nrow*ncol), nr)
    for ind in pos:
        n_ind = math.floor(ind/ncol)
        m_ind = ind-n_ind*ncol
        res[n_ind][m_ind]=random.random()
    return res

def is_equal(matrix, sparse_matrix, epsilon=1e-9):
    """ 
    This function compares a matrix with list of lists representation to a sparse matrix
    """

    nrows=len(matrix)
    ncols=len(matrix[0])
    if nrows!=sparse_matrix[-1][0] or ncols!=sparse_matrix[-1][1]:
        return False
        
    for r in range(nrows):
        for c in range(ncols):
            if abs(matrix[r][c] - sparse_matrix.get((r,c),0)) > epsilon:
                return False

    return True                

def show_sparse(sp_matrix):
    """
    This function displays the input sparse matrix as a formatted string
    """
    
    nrow,ncol=sp_matrix[-1]
    out=""
    for i in range(nrow):
        for j in range(ncol-1):
            out+=f"{sp_matrix.get((i,j),0.):8.3f},"
        out+=f"{sp_matrix.get((i,j+1),0.):8.3f}"+"\n"
    return out

def get_shape(item):
    rows, cols = 1,1
    if type(item) == list:  
        rows = len(item)
        if type(item[0]) == list:
            cols = len(item[0])
    return rows, cols

def mat_mult(matrix1, matrix2):
    """ 
    This function multiplies two sparse matrices to get a third sparse matrix and returns the result.
    sp_matrix_res = sp_matrix1*sp_matrix2
    TODO: Implement this function
    """
    
    r1,c1 = get_shape(matrix1)
    r2,c2 = get_shape(matrix2)
    
    if c1 != r2:
        raise ValueError("Inner matrix dimensions do not match")
    
    output_item = [0]*r1
    for i in range(r1):
        output_item[i] = [0]*c2
        for j in range(c2):
            for k in range(c1):
                output_item[i][j] += matrix1[i][k]*matrix2[k][j]
    return output_item

# The functions you need to modify are given below, you do not need to modify anything above this line. 
# Feel free to add more functions

def dense_to_sparse(matrix):
    """ 
    This function converts a given list of lists representation of a matrix to a sparse representation.
    This function must return the sparse representation of matrix as a dictionary. 
    return sp_matrix
    TODO: Implement this function
    """
    
    sp_matrix = {}
    
    # YOUR CODE GOES HERE. MAKE SURE sp_matrix IS THE SPARSE REPRESENTATION OF matrix
    numrow = -1
    for row in matrix:
        numrow += 1
        numcol = -1
        for col in row:
            numcol += 1
            if not col == 0:
                sp_matrix[(numrow,numcol)] = col
    sp_matrix[-1] = (numrow+1,numcol+1)
    #########mycodesfinished#####
    return sp_matrix
    
def sparse_transpose(sp_matrix):
    """ 
    This function returns the transpose of the input sparse matrix (sp_matrix) as another
    sparse matrix (sp_matrix_transpose).
    Hint: Look at the mat_mult function given above
    TODO: Implement this function
    """
    
    sp_matrix_transpose = {}
    
    # YOUR CODE GOES HERE. MAKE SURE sp_matrix_transpose IS SPARSE 
    numrow = -1
    for row in sp_matrix:
        numrow += 1
        numcol = -1
        for col in row:
            numcol += 1
            if not col == 0:
                sp_matrix_transpose[(numcol,numrow)] = col
    sp_matrix_transpose[-1] = (numcol+1,numrow+1)
    ##MYCODESEND##
    return sp_matrix_transpose
    
def sparse_mat_mult(sp_matrix1, sp_matrix2):
    """ 
    This function multiplies two sparse matrices to get a third sparse matrix and returns the result.
    sp_matrix_res = sp_matrix1*sp_matrix2
    TODO: Implement this function
    """
    
    sp_matrix_res = {}
    
    # YOUR CODE GOES HERE. MAKE SURE sp_matrix_res IS SPARSE 
    A = mat_mult(sp_matrix1, sp_matrix2)
    sp_matrix_res = dense_to_sparse(A)
    ##MYCODESEND##
    
    return sp_matrix_res

if __name__=="__main__":
    #WARNING: Not all the conditions are checked!!!
    
    iters = 100
    
    for iter in range(iters):
        r1 = random.randint(1,100)
        c1 = random.randint(1,100)
        c2 = random.randint(1,100)
        no_match = False
        if random.random() < 0.9:
            r2 = c1  
        else: 
            r2 = random.randint(1,100)
            if r2 != c1:
                no_match = True
        ll_sp_m1 = generate_random_sparse_matrix(3,4)
        ll_sp_m2 = generate_random_sparse_matrix(4,2)
        
        sp_m1 = dense_to_sparse(ll_sp_m1)
        sp_m2 = dense_to_sparse(ll_sp_m2)
        
        if(not is_equal(ll_sp_m1,sp_m1) or not is_equal(ll_sp_m2,sp_m2)):
            raise Exception("Wrong conversion from dense to sparse")
            
        sp_m1T = sparse_transpose(sp_m1)
        sp_m1TT = sparse_transpose(sp_m1T)
        if(not is_equal(ll_sp_m1,sp_m1TT)):
            raise Exception("Wrong sparse transpose operation")    
        
        try:
            ll_mult = mat_mult(ll_sp_m1, ll_sp_m2)    
            sp_mult = sparse_mat_mult(sp_m1, sp_m2)
        except ValueError as e:
            print(e)
            if(not no_match):
                raise
                
        if(not is_equal(ll_mult,sp_mult)):
            raise Exception("Wrong sparse matrix multiplication operation") 

Answer 1

请分享你在未来一直在尝试的代码示例。 通过这种方式，我们可以很容易地为您指出一个方向，而不是填鸭式地为您的完整作业表提供解决方案

下面是为练习的第1部分创建dict并开始的示例：

def main():
    matrix = [
        [0,1,5,0,0],
        [3,0,0,0,0],
        [0,0,7,0,9],
        [0,0,0,4,0],
        [0,2,0,0,8]
    ]

    sparse_matrix = dense_to_sparse(matrix)
    print(sparse_matrix)

#part1
def dense_to_sparse(matrix):
    sparse_matrix = dict()

    #getting the dimensions:
    #len(matrix) will give you the number of rows
    #len(matrix[0]) will give you the number of columns:
    sparse_matrix[-1] = (len(matrix), len(matrix[0]))

    for i, row in enumerate(matrix):
        for j, val in enumerate(row):
            # we just want to add the non-zero elements
            if val != 0:
                sparse_matrix[(i,j)] = val
    return sparse_matrix


if __name__ == '__main__':
    main()

关于练习的第2部分和第3部分： 通过翻转矩阵每个条目的列和行位置，可以获得矩阵的转置。在稀疏表示中，您在哪里找到它们

关于第3部分： 在矩阵A*B=C相乘的情况下，元素C[i][j] 是A的第i行和B的第j列的标量积。 提示：python dict将为缺少的键返回None。你必须把它们变成零

请尝试一下，分享一下你所做的。如果有问题 关于第二部分或第三部分或上述代码，请询问他们

如果您不熟悉字典：https://docs.python.org/3/library/stdtypes.html#typesmapping

更新： 我一直在复制和评论的代码，你已经分享以上。 若你们对一行代码有疑问，可以问我。 我没有详细检查所有已经实现的函数，但是稀疏的mat_add（）函数有缺陷。 它将两个输入矩阵的维数连接起来

不知道解算器是否会自动检查你的作业。最好事先和你的老师讨论一下

请在下面添加有关代码的更多问题（auf Hessisch gehts auch:），但我们最好为所有其他读者编写英语：

import random
import math

def sparse_mat_add(sp_matrix1, sp_matrix2):
    """
    This function adds two sparse matrices together.
    You do not need to do do anything to this function, it is given to you
    as an example.
    """
    if (sp_matrix1[-1][0] != sp_matrix2[-1][0]) or (sp_matrix1[-1][1] != sp_matrix2[-1][1]):
        raise Exception ("Error! Matrix dimensions must agree.")


    sp_matrix_res = {}
    #This will cause a bug later on, and the dimension-key will
    #have the concatenated tuples of matrix1 and matrix2 with 4 entries ...
    #sp_matrix_res[-1] = sp_matrix1[-1]
    #Removing the key -1 from both dicts, before looping over them.
    #Inserting the key, after the loop is done, otherwise, we have to check
    #each key, wether or not it is -1.
    if sp_matrix1 != sp_matrix2:
        sp_matrix2.pop(-1)
    dimensions = sp_matrix1.pop(-1)
    #Since i don't know, how your homework is checked. might be, that it is
    #just accepting the bugged result...


    # Copying the first matrix into the result matrix
    # You can directly use a built-in dictionary method for this!
    # sp_matrix_res = sp_matrix1.copy()

    for key in sp_matrix1.keys():
        sp_matrix_res[key] = sp_matrix1[key]

    # Now, just add them update
    # Remember the get method of dictionaries!
    for key in sp_matrix2.keys():
        sp_matrix_res[key] = sp_matrix_res.get(key,0)+sp_matrix2[key]


    #Inserting the dimensions:
    sp_matrix1[-1] = dimensions
    sp_matrix2[-1] = dimensions
    sp_matrix_res[-1] = dimensions
    return sp_matrix_res

def generate_random_sparse_matrix(nrow, ncol, sparsity=0.6):
    """
    This function generates a random matrix as a list of lists with a given sparsity.
    """

    row = [0.]*ncol
    res=[]
    for i in range(nrow):
        res.append(row[:])

    nr = int((1.-sparsity)*nrow*ncol)
    pos = random.sample(range(nrow*ncol), nr)
    for ind in pos:
        n_ind = math.floor(ind/ncol)
        m_ind = ind-n_ind*ncol
        res[n_ind][m_ind]=random.random()
    return res


def is_equal(matrix, sparse_matrix, epsilon=1e-9):
    """
    This function compares a matrix with list of lists representation to a sparse matrix
    """

    nrows=len(matrix)
    ncols=len(matrix[0])
    if nrows!=sparse_matrix[-1][0] or ncols!=sparse_matrix[-1][1]:
        return False

    for r in range(nrows):
        for c in range(ncols):
            if abs(matrix[r][c] - sparse_matrix.get((r,c),0)) > epsilon:
                return False
    return True

def show_sparse(sp_matrix):
    """
    This function displays the input sparse matrix as a formatted string
    """

    nrow,ncol=sp_matrix[-1]
    out=""
    for i in range(nrow):
        for j in range(ncol-1):
            out+=f"{sp_matrix.get((i,j),0.):8.3f},"
        out+=f"{sp_matrix.get((i,j+1),0.):8.3f}"+"\n"
    return out


def get_shape(item):
    rows, cols = 1,1
    if type(item) == list:
        rows = len(item)
        if type(item[0]) == list:
            cols = len(item[0])
    return rows, cols

def mat_mult(matrix1, matrix2):
    """
    This function multiplies two sparse matrices to get a third sparse matrix and returns the result.
    sp_matrix_res = sp_matrix1*sp_matrix2
    TODO: Implement this function
    """

    r1,c1 = get_shape(matrix1)
    r2,c2 = get_shape(matrix2)

    if c1 != r2:
        raise ValueError("Inner matrix dimensions do not match")

    output_item = [0]*r1
    for i in range(r1):
        output_item[i] = [0]*c2
        for j in range(c2):
            for k in range(c1):
                output_item[i][j] += matrix1[i][k]*matrix2[k][j]
    return output_item

# The functions you need to modify are given below, you do not need to modify anything above this line.
# Feel free to add more functions

def dense_to_sparse(matrix):
    """
    This function converts a given list of lists representation of a matrix to a sparse representation.
    This function must return the sparse representation of matrix as a dictionary.
    return sp_matrix
    TODO: Implement this function
    """

    sp_matrix = {}
    # YOUR CODE GOES HERE. MAKE SURE sp_matrix IS THE SPARSE REPRESENTATION OF matrix
    """
    #your code is working, however I suggest to use enumerate(), in order
    #to loop over your iterables. this way, you get the index + val at the same time
    #and don't have to update indexing variables.
    #my version from yesterday stored the dimensions with key (-1), however it seems
    #like your teacher asked for the key  -1.

    numrow = -1
    for row in matrix:
        numrow += 1
        numcol = -1
        for col in row:
            numcol += 1
            if not col == 0:
                sp_matrix[(numrow,numcol)] = col
    sp_matrix[-1] = (numrow+1,numcol+1)
    """
    sp_matrix[-1] = get_shape(matrix)#seems like your teacher shared already a get_shape() :)
    for i, row in enumerate(matrix):
        for j, val in enumerate(row):
            # we just want to add the non-zero elements
            if val != 0:
                sp_matrix[(i,j)] = val
    #########mycodesfinished#####
    return sp_matrix


def sparse_transpose(sp_matrix):
    """
    This function returns the transpose of the input sparse matrix (sp_matrix) as another
    sparse matrix (sp_matrix_transpose).
    Hint: Look at the mat_mult function given above
    TODO: Implement this function
    """

    sp_matrix_transpose = {}

    # YOUR CODE GOES HERE. MAKE SURE sp_matrix_transpose IS SPARSE
    """
    numrow = -1
    for row in sp_matrix: # sp_matrix is a dict, not a list of lists!!!
        numrow += 1
        numcol = -1
        for col in row:
            numcol += 1
            if not col == 0:
                sp_matrix_transpose[(numcol,numrow)] = col
    sp_matrix_transpose[-1] = (numcol+1,numrow+1)
    """
    """
    In comparism to the "list of lists-version of the matrix,
    the sparse - dict() is just like a single list. so we are going
    to iterate over all the keys of the dict, which store the position
    or the original matrix in the format (row, col), flip them to (col, row)
    and insert them in the transpose:
    """
    #popping the dimension:
    rows, cols = sp_matrix.pop(-1)

    for key, val in sp_matrix.items():
        row, col = key # unpacking the tuple
        sp_matrix_transpose[(col, row)] = val # flipping col and row !

    #inserting the dimension back into the dicts:
    sp_matrix_transpose[-1] = (cols, rows)
    sp_matrix[-1] = (rows, cols)
    ##MYCODESEND##
    return sp_matrix_transpose

def sparse_mat_mult(sp_matrix1, sp_matrix2):
    """
    This function multiplies two sparse matrices to get a third sparse matrix and returns the result.
    sp_matrix_res = sp_matrix1*sp_matrix2
    TODO: Implement this function
    """

    sp_matrix_res = {}

    # YOUR CODE GOES HERE. MAKE SURE sp_matrix_res IS SPARSE

    #A = mat_mult(sp_matrix1, sp_matrix2)
    #sp_matrix_res = dense_to_sparse(A)
    """the mat_mult() takes 2 list-of-lists - matrices as arguments
    and does the multiplication. We can't push the sparse-matrices as
    arguments to that function.

    We may use the sparse_to_dense() function, which i added below,
    convert them back to dense matrices, do the multiplication and
    convert back into sparse-form.

    Technically that approach would solve it, and its a good idea, to check
    small examples this way, to see, wether or not we did everything correct.

    However the idea behind Sparse (dünnbesetzt) matrices, which may contain
    a huge amount of zeroes -  imagine a matrix with a couple million zeroes
    - is to store them in a compressed form.
    In case we decompress them just for a multiplication, we shouldn't have
    been compressing them in the first place, since we just loose time with
    the compression and decompression-steps.
    """

    

    #popping the dimensions again, so we don't have to check for the key -1
    if sp_matrix1 != sp_matrix2:
        dimensions1 = sp_matrix1.pop(-1)
        rows1, cols1 = dimensions1

        dimensions2 = sp_matrix2.pop(-1)
        rows2, cols2 = dimensions2

        if cols1 != rows2:
            raise ValueError("Inner matrix dimensions do not match")
    else:
        dimensions1 = sp_matrix1.pop(-1)
        rows1, cols1 = dimensions1
        rows2, cols2 = dimensions1


    ##Lets follow the mat_mult, step by step, but use the dict-format:
    for i in range(rows1):
        for j in range(cols2):
            val = 0
            for k in range(cols1):
                #The dict returns a missing key as None
                #A None Value is equal to a zero-entry in the original matrix.
                v1 = sp_matrix1.get((i,k))
                v2 = sp_matrix2.get((k,j))
                if v1 is not None and v2 is not None:
                    val += v1*v2
            sp_matrix_res[(i,j)] = val

    #inserting dimensions back again:
    sp_matrix1[-1] = dimensions1
    sp_matrix2[-1] = dimensions2
    sp_matrix_res[-1] = (rows1, cols2)

    ##MYCODESEND##
    return sp_matrix_res



#### EIGENE FUNKTIONEN:
def sparse_to_dense(sparse):
    print(sparse)
    dimensions = sparse.pop(-1)# pop dimension-key,
    # ... so we don't have to ignore it, while looping over the dict
    rows, cols = dimensions

    dense = [[0 for _ in range(cols)] for _ in range(rows)]
    for key, val in sparse.items():
        row, col = key
        dense[row][col] = val
    sparse[-1] = dimensions #insert the dimensions again
    return dense


if __name__=="__main__":
    #WARNING: Not all the conditions are checked!!!
    a = [
        [1,0],
        [2,3]
    ]
    b = [
        [1,2,3],
        [4,5,6]
    ]

    sp_a = dense_to_sparse(a)
    sp_b = dense_to_sparse(b)
    c = sparse_mat_mult(sp_a, sp_b)
    print(c)
    print(show_sparse(c))

    print()
    t_a = sparse_transpose(sp_a)
    print(show_sparse(sp_a))
    print()
    print(show_sparse(t_a))

    t_b = sparse_transpose(sp_b)
    print()
    print(show_sparse(sp_b))
    print()
    print(show_sparse(t_b))
    """
    for row in a:
        print(row)
    print(get_shape(a))
    sp_a = dense_to_sparse(a)
    print(sp_a)
    b = sparse_to_dense(sp_a)
    for row in b:
        print(row)

    c = sparse_mat_add(sp_a, sp_a)
    print(c)
    print(show_sparse(c))
    """
    """
    iters = 100

    for iter in range(iters):
        r1 = random.randint(1,100)
        c1 = random.randint(1,100)
        c2 = random.randint(1,100)
        no_match = False
        if random.random() < 0.9:
            r2 = c1
        else:
            r2 = random.randint(1,100)
            if r2 != c1:
                no_match = True
        ll_sp_m1 = generate_random_sparse_matrix(3,4)
        ll_sp_m2 = generate_random_sparse_matrix(4,2)

        sp_m1 = dense_to_sparse(ll_sp_m1)
        sp_m2 = dense_to_sparse(ll_sp_m2)

        if(not is_equal(ll_sp_m1,sp_m1) or not is_equal(ll_sp_m2,sp_m2)):
            raise Exception("Wrong conversion from dense to sparse")

        sp_m1T = sparse_transpose(sp_m1)
        sp_m1TT = sparse_transpose(sp_m1T)
        if(not is_equal(ll_sp_m1,sp_m1TT)):
            raise Exception("Wrong sparse transpose operation")

        try:
            ll_mult = mat_mult(ll_sp_m1, ll_sp_m2)
            sp_mult = sparse_mat_mult(sp_m1, sp_m2)
        except ValueError as e:
            print(e)
            if(not no_match):
                raise

        if(not is_equal(ll_mult,sp_mult)):
            raise Exception("Wrong sparse matrix multiplication operation")
    """