Implementation of Sparse Arrays

A Sparse Array is an array that contains mostly zero values. On the contrary, the majority of the elements are non-zero in the dense array. One question that might come to your mind that why sparse arrays are discussed separately and not treated like regular arrays? The thing is, most of the elements are zero in a sparse array, and they won’t be of any use when we work with them or perform operations on them.

Moreover, storing zero-values will waste memory space as well. For example, if we have a matrix of 20 by 20, and only 50 values are non-zero; storing the complete 2D array will waste space and consume more time as well. Therefore, some other strategy needs to be employed that represents such data efficiently. Many methods exist for the implementation of sparse arrays. We will talk about three such ways in this article.


Representation using Arrays.

The main catch here is that we only need to store the non-zero values. Therefore, one of the implementations is to create a 2D array, in which each internal array contains three columns. The first column has the row index, the second column contains the column index, and the third one stores the value. The size of this 2D would be a number of non-zero values×3.

Taking the above example, we will have a 50 by three array now, instead of a 20 by 20. You can see here that this method is relatively more efficient.

Consider the code given below.

sparseArray = [
    [1, 0, 3, 0, 0],
    [0, 0, 1, 0, 0],
    [2, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 5, 0, 0, 9],
]
rows = len(sparseArray)
cols = len(sparseArray[0])
#count number of non-zero values
count = 0
compactArray = []
for i in range(0, rows):
    for j in range(0, cols):
        if sparseArray[i][j]!=0:
            compactArray.append([i, j, sparseArray[i][j]])
            count += 1


#traverse the array
print("row", "col", "val")
for i in range(0, len(compactArray)):
    print(compactArray[i][0], "\t", compactArray[i][1], "\t", compactArray[i][2])

#sparsity
size = rows*cols
sparsity = (size-count)/size
print("Sparsity", sparsity)

Output

row col val

0              0             1

0              2             3

1              2             1

2              0             2

4              1             5

4              4             9

Sparsity 0.76


Representation using List of Lists

This is another representation of sparse Arrays. As the name suggests, it includes a list of lists (Linked Lists). A node in the outer linked list contains the index of a row and an inner list. It also points to the next row node. Moreover, a node in a sublist has a column index, a value at that row and column, and a pointer to the next node. Consider the figure below that illustrates the above concept.

 

Let’s go ahead and see its implementation.

class RowNode(object):
    def __init__(self, index=None, nextRowNode=None, colNode=None):
        self.index=index
        self.nextRowNode=nextRowNode
        self.colNode=colNode


class ColumnNode(object):
    def __init__(self, index=None, value=None, nextNode=None ):
        self.index=index
        self.value=value
        self.nextNode=nextNode


def createColNodes(sparseArray, j, curRowNode): 
    curColNode = ColumnNode(j, sparseArray[curRowNode.index][j]) #create the current inner node
    rightHead = curRowNode.colNode
    if (rightHead==None): #if it is the first node in the innerList
        curRowNode.colNode = curColNode
    else:
        while (rightHead.nextNode):
            rightHead = rightHead.nextNode
        rightHead.nextNode=curColNode


def createRowNodes(sparseArray, m, n): #m rows and n columns in the sparse Array
    global head
    for i in range(0, m):
        curRowNode = RowNode(i) #creating a row node with the current row index
        if i==0: #first row node
            head = curRowNode #set the head
        else:
            tempRowNode = head
            while (tempRowNode.nextRowNode):
                tempRowNode = tempRowNode.nextRowNode
            tempRowNode.nextRowNode = curRowNode

        #add the value to the inner node
        for j in range(0, n):
            if sparseArray[i][j]!=0:
                createColNodes(sparseArray, j, curRowNode)

rows = len(sparseArray)
cols = len(sparseArray[0])
head = RowNode() #initial start node for row index 0
createRowNodes(sparseArray, rows,cols)

In the above code, class RowNode is responsible for creating a node in the outer linked list, and class ColumnNode creates a node for the inner linked list. The head variable refers to the first node in the outer rows list, i.e., its index value will be 0. As you can observe in the createRowNodes() method, we iterate through the sparseArray row by row. First, we create a row node and add it at the appropriate place of the outer linked list, i.e., iterate through the list until we find the last node. Then, we iterate through columns in that row and find non-zero values. The non-zero value, column index, and row node gets passed to the createColNodes() method, where we create the inner node and add it to the sub list.

Let’s now traverse through this list of lists.

def traverse():
    global head
    if (head.index==None):
        print("Empty Sparse Array")
        return;
    st = head
    print("row", "col", "val")
    while (st):
        col = st.colNode
        while(col):
            print(st.index, "\t", col.index, "\t", col.value)
            col = col.nextNode
        st = st.nextRowNode

Output

row col val

0              0             1

0              2             3

1              2             1

2              0             2

4              1             5

4              4             9


Representation using Dictionary of Keys

In this representation, we use a dictionary to store the sparse array. The key is a row and column pair, i.e., (row, column), and the value is the data stored at the position.

Consider the following code below.

sparseArray = [
    [1, 0, 3, 0, 0],
    [0, 0, 1, 0, 0],
    [2, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 5, 0, 0, 9],
]
rows = len(sparseArray)
cols = len(sparseArray[0])

dok = {} #dictionay of keys
for i in range(0, rows):
    for j in range(0, cols):
        if sparseArray[i][j]!=0:
            dok[(i, j)] = sparseArray[i][j] #add the value to the dictionary


for key, value in dok.items(): #iterate through the dictionary
    print("Key:", key,"Value:", value)

Output

Key: (0, 0) Value: 1
Key: (0, 2) Value: 3
Key: (1, 2) Value: 1
Key: (2, 0) Value: 2
Key: (4, 1) Value: 5
Key: (4, 4) Value: 9

 

Back to: Data Structure > Data Structure - Arrays

Leave a Reply

Your email address will not be published. Required fields are marked *