In this article, we will learn how to use a dictionary in Python to store the sparse matrix in an efficient manner. We frequently encounter instances in which Memory is wasted for improper/inefficient data storage. To solve this problem, we can use data structures like the dictionary in Python.
Dictionary in Python:
A dictionary is a type of data structure that stores values as a pair of key and value.
A colon (:) separates each of its keys from its value.
Commas (,) are used to separate consecutive items.
Syntax:
dict = {key_1: value1, key_2: value2...}What is Sparse Matrix?
It is a matrix with very few non-zero elements. The majority of its elements are zero. We waste a lot of memory space when we express it with a 2-dimensional array.
Because the majority of its elements are zero, we aim to store only the non-zero elements because the remainder of the elements will be zero anyhow. So the question is, why employ this sparse matrix?
The explanation is that these matrices are extremely beneficial for storing data with a large number of zero-valued elements because they save a lot of memory while simultaneously speeding up processing.
Example
0 0 0 1 0 6 0 0 0 8 0 2 0 0 0 // sparse matrix with 4 non-zero elements
The usage of a 2D array to represent a sparse matrix wastes a lot of memory because the zeroes in the matrix are useless in most circumstances. As a result, rather than keeping zeroes alongside non-zero elements, we just store non-zero elements.
These efficient methods simply require the only non-zero values to be saved together with their index, allowing the original matrix to be accessed when needed. The use of a dictionary is one such efficient method in Python. In Python, dictionaries, like maps in Java, store data in key-value pairs. The data in a dictionary is stored in an unordered way.
Program to Store a Sparse Matrix as a Dictionary in Python
Approach:
- Give the matrix as static input and store it in a variable
- Take a new empty dictionary and store it in another variable.
- Loop till the length of the given matrix(rows) using the for loop
- Loop till the number of columns using another Nested For loop
- Print the matrix Value
- Check if the matrix values is equal to 0 or not using the If conditional statement
- If the value is non zero then
- Take a tuple(i,j)(where i is the row number and j is the column number) as a key to the dictionary and value as matrix value
- Printing new line.
- The Exit of the Program.
Below is the implementation:
# Give the matrix as static input and store it in a variable
mat=[[0,5,0,0,0],
[2,0,0,0,0],
[0,0,0,3,0]]
# Take a new empty dictionary and store it in another variable.
dic={}
print("Printing the Sparse Matrix")
# Loop till the length of the given matrix(rows) using the for loop
for i in range (len(mat)):
# Loop till the number of columns using another Nested For loop
for j in range(len(mat[i])):
# Print the matrix Value
print(mat[i][j],end=' ')
# Check if the matrix valies is equal to 0 or not using the If conditional statement
if mat[i][j]!=0:
# If the value is non zero then
# Take a tuple(i,j)(where i is the row number and j is the column number) as a key
# to the dictionary and value as matrix value
dic[(i,j)]=mat[i][j]
# Printing new line
print("\n")
print("\nPrinting the Sparse Matrix efficiently which is represented as Dictionary :")
print(dic)Output:
Printing the Sparse Matrix
0 5 0 0 0
2 0 0 0 0
0 0 0 3 0
Printing the Sparse Matrix efficiently which is represented as Dictionary :
{(0, 1): 5, (1, 0): 2, (2, 3): 3}