Program to store a sparse matrix as a dictionary in Python

In this tutorial, we will learn how to store sparse matrix in an efficient way by using dictionary in Python. Many times we come across situations, where the memory is wasted for storing data in an inefficient way. To overcome this problem, we can make use of data structures like dictionary in Python.

DICTIONARY

Dictionary is a data structure in which we store values as a pair of key and value.

  • Each of its key is isolated from its value by a colon (:).
  • Consecutive items are distinct by commas (,).

syntax:

Dictonary_name={key1:value_1,key2:value_2...}

SPARSE MATRIX

It is a matrix that contains very few non-zero elements. Most of its elements are zero. When it is represented with a 2-dimensional array, we waste a lot of space in the memory.

Since most of its elements are zero, we try to store only the non-zero elements since the rest all the elements are just going to be zero anyway. So, now a question arises as to why use this sparse matrix ?.

The answer is that these matrix are so much useful to store data that contains a large number of zero-valued elements and can save a lot of memory and also speed up the processing.


[1,]    [2,]      [3,]     [4,]     [5,]

[,1]    2         0        0         0          0

[,2]   0         0         0         0          1

[,3]   2          0          2         0         0

[,4]    0        0          0         3         0

[,5]    1        4           0         0         0


To store this more efficiently in the memory, we use dictionary in Python. By using dictionary we can simply indicate the rows and columns that contain the non zero element along with the value present in them.

matrix=[[0,0,0,1,0],
        [2,0,0,0,3],
        [0,0,0,4,0]]
Dict={}
print("Sparse Matrix")
for i in range (len(matrix)):
     print("\n")
     for j in range(len(matrix[i])):
         print(matrix[i][j],end=' ')
         if matrix[i][j]!=0:
            Dict[(i,j)]=matrix[i][j]
print("\n\n Sparse Matrix can be efficiently represented as Dictionary :")
print(Dict)



OUTPUT

Sparse Matrix
0 0 0 1 0
2 0 0 0 3
0 0 0 4 0
sparse matrix can be efficiently represented as Dictionary:
{(0, 3): 1, (2, 3): 4, (1, 0): 2, (1, 4): 3}

In the above example, the matrix contains only 4 non zero elements and hence they are displayed in the form of dictionary.

Leave a Reply

Your email address will not be published.