Sparse Array Data Structure

A Sparse Array Data Structure is an array data structure that is populated mostly with a single data value.

• Context:
  • It can range from being a Column-oriented Sparse Array Structure to being a Row-oriented Sparse Array Structure.
• Example(s):
  • a Python sparse_list[1].
  • a Sparse Bit Array.
  • …
• Counter-Example(s):
  • a Dense Array Data Structure.
  • a Sparse Matrix Data Structure.
• See: Nullable Type, Bit Array.

---

---

References

2014

• (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Sparse_array Retrieved:2014-11-18.
  • 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 inefficient for both computation and storage. An array in which there is a large number of zero elements is referred to as being sparse.

    In the case of sparse arrays, one can ask for a value from an "empty" array position. If one does this, then for an array of numbers, a value of zero should be returned, and for an array of objects,

    a value of null should be returned.

    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., the elements occur in blocks).
    

    A heap memory allocator in a program might choose to store regions of blank space in a linked list rather than storing all of the allocated regions in, say a bit array.

---