Sparse array
From Wikipedia, the free encyclopedia
A sparse array in computing is an array where most of the elements have the same value (called the default value -- usually 0 or null) and only a few elements have a non-default value. Arrays are data structures used in programming languages, databases, and other computer systems. They use a value, called a subscript or an index, that indicates a position to locate a particular value.
A naive implementation may allocate space for the entire array, but this is inefficient since there are only a few non-default values. If the sparsity is known in advance, more space-efficient implementations can be used which allocate space only for the non-default values.
Example: An array with length of one million, where only the indices 1, 3, 120 and 999999 have non-default values, is sparse. It would be inefficient to allocate any space for the 999996 array elements with default values.
[edit] See also
 |
This computer-related article is a stub. You can help Wikipedia by expanding it. |
