- Sparse array
In
computer science , a sparse array is anarray in which most of the elements have the same value (known as the default value -- usually 0 or 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 100x100 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 .See also
*
Sparse matrix External links
* [http://boost.org/libs/numeric/ublas/doc/vector_sparse.htm Boost sparse vector class]
* [http://portal.acm.org/citation.cfm?id=1363086&jmp=cit&coll=GUIDE&dl=GUIDE| Rodolphe Buda, "Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm", "Computational Economics", 31(4), May, pp.397--408, 2008.]
Wikimedia Foundation. 2010.
