Sparse array

In computer science, a sparse array is an array in which most of the elements have the same value (known as the default value—usually 0 or null). The occurrence of zero elements in a large array is inconvenient for both computation and storage. An array in which there is large number of zero elements is referred to as being sparse.

In case of sparse arrays, we can ask for a value from an "empty" array position. If we do this, then for array of numbers, it should return zero and for array of objects, it should return null.

A naive implementation of an array may allocate space for the entire array, but in the case where there are few non-default values, this implementation is inefficient. Typically the algorithm used instead of an ordinary array is determined by other known features (or statistical features) of the array, for instance if the sparsity is known in advance, or if the elements are arranged according to some function (e.g. occur in blocks).
A heap memory allocator inside a program might choose to store regions of blank space inside a linked list rather than storing all of the allocated regions in, say a bit array.

Representation

Sparse Array can be represented as

Sparse_Array[{pos1 -> val1, pos2 -> val2,...}] or
Sparse_Array[{pos1, pos2,...} -> {val1, val2,...}]

which yields a sparse array in which values $val_{i}$ appear at positions $pos_{i}$.

Sparse Array as Linked List

An obvious question might be asked that why we need linked list to represent sparse array if we can represent it using normal array easily. The answer to this question lies in the fact that while representing sparse array as normal array, a lot of space is allocated for zero or null elements. For example, consider following array declaration:

double arr[1000][1000];

When we define this array an enough space of 1,000,000 doubles is allocated. As each double requires 8 bytes of memory, this array will require 8 million bytes of memory. Now this being a sparse array, most of its elements will have a zero(or null) value. Hence, defining this array will soak up all this space which will result in wastage of memory. An effective way to overcome this problem is to represent the array using linked list which requires less memory as elements having non-zero value only are stored. Also, the array elements can be accessed through less number of iterations than normal array when linked lists are used.

A sparse array as linked list contains nodes linked to each other. In one-dimensional sparse array each node consist of an "index" (position) of the non-zero element and the "value" at that position and a node pointer "next"(for linking to the next node), nodes are linked in order as per the index.In case of two-dimensional sparse array each node contains row index, column index(together gives us position), value at that position and a node pointer next.

See also

• Sparse matrix

External links

• Boost sparse vector class
• Rodolphe Buda, "Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm", Computational Economics, 31(4), May, pp.397–408, 2008.