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 occurence of zero elements in a large array is both computational and storage inconvinient. An array in which there is large number of zero elements is referred to as being sparse.

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.

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