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).

As an example, a spreadsheet containing 100×100 mostly empty cells might be more efficiently stored as a linked list rather than an array containing ten thousand array elements. 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 lists which requires less memory as elements having non-zero value only are stored

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.

Sparse Array as Linked Lists

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. For manipulation of large sparse arrays the elements of such arrays can be accessed through less number of iterations if we use linked list instead of ordinary 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 vali appear at positions posi.

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.