- For Phyton Please Import Random Import Math Below 1 (258.7 KiB) Viewed 37 times
- For Phyton Please Import Random Import Math Below 2 (285.86 KiB) Viewed 37 times
import math
################################################################
### Below are the functions you need to implement in the HW.
###
### Feel free to create your own helper functions.
###
################################################################
def dense_to_sparse(matrix):
"""
This function converts a sparse matrix in list of
lists representation to
a sparse matrix in dictionary representation.
You need to implement this function.
"""
sp_matrix = {}
return sp_matrix
def sparse_transpose(sp_matrix):
"""
This function takes the transpose of the input sparse
matrix (sp_matrix)
and returns the result (result is also a sparse
matrix).
You need to implement this function.
"""
sp_transpose = {}
return sp_transpose
def sparse_add(sp_matrix1, sp_matrix2):
"""
This function computes the sum of the two input
sparse matrices and
returns the result (result is also a sparse
matrix).
You need to implement this function.
"""
sp_res = {}
return sp_res
def sparse_multiply(sp_matrix1, sp_matrix2):
"""
This function multiplies the two input sparse
matrices and returns
the result (result is also a sparse matrix).
You need to implement this function.
"""
sp_matrix_res = {}
return sp_matrix_res
################################################################
### Below are some functions we are providing you to help
###
### you test your solutions. They won't be graded.
###
################################################################
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.randint(1,20)
return res
def main():
"""
This function contains some test cases for you to
test your solutions.
We recommend that you create additional test cases
for yourself.
"""
ll_sp_m1 = generate_random_sparse_matrix(3, 5)
ll_sp_m2 = generate_random_sparse_matrix(5, 2)
ll_sp_m3 = generate_random_sparse_matrix(3, 5)
print(ll_sp_m1)
print(ll_sp_m2)
sp_m1 = dense_to_sparse(ll_sp_m1)
sp_m2 = dense_to_sparse(ll_sp_m2)
sp_m3 = dense_to_sparse(ll_sp_m3)
#print(sp_m1)
#print(sp_m2)
sp_m1_transpose = sparse_transpose(sp_m1)
sp_m2_transpose = sparse_transpose(sp_m2)
#print(sp_m1_transpose)
#print(sp_m2_transpose)
add1 = sparse_add(sp_m1, sp_m3)
add2 = sparse_add(sp_m1, sp_m2)
#print(add1)
#print(add2)
mult1 = sparse_multiply(sp_m1, sp_m2)
mult2 = sparse_multiply(sp_m1, sp_m3)
#print(mult1)
#print(mult2)
main()
Alright I have added as text...
In this homework, you will use dictionaries to store sparse matrices. Let Anxm be a sparse matrix with N rows and M columns, stored as a list of lists. Let Abe the element of A in the i'th row and j'th column (i=0...N-1, j=0...M-1). Then, this sparse matrix can be stored as a dictionary as follows: . Let sp A be the Python dictionary that will store A The keys are tuples of the row and column indices of non-zero elements, that is: sp_A[(i, j)]= Aij, where A + 0 A special key (-1) stores the dimensions of the matrix as a list: sp_A(-1)=[N,M] Open SparseMatrix.py and examine the code given to you. Then, solve the following parts. Part A (10 pts): Implement the function dense_to_sparse(matrix). matrix is a sparse matrix stored in list-of-lists representation. This function should convert it to dictionary representation as explained above and return the result. For example, the input matrix A and the return value sp_A could be: Го 3 A= 1 0 → sp_A[(0,1)] = 3, sp_A[(1,0)] = 1, sp_A(-1) = [2, 3] Another example – consider the following matrix in list of lists representation: [[0, 0, 0, 0, 1], [1, 7, 9, 3, 0], [0, 0, 0, 10, 16]] Its dictionary representation is: {-1: [3, 5), (0, 4): 1, (1, 0): 1, (1, 1): 7, (1, 3): 3, (2, 3): 10, (2, 4): 16} Part B (5 pts): Implement the function sparse_transpose(sp_matrix). sp_matrix is a sparse matrix stored in dictionary representation. This function should compute the transpose of sp_matrix and return the result. The result should also be a sparse matrix in dictionary representation. Mathematically, the transpose operation is converting Aij -> Aji. For example, the input matrix A and its transpose At could be: 0 1- (939-*-| A 이 AT 3 0 1 0 0 0 Note that in your program, both A and AT are sparse matrices stored in dictionary representation, not as a list of lists. The transpose of the example given at the end of Part A is: {-1: [5, 3], (4, 0): 1, (0, 1): 1, (1, 1): 7, (3, 1): 3, (3, 2): 10, (4, 2): 16}
Part C (10 pts): Implement the function sparse_add(sp_matrix1, sp_matrix2). sp_matrix1 and sp_matrix2 are sparse matrices stored in dictionary representation. This function should compute the SUM of these matrices and return the result. The result should also be a sparse matrix in dictionary representation. Here, we are performing element-wise sum of the two matrices. Let Anxm and BNxm be two matrices. Then, their sum should have the same dimensions (CNxm) and its elements should be calculated as: Cij = Aj + Bij. If the dimensions of sp_matrix1 and sp_matrix2 do not match, sparse_add should return -1. For example, if we add the following two matrices: {-1: [3, 5), (0, 4): 1, (1, 0): 1, (1, 1): 7, (1, 3): 3, (2, 3): 10, (2, 4): 16} {-1: [3, 5), (0, 2): 5, (1, 1): 6, (2, 1): 14, (2, 2): 10, (2, 3): 2, (2, 4): 20} We should find: {-1: [3, 5), (0, 4): 1, (1, 0): 1, (1, 1): 13, (1, 3): 3, (2, 3): 12, (2, 4): 36, (0, 2): 5, (2, 1): 14, (2, 2): 10} . . Part D (10 pts): Implement the function sparse_multiply(sp_matrix1, sp_matrix2). sp_matrix 1 and sp_matrix2 are sparse matrices stored in dictionary representation. This function should compute the MULTIPLICATION of these matrices and return the result. The result should also be a sparse matrix in dictionary representation. Let Anxm, BM&K be two matrices and let CNxK = AB be their multiplication. The elements of C are calculated as: Cij = D.O AikBkj k=0 For matrix multiplication to work, number of columns in sp_matrix1 should be equal to the number of rows in sp_matrix2. If that is not the case, sparse_multiply should return -1. By the end of multiplication, you may end up with O values in your result dictionary (if Cj = 0). In this part only, we prefer that those Os stay in your dictionary. Do not delete them. For example, if we multiply the following two matrices: {-1: [3, 5), (0, 4): 1, (1, 0): 1, (1, 1): 7, (1, 3): 3, (2, 3): 10, (2, 4): 16} {-1: [5, 2], (1, 1): 19, (2, 0): 14, (3, 0): 16, (4, 1): 17} We should find: {-1: [3, 2), (0, 0): 0, (0, 1): 17, (1, 0): 48, (1, 1): 133, (2, 0): 160, |(2, 1): 272}
import random import math ######## ################# ####### ############## ### Below are the functions you need to implement in the HW. ### ### Feel free to create your own helper functions. ### ################################# ############### ###### def dense_to_sparse(matrix) : This function converts a sparse matrix in list of lists representation to a sparse matrix in dictionary representation. You need to implement this function. sp_matrix = {} return sp_matrix def sparse_transpose( sp_matrix): This function takes the transpose of the input sparse matrix (sp_matrix) and returns the result (result is also a sparse matrix). You need to implement this function. sp_transpose = {} return sp_transpose def sparse_add(sp_matrix1, sp_matrix2): This function computes the sum of the two input sparse matrices and returns the result (result is also a sparse matrix). You need to implement this function. sp_res = {} return sp_res def sparse_multiply(sp_matrix1, sp_matrix2): This function multiplies the two input sparse matrices and returns the result (result is also a sparse matrix). You need to implement this function. sp_matrix_res = {} return sp_matrix_res
################################################################ ### Below are some functions we are providing you to help ### ### you test your solutions. They won't be graded. ### ################################################################ 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)*nrowincol) pos = random. sample(range (nrowincol), nr) for ind in pos: n_ind = math.floor(ind/ncol) m_ind = ind-n_ind*ncol res [n_ind] [m_ind]=random.randint(1, 20) return res def main(): This function contains some test cases for you to test your solutions. We recommend that you create additional test cases for yourself. 1l_sp_m1 = generate_random_sparse_matrix(3, 5) ll_sp_m2 = generate_random_sparse_matrix(5, 2) ll_sp_m3 = generate_random_sparse_matrix(3, 5) print(ll_sp_m1) print(ll_sp_m2) sp_m1 = dense_to_sparse(ll_sp_m1) sp_m2 = dense_to_sparse(ll_sp_m2) sp_m3 = dense_to_sparse(ll_sp_m3) #print(sp_m1) #print(sp_m2) sp_m1_transpose = sparse_transpose( sp_m1) sp_m2_transpose = sparse_transpose( sp_m2) #print(sp_m1_transpose) #print(sp_m2_transpose) add1 = sparse_add(sp_mi, sp_m3) add2 = sparse_add(sp_mi, sp_m2) #print(add1) #print(add2) mult1 = sparse_multiply(sp_mi, sp_m2) mult2 = sparse_multiply(sp_mi, sp_m3) #print(multi) #print(mult2) main()